[an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] (none) [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] (none) [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive]
 
[an error occurred while processing this directive] [an error occurred while processing this directive]
Skåne Sjælland Linux User Group - http://www.sslug.dk Home   Subscribe   Mail Archive   Forum   Calendar   Search
MhonArc Date: [Date Prev] [Date Index] [Date Next]   Thread: [Date Prev] [Thread Index] [Date Next]   MhonArc
 

Re: [MISC] Programeringssproget BrainFuck



Peter Makholm <sslug@sslug> wrote:
: Morten Sylvest Olsen <sslug@sslug> writes:

:> Er muligheden for at blive stående med i Turings oprindelige?

: Den oprindelige Turingmaskine starter med at læse symbolet i den
: aktuelle celle, så skriver den et symbol (eventuelt det samme) og så
: flytter den enten til højre eller venstre. En maskincyclus er derfor
: altid læse, skrive og flytte.

Ja, sådan lærte jeg den også at kende. Dog til at begynde med kun med
et enkelt uendeligt tape.

: Sådan lige uden at tænke nærmere over det, så vil programmet i den
: originale maskine højst være liniært større i antallet af symboler og
: antallet af tilstande end programmet i en maskine der kan undlade at
: læse, skrive og flytte.

Ja, der findes jo mange Turing ækvivalente maskiner. Jeg sidder foran en
nu ;-) Men også Post maskiner, Turing med stay-option, Nondeterministisk 
TM, PDA med 2 stakke etc.

:> Desuden er båndet uendeligt i begge retninger i Turings oprindelig TM...

: Men husk at den for alle inddata skal afslutte efter endelig tid og
: kan dermed kun bruge endelig meget hukommelse. "Vilkårlig langt", vil
: derfor være en bedre beskrivelse.

Hmm, hvem siger den skal afslutte?

Hvis det definerede sprog er rekursivt enumerabelt, så er der 3 klasser, 
nemlig ord der accepteres, ord der afvises og ord hvorpå der køres i 
uendelig løkke.

Mvh Morten
-- 



 
Home   Subscribe   Mail Archive   Index   Calendar   Search

 
 
Questions about the web-pages to <www_admin>. Last modified 2005-08-10, 19:22 CEST [an error occurred while processing this directive]
This page is maintained by [an error occurred while processing this directive]MHonArc [an error occurred while processing this directive] # [an error occurred while processing this directive] *