Turingmaskiner förklarade

År 1936, innan elektroniska datorer fanns, frågade sig den 24-årige matematikern Alan Turing vad det innebär att en beräkning är mekanisk. Hans svar var en tänkt maskin så enkel att den knappast kunde göra mindre: den läser och skriver symboler på ett band, en cell i taget, enligt en fast tabell med regler. Den maskinen visade sig definiera själva begreppet beräkning, och den visade att vissa frågor aldrig kan besvaras av någon dator alls.

Ett band av celler med ettor och tomma celler och ett läs- och skrivhuvud ovanför en cell, märkt med sitt tillstånd
Ett band av celler med ettor och tomma celler och ett läs- och skrivhuvud ovanför en cell, märkt med sitt tillstånd

Turings fråga

År 1928 frågade David Hilbert om det finns en mekanisk procedur som för varje matematiskt påstående avgör om det kan bevisas: Entscheidungsproblem. För att besvara frågan måste någon säga exakt vad en mekanisk procedur är. I sin artikel On Computable Numbers från 1936 föreställde sig Turing en kontorist som arbetar med penna och papper och skalade ned arbetet till dess minsta steg: titta på en symbol, ändra den, flytta till en grannsymbol och komma ihåg lite om vad man höll på med. Resultatet blev Turingmaskinen.

En Bombe-maskin (till vänster) och ett porträtt av Alan Turing (till höger)
En Bombe-maskin (till vänster) och ett porträtt av Alan Turing (till höger)

Maskinen

En Turingmaskin har ett band uppdelat i celler, oändligt åt båda hållen, där varje cell innehåller en symbol, oftast tom. Ett huvud står på en cell, och maskinen befinner sig i ett av ändligt många tillstånd. En tabell med regler anger, för varje tillstånd och varje symbol som huvudet kan läsa, vilken symbol som ska skrivas, åt vilket håll huvudet ska flytta sig och nästa tillstånd. Maskinen tillämpar en regel per steg. När den går in i ett stopptillstånd stannar den, och det som finns kvar på bandet är dess svar.

Program som regeltabeller

Varje regeltabell är ett program. För att addera 1 till ett binärt tal går maskinen till talets högra ände och flyttar sig sedan åt vänster och gör om ettor till nollor tills den hittar en nolla eller en tom cell, som den gör om till en etta. För att kontrollera om ett ord är ett palindrom raderar den den första symbolen, kommer ihåg den i sitt tillstånd, springer till andra änden och kontrollerar att den sista symbolen stämmer, och upprepar sedan. Långa program, som ett som multiplicerar eller sorterar, byggs av samma få sorters regler.

Den universella maskinen

Turings viktigaste idé var att själva regeltabellen kan skrivas på bandet. En universell Turingmaskin läser en beskrivning av vilken annan maskin som helst och dess indata och härmar den sedan steg för steg. En enda fast maskin kan därför köra varje program: det är principen bakom varje dator med lagrat program, där mjukvara bara är data i minnet. Varje system som kan härma en universell Turingmaskin kallas Turingkomplett, däribland varje programmeringsspråk, Conways Game of Life och den cellulära automaten Regel 110.

Church–Turings tes

Samma år beskrev Alonzo Church beräkning med sin lambdakalkyl, och de två definitionerna visade sig beräkna exakt samma funktioner. Det gjorde även varje senare modell, från registermaskiner till moderna processorer. Church–Turings tes säger att allt som kan beräknas med en steg-för-steg-procedur kan beräknas av en Turingmaskin. Den kan inte bevisas, eftersom ”steg-för-steg-procedur” är ett informellt begrepp, men inget motexempel har någonsin hittats.

Stopproblemet

Sedan visade Turing att vissa frågor saknar mekaniskt svar. Anta att en maskin kunde avgöra, för varje program och varje indata, om programmet till slut stannar. Bygg ett nytt program som frågar denna avgörare om sig självt och sedan gör motsatsen: om det får veta att det stannar, loopar det för evigt, och om det får veta att det loopar, stannar det. Båda svaren är fel, så avgöraren kan inte finnas. Stopproblemet är oavgörbart, och därmed även Entscheidungsproblem: ingen algoritm kan avgöra varje matematisk fråga.

Flitiga bävrar

År 1962 gjorde Tibor Radó stopproblemet till ett spel: bland alla maskiner med n tillstånd och symbolerna 0 och 1 som stannar när de startas på ett tomt band, vilken skriver flest ettor, och hur många steg kan en sådan maskin ta? Dessa tal, värdena för de flitiga bävrarna, växer snabbare än varje beräkningsbar funktion, eftersom ett sätt att beräkna dem skulle lösa stopproblemet. De kända värdena är 6, 21 och 107 steg för två, tre och fyra tillstånd; för fem tillstånd tar Heiner Marxens och Jürgen Buntrocks mästare 47 176 870 steg, ett värde som bevisades 2024 av onlinesamarbetet bbchallenge med ett datorkontrollerat bevis. För sex tillstånd känner man till maskiner som kör fler steg än vad som kan skrivas ned med vanlig notation.

Utforska den

Öppna Turingmaskinsimulatorn för att köra åtta färdiga program eller skriva ett eget. Följ huvudet steg för steg och se vilken regel som används, titta på räknaren som aldrig stannar, kontrollera palindrom och kör de flitiga bävrarna: fyrtillståndsmästarens 107 steg ryms i diagrammet, och femtillståndsmästarens 47 miljoner steg tar några sekunder på högsta hastighet.

Ofta ställda frågor

Byggdes Turingmaskinen någonsin?

Inte så som Turing beskrev den, eftersom dess band är oändligt, men idén följdes snart av verkliga datorer med lagrat program, som Turing själv hjälpte till att konstruera efter andra världskriget. Hobbyister har sedan dess byggt fungerande modeller av trä, av LEGO och till och med i Game of Life, alla med ett ändligt band, vilket räcker för varje beräkning som blir klar.

Vad är skillnaden mellan stegantalen 14 och 21 för tre tillstånd?

Det finns två frågor om flitiga bävrar: flest skrivna ettor och flest tagna steg. För tre tillstånd skriver maskinen i simulatorn det maximala antalet sex ettor på 14 steg, medan en annan maskin med tre tillstånd tar det maximala antalet 21 steg men bara lämnar fem ettor efter sig. För två, fyra och fem tillstånd vinner en och samma maskin båda.

Betyder Turingkomplett kraftfull?

Det betyder att kunna beräkna allt som är beräkningsbart, med tillräckligt med tid och minne, vilket inte säger något om hastighet. En Turingmaskin behöver många steg för enkel aritmetik, och vissa system är Turingkompletta nästan av en slump, som kortspel, kalkylbladsformler och redstone i Minecraft.

Varför kan en dator inte bara köra ett program för att se om det stannar?

Att köra det visar att ett program stannar, om det gör det, men om det inte har stannat än kan du inte veta om det aldrig kommer att göra det eller bara behöver mer tid. Turings bevis visar att ingen smartare metod fungerar för varje program, även om frågan kan besvaras för många enskilda program.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Öppna Turingmaskinsimulatorn