| I tillstånd | Läser | Skriver | Flyttar | Nästa tillstånd |
|---|
Turingmaskinsimulator
En Turingmaskin är den enklaste tänkbara datorn: ett huvud som läser en symbol på ett oändligt band, skriver en symbol, flyttar sig en cell åt vänster eller höger och byter tillstånd, enligt en kort tabell med regler. Alan Turing uppfann den 1936, och allt din dator gör kan i princip göras på det här sättet. Skriv egna regler eller läs in ett exempel, tryck på Kör och se bandet förändras steg för steg, med ett diagram över hela dess historik nedanför. Välj ett program eller skriv ett eget, ange indata och tryck på Kör, eller på Steg för att följa en regel i taget; Tillbaka ångrar ett steg. Varje rad i programmet är en regel: tillstånd, läst symbol, symbol att skriva, förflyttning (L, R eller N för ingen förflyttning) och nästa tillstånd, till exempel A 0 -> 1 R B. Använd _ för en tom cell. Maskinen startar i den första regelns tillstånd, på den första symbolen i indata, och stannar i H, accept eller reject, eller när ingen regel passar. Diagrammet visar bandet efter varje steg, uppifrån och ned.
Hur det fungerar
- Välj ett exempelprogram eller skriv regler som A 0 -> 1 R B, en per rad, och skriv in indata.
- Tryck på Kör för att se huvudet röra sig, eller på Steg för att följa en regel i taget; Tillbaka ångrar ett steg.
- Läs av tillståndet, stegen och symbolerna på bandet i rutorna och bandets historik i diagrammet.
Så fungerar maskinen
I varje ögonblick befinner sig maskinen i ett av några få tillstånd, och dess huvud står på en cell av bandet. Regeln för det tillståndet och symbolen under huvudet säger tre saker: vilken symbol som ska skrivas i cellen, om huvudet ska flytta sig åt vänster, åt höger eller inte alls, och vilket tillstånd maskinen ska gå till härnäst. Det är hela maskinen. Den stannar när den når ett stopptillstånd, som H, accept eller reject, eller när ingen regel passar. Ett program som adderar 1 till ett binärt tal behöver bara nio sådana regler.
Flitiga bävrar
Vilken maskin med n tillstånd, startad på ett tomt band, skriver flest ettor innan den stannar? Det frågade Tibor Radó 1962. Mästarna kallas flitiga bävrar (busy beavers), och de växer snabbare än någon funktion som en dator kan beräkna. Två tillstånd ger 4 ettor på 6 steg, tre tillstånd 6 ettor, fyra tillstånd 13 ettor på 107 steg. Mästaren med fem tillstånd, som hittades 1989, skriver 4 098 ettor på 47 176 870 steg, och 2024 bevisade ett onlinesamarbete med datorkontrollerad matematik att ingen annan maskin med fem tillstånd som stannar kör längre.
Ofta ställda frågor
Hur skriver jag en regel?
En regel per rad: det aktuella tillståndet, symbolen den läser, symbolen den ska skriva, förflyttningen (L, R eller N) och nästa tillstånd, till exempel A 0 -> 1 R B. Pilen och kommatecknen är valfria. Använd _ för en tom cell och # för en kommentar. Maskinen startar i den första regelns tillstånd; ett nästa tillstånd som heter H eller halt stoppar den, och accept och reject stoppar den med ett utslag.
Kan en Turingmaskin verkligen beräkna vad som helst?
Allt som någon dator kan beräkna, med tillräckligt med band och tid: det är Church–Turings tes. En Turingmaskin har ingen minnesgräns, så i den meningen är den kraftfullare än någon verklig dator, om än mycket långsammare. Vad den inte kan är att besvara varje fråga: Turing bevisade att ingen maskin kan avgöra, för varje program och varje indata, om programmet kommer att stanna.
Varför stannar räknaren aldrig?
Dess regler leder aldrig till ett stopptillstånd. Den fortsätter att addera 1 till ett binärt tal i bandets högra ände och gå tillbaka, så talet växer för evigt. Turings stopproblem säger att ingen allmän metod kan avgöra, för varje maskin, om den kommer att stanna; för den här enkla räknaren kan du se det, men för vissa maskiner med bara sex tillstånd vet ingen det ännu.
Hur kan den flitiga bävern med fem tillstånd köra 47 miljoner steg här?
Bandet lagras som en kompakt array som växer åt båda hållen, och på den snabbaste inställningen kör appen hundratusentals steg mellan skärmuppdateringarna, så hela körningen tar några sekunder i en modern webbläsare. Diagrammet registrerar bara de första 400 stegen, eftersom en bild med 47 miljoner rader inte skulle få plats på någon skärm.
Skickas något till en server?
Nej. Programmet körs i din webbläsare, och ditt program och dina indata stannar i den här webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor