Toestand
Stappen
Symbolen op de band
Status

In toestand Leest Schrijft Beweegt Volgende toestand

Meer over Turingmachines

Turingmachine-simulator

Een Turingmachine is de eenvoudigst mogelijke computer: een kop die één symbool van een eindeloze band leest, een symbool schrijft, één cel naar links of rechts gaat en van toestand verandert, volgens een korte tabel met regels. Alan Turing bedacht hem in 1936, en alles wat je computer doet, kan in principe op deze manier. Schrijf je eigen regels of laad een voorbeeld, druk op Uitvoeren en kijk hoe de band stap voor stap verandert, met daaronder een diagram van de hele geschiedenis. Kies een programma of schrijf er zelf een, voer de invoer in en druk op Uitvoeren, of op Stap om één regel tegelijk te volgen; Terug maakt een stap ongedaan. Het programma bestaat uit regels, één per tekstregel: toestand, gelezen symbool, te schrijven symbool, beweging (L, R of N voor geen beweging) en de volgende toestand, bijvoorbeeld A 0 -> 1 R B. Gebruik _ voor een lege cel. De machine begint in de toestand van de eerste regel, op het eerste symbool van de invoer, en stopt in H, accept of reject, of wanneer geen enkele regel past. Het diagram toont de band na elke stap, van boven naar beneden.

Hoe het werkt

  1. Kies een voorbeeldprogramma of schrijf regels zoals A 0 -> 1 R B, één per tekstregel, en typ de invoer.
  2. Druk op Uitvoeren om de kop te zien bewegen, of op Stap om één regel tegelijk te volgen; Terug maakt een stap ongedaan.
  3. Lees de toestand, de stappen en de symbolen op de band af in de tegels, en de geschiedenis van de band in het diagram.

Hoe de machine werkt

Op elk moment is de machine in een van een paar toestanden en staat haar kop op één cel van de band. De regel voor die toestand en het symbool onder de kop zegt drie dingen: welk symbool er in de cel geschreven wordt, of de kop naar links, naar rechts of helemaal niet beweegt, en naar welke toestand de machine daarna gaat. Dat is de hele machine. Ze stopt wanneer ze een stoptoestand bereikt, zoals H, accept of reject, of wanneer geen enkele regel past. Een programma dat 1 optelt bij een binair getal heeft maar negen van zulke regels nodig.

Bezige bevers

Welke machine met n toestanden, gestart op een lege band, schrijft de meeste enen voordat ze stopt? Tibor Radó stelde die vraag in 1962. De kampioenen heten bezige bevers (busy beavers), en ze groeien sneller dan elke functie die een computer kan berekenen. Twee toestanden geven 4 enen in 6 stappen, drie toestanden 6 enen, vier toestanden 13 enen in 107 stappen. De kampioen met vijf toestanden, gevonden in 1989, schrijft 4.098 enen in 47.176.870 stappen, en in 2024 bewees een online samenwerking met door een computer gecontroleerde wiskunde dat geen enkele andere machine met vijf toestanden die stopt langer doorgaat.

Veelgestelde vragen

Hoe schrijf ik een regel?

Eén regel per tekstregel: de huidige toestand, het symbool dat gelezen wordt, het symbool dat geschreven wordt, de beweging (L, R of N) en de volgende toestand, bijvoorbeeld A 0 -> 1 R B. De pijl en de komma's zijn optioneel. Gebruik _ voor een lege cel en # voor commentaar. De machine begint in de toestand van de eerste regel; een volgende toestand met de naam H of halt laat haar stoppen, en accept en reject laten haar stoppen met een oordeel.

Kan een Turingmachine echt alles berekenen?

Alles wat welke computer dan ook kan berekenen, met genoeg band en tijd: dat is de these van Church–Turing. Een Turingmachine heeft geen geheugenlimiet, dus in die zin is ze krachtiger dan elke echte computer, al is ze veel trager. Wat ze niet kan, is elke vraag beantwoorden: Turing bewees dat geen enkele machine voor elk programma en elke invoer kan beslissen of het zal stoppen.

Waarom stopt de teller nooit?

Zijn regels leiden nooit naar een stoptoestand. Hij telt steeds 1 op bij een binair getal aan het rechteruiteinde van de band en loopt weer terug, dus het getal groeit eindeloos. Volgens Turings stopprobleem bestaat er geen algemene methode die voor elke machine kan zeggen of ze zal stoppen; bij deze eenvoudige teller zie je het, maar voor sommige machines met maar zes toestanden weet nog niemand het.

Hoe kan de bezige bever met vijf toestanden hier 47 miljoen stappen doen?

De band wordt opgeslagen als een compacte array die in beide richtingen groeit, en op de snelste stand voert de app honderdduizenden stappen uit tussen twee schermverversingen, zodat de hele run in een moderne browser een paar seconden duurt. Het diagram legt alleen de eerste 400 stappen vast, want een afbeelding van 47 miljoen rijen past op geen enkel scherm.

Wordt er iets naar een server gestuurd?

Nee. Het programma draait in je browser, en je programma en invoer blijven in de lokale opslag van deze browser.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Ga naar Editor