Turingmachines uitgelegd

In 1936, voordat er elektronische computers bestonden, vroeg de 24-jarige wiskundige Alan Turing zich af wat het betekent dat een berekening mechanisch is. Zijn antwoord was een denkbeeldige machine die zo eenvoudig is dat ze nauwelijks minder zou kunnen: ze leest en schrijft symbolen op een band, één cel tegelijk, volgens een vaste tabel met regels. Die machine bleek het begrip berekening zelf te definiëren, en ze liet zien dat sommige vragen door geen enkele computer ooit beantwoord kunnen worden.

Een band met cellen vol enen en lege cellen, met boven één cel een lees-schrijfkop die met zijn toestand gelabeld is
Een band met cellen vol enen en lege cellen, met boven één cel een lees-schrijfkop die met zijn toestand gelabeld is

De vraag van Turing

In 1928 vroeg David Hilbert of er een mechanische procedure bestaat die voor elke wiskundige bewering beslist of ze bewezen kan worden: het Entscheidungsproblem. Om die vraag te beantwoorden moest iemand precies zeggen wat een mechanische procedure is. In zijn artikel On Computable Numbers uit 1936 stelde Turing zich een klerk voor die met potlood en papier werkt, en hij bracht dat werk terug tot de kleinst mogelijke stappen: naar één symbool kijken, het veranderen, naar een naburig symbool gaan en een beetje onthouden van waar je mee bezig was. Het resultaat was de Turingmachine.

Een Bombe-machine (links) en een portret van Alan Turing (rechts)
Een Bombe-machine (links) en een portret van Alan Turing (rechts)

De machine

Een Turingmachine heeft een band die in cellen is verdeeld, eindeloos in beide richtingen, en elke cel bevat één symbool, meestal een blanco. Een kop staat op één cel en de machine is in een van eindig veel toestanden. Een tabel met regels geeft voor elke toestand en elk symbool dat de kop kan lezen het symbool dat geschreven wordt, de richting waarin de kop beweegt en de volgende toestand. De machine past per stap één regel toe. Wanneer ze een stoptoestand bereikt, stopt ze, en wat er dan nog op de band staat, is haar antwoord.

Programma's als regeltabellen

Elke regeltabel is een programma. Om 1 op te tellen bij een binair getal loopt de machine naar het rechteruiteinde van het getal en gaat dan naar links, waarbij ze enen in nullen verandert tot ze een 0 of een lege cel vindt, die ze in een 1 verandert. Om te controleren of een woord een palindroom is, wist ze het eerste symbool, onthoudt het in haar toestand, loopt naar het andere uiteinde, controleert of het laatste symbool overeenkomt en herhaalt dat. Lange programma's, zoals een programma dat vermenigvuldigt of sorteert, worden opgebouwd uit dezelfde paar soorten regels.

De universele machine

Turings belangrijkste idee was dat de regeltabel zelf op de band geschreven kan worden. Een universele Turingmachine leest een beschrijving van een willekeurige andere machine en haar invoer, en bootst die machine dan stap voor stap na. Eén vaste machine kan dus elk programma uitvoeren: dat is het principe achter elke computer met een opgeslagen programma, waarin software gewoon data in het geheugen is. Elk systeem dat een universele Turingmachine kan nabootsen, heet Turingvolledig, waaronder elke programmeertaal, Conways Game of Life en de cellulaire automaat Regel 110.

De these van Church–Turing

In hetzelfde jaar beschreef Alonzo Church berekening met zijn lambdacalculus, en de twee definities bleken precies dezelfde functies te berekenen. Dat gold ook voor elk later model, van registermachines tot moderne processors. De these van Church–Turing stelt dat alles wat met een stapsgewijze procedure berekend kan worden, ook door een Turingmachine berekend kan worden. Ze kan niet bewezen worden, omdat “stapsgewijze procedure” een informeel begrip is, maar er is nooit een tegenvoorbeeld gevonden.

Het stopprobleem

Vervolgens liet Turing zien dat sommige vragen geen mechanisch antwoord hebben. Stel dat een machine voor elk programma en elke invoer kon beslissen of dat programma uiteindelijk stopt. Bouw dan een nieuw programma dat deze beslisser naar zichzelf vraagt en vervolgens het tegenovergestelde doet: als het te horen krijgt dat het stopt, gaat het eindeloos door, en als het te horen krijgt dat het eindeloos doorgaat, stopt het. Beide antwoorden zijn fout, dus de beslisser kan niet bestaan. Het stopprobleem is onbeslisbaar, en daarmee ook het Entscheidungsproblem: geen enkel algoritme kan elke wiskundige vraag beslechten.

Bezige bevers

In 1962 maakte Tibor Radó van het stopprobleem een spel: welke van alle machines met n toestanden en de symbolen 0 en 1 die stoppen wanneer ze op een lege band starten, schrijft de meeste enen, en hoeveel stappen kan zo'n machine doen? Deze getallen, de waarden van de bezige bevers, groeien sneller dan elke berekenbare functie, want een manier om ze te berekenen zou het stopprobleem oplossen. De bekende waarden zijn 6, 21 en 107 stappen voor twee, drie en vier toestanden; voor vijf toestanden doet de kampioen van Heiner Marxen en Jürgen Buntrock 47.176.870 stappen, een waarde die in 2024 bewezen werd door de online samenwerking bbchallenge met een door een computer gecontroleerd bewijs. Voor zes toestanden zijn machines bekend die meer stappen doen dan in gewone notatie opgeschreven kan worden.

Ontdek het zelf

Open de Turingmachine-simulator om acht kant-en-klare programma's uit te voeren of je eigen programma te schrijven. Volg de kop stap voor stap en zie welke regel wordt toegepast, kijk naar de teller die nooit stopt, controleer palindromen en laat de bezige bevers lopen: de 107 stappen van de kampioen met vier toestanden passen in het diagram, en de 47 miljoen stappen van de kampioen met vijf toestanden duren op de hoogste snelheid een paar seconden.

Veelgestelde vragen

Is de Turingmachine ooit gebouwd?

Niet zoals Turing haar beschreef, want haar band is eindeloos, maar het idee werd al snel gevolgd door echte computers met een opgeslagen programma, die Turing na de Tweede Wereldoorlog zelf mee hielp ontwerpen. Hobbyisten hebben sindsdien werkende modellen gebouwd van hout, van LEGO en zelfs in de Game of Life, allemaal met een eindige band, wat genoeg is voor elke berekening die eindigt.

Wat is het verschil tussen de stappenaantallen 14 en 21 bij drie toestanden?

Er zijn twee vragen over bezige bevers: de meeste geschreven enen en de meeste gezette stappen. Bij drie toestanden schrijft de machine in de simulator het maximum van zes enen in 14 stappen, terwijl een andere machine met drie toestanden het maximum van 21 stappen doet, maar slechts vijf enen achterlaat. Bij twee, vier en vijf toestanden wint één machine allebei.

Betekent Turingvolledig krachtig?

Het betekent dat iets alles kan berekenen wat berekenbaar is, met genoeg tijd en geheugen, en dat zegt niets over snelheid. Een Turingmachine heeft veel stappen nodig voor eenvoudige rekenkunde, en sommige systemen zijn bijna per ongeluk Turingvolledig, zoals kaartspellen, spreadsheetformules en redstone in Minecraft.

Waarom kan een computer niet gewoon een programma uitvoeren om te zien of het stopt?

Door het uit te voeren zie je dat een programma stopt, als het dat doet, maar als het nog niet gestopt is, kun je niet weten of het nooit zal stoppen of gewoon meer tijd nodig heeft. Turings bewijs laat zien dat geen slimmere methode voor elk programma werkt, al kan de vraag voor veel afzonderlijke programma's wel beantwoord worden.

Klaar om het te proberen?

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

Open de Turingmachine-simulator