| I tilstand | Læser | Skriver | Flytter | Næste tilstand |
|---|
Turingmaskine-simulator
En Turingmaskine er den enklest mulige computer: et hoved, der læser ét symbol på et endeløst bånd, skriver et symbol, flytter sig én celle til venstre eller højre og skifter tilstand efter en kort tabel med regler. Alan Turing opfandt den i 1936, og alt, hvad din computer gør, kan i princippet gøres på denne måde. Skriv dine egne regler, eller indlæs et eksempel, tryk på Kør, og se båndet ændre sig trin for trin, med et diagram over hele dets historik nedenunder. Vælg et program, eller skriv dit eget, indtast inputtet, og tryk på Kør, eller på Trin for at følge én regel ad gangen; Tilbage fortryder et trin. Hver linje i programmet er én regel: tilstand, læst symbol, symbol, der skal skrives, bevægelse (L, R eller N for ingen bevægelse) og den næste tilstand, for eksempel A 0 -> 1 R B. Brug _ for en tom celle. Maskinen starter i tilstanden fra den første regel, på inputtets første symbol, og standser i H, accept eller reject, eller når ingen regel passer. Diagrammet viser båndet efter hvert trin, fra top til bund.
Sådan virker det
- Vælg et eksempelprogram, eller skriv regler som A 0 -> 1 R B, én pr. linje, og indtast inputtet.
- Tryk på Kør for at se hovedet bevæge sig, eller på Trin for at følge én regel ad gangen; Tilbage fortryder et trin.
- Aflæs tilstanden, trinene og symbolerne på båndet i felterne og båndets historik i diagrammet.
Sådan virker maskinen
I hvert øjeblik er maskinen i én af nogle få tilstande, og dens hoved står på én celle af båndet. Reglen for den tilstand og symbolet under hovedet siger tre ting: hvilket symbol der skal skrives i cellen, om hovedet skal flytte sig til venstre, til højre eller slet ikke, og hvilken tilstand maskinen skal gå til bagefter. Det er hele maskinen. Den standser, når den når en stoptilstand som H, accept eller reject, eller når ingen regel passer. Et program, der lægger 1 til et binært tal, behøver kun ni sådanne regler.
Travle bævere
Hvilken maskine med n tilstande, startet på et tomt bånd, skriver flest ettaller, før den standser? Det spurgte Tibor Radó om i 1962. Mestrene kaldes travle bævere (busy beavers), og de vokser hurtigere end nogen funktion, en computer kan beregne. To tilstande giver 4 ettaller på 6 trin, tre tilstande 6 ettaller, fire tilstande 13 ettaller på 107 trin. Mesteren med fem tilstande, fundet i 1989, skriver 4.098 ettaller på 47.176.870 trin, og i 2024 beviste et onlinesamarbejde med computerkontrolleret matematik, at ingen anden maskine med fem tilstande, der standser, kører længere.
Ofte stillede spørgsmål
Hvordan skriver jeg en regel?
Én regel pr. linje: den nuværende tilstand, det symbol, den læser, det symbol, den skal skrive, bevægelsen (L, R eller N) og den næste tilstand, for eksempel A 0 -> 1 R B. Pilen og kommaerne er valgfrie. Brug _ for en tom celle og # for en kommentar. Maskinen starter i tilstanden fra den første regel; en næste tilstand ved navn H eller halt standser den, og accept og reject standser den med en afgørelse.
Kan en Turingmaskine virkelig beregne alt?
Alt, hvad nogen computer kan beregne, med nok bånd og tid: det er Church–Turing-tesen. En Turingmaskine har ingen hukommelsesgrænse, så i den forstand er den mere kraftfuld end nogen rigtig computer, om end langt langsommere. Hvad den ikke kan, er at besvare ethvert spørgsmål: Turing beviste, at ingen maskine kan afgøre for ethvert program og ethvert input, om det vil standse.
Hvorfor standser tælleren aldrig?
Dens regler fører aldrig til en stoptilstand. Den bliver ved med at lægge 1 til et binært tal i højre ende af båndet og gå tilbage igen, så tallet vokser for evigt. Turings stopproblem siger, at ingen generel metode kan afgøre for enhver maskine, om den vil standse; for denne simple tæller kan du se det, men for visse maskiner med kun seks tilstande ved ingen det endnu.
Hvordan kan den travle bæver med fem tilstande køre 47 millioner trin her?
Båndet gemmes som et kompakt array, der vokser i begge retninger, og på den hurtigste indstilling kører appen hundredtusinder af trin mellem hver skærmopdatering, så hele kørslen tager et par sekunder i en moderne browser. Diagrammet registrerer kun de første 400 trin, da et billede med 47 millioner rækker ikke ville kunne være på nogen skærm.
Bliver noget sendt til en server?
Nej. Programmet kører i din browser, og dit program og input bliver i denne browsers lokale lager.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor