Turingmaskiner forklaret

I 1936, før elektroniske computere fandtes, spurgte den 24-årige matematiker Alan Turing, hvad det vil sige, at en beregning er mekanisk. Hans svar var en tænkt maskine, så enkel at den næppe kunne gøre mindre: den læser og skriver symboler på et bånd, én celle ad gangen, efter en fast tabel med regler. Den maskine viste sig at definere selve begrebet beregning, og den viste, at nogle spørgsmål aldrig kan besvares af nogen computer overhovedet.

Et bånd af celler med ettaller og tomme celler og et læse-skrive-hoved over én celle, mærket med sin tilstand
Et bånd af celler med ettaller og tomme celler og et læse-skrive-hoved over én celle, mærket med sin tilstand

Turings spørgsmål

I 1928 spurgte David Hilbert, om der findes en mekanisk procedure, der for ethvert matematisk udsagn afgør, om det kan bevises: Entscheidungsproblem. For at besvare det måtte nogen sige præcis, hvad en mekanisk procedure er. I sin artikel On Computable Numbers fra 1936 forestillede Turing sig en kontorist, der arbejder med blyant og papir, og skar arbejdet ned til dets mindste trin: se på ét symbol, ændre det, flytte til et nabosymbol og huske lidt om, hvad man var i gang med. Resultatet var Turingmaskinen.

En Bombe-maskine (til venstre) og et portræt af Alan Turing (til højre)
En Bombe-maskine (til venstre) og et portræt af Alan Turing (til højre)

Maskinen

En Turingmaskine har et bånd, der er delt i celler og endeløst i begge retninger, og hver celle indeholder ét symbol, som regel blankt. Et hoved står på én celle, og maskinen er i én af endeligt mange tilstande. En tabel med regler angiver for hver tilstand og hvert symbol, hovedet kan læse, hvilket symbol der skal skrives, hvilken retning hovedet skal flytte sig i, og den næste tilstand. Maskinen anvender én regel pr. trin. Når den går ind i en stoptilstand, standser den, og det, der står tilbage på båndet, er dens svar.

Programmer som regeltabeller

Hver regeltabel er et program. For at lægge 1 til et binært tal går maskinen til højre ende af tallet og bevæger sig derefter mod venstre, mens den gør ettaller til nuller, indtil den finder et 0 eller en tom celle, som den gør til et 1. For at tjekke, om et ord er et palindrom, sletter den det første symbol, husker det i sin tilstand, løber til den anden ende, tjekker, at det sidste symbol passer, og gentager så. Lange programmer, som et, der ganger eller sorterer, bygges af de samme få slags regler.

Den universelle maskine

Turings vigtigste idé var, at selve regeltabellen kan skrives på båndet. En universel Turingmaskine læser en beskrivelse af en hvilken som helst anden maskine og dens input og efterligner den derefter trin for trin. Én fast maskine kan derfor køre ethvert program: det er princippet bag enhver computer med lagret program, hvor software blot er data i hukommelsen. Ethvert system, der kan efterligne en universel Turingmaskine, kaldes Turing-komplet, herunder ethvert programmeringssprog, Conways Game of Life og den cellulære automat Regel 110.

Church–Turing-tesen

Samme år beskrev Alonzo Church beregning med sin lambdakalkyle, og de to definitioner viste sig at beregne præcis de samme funktioner. Det samme gjorde enhver senere model, fra registermaskiner til moderne processorer. Church–Turing-tesen siger, at alt, hvad der kan beregnes ved en trinvis procedure, kan beregnes af en Turingmaskine. Den kan ikke bevises, fordi »trinvis procedure« er et uformelt begreb, men der er aldrig fundet et modeksempel.

Stopproblemet

Derefter viste Turing, at nogle spørgsmål ikke har noget mekanisk svar. Antag, at en maskine kunne afgøre for ethvert program og ethvert input, om programmet til sidst standser. Byg et nyt program, der spørger denne afgører om sig selv og derefter gør det modsatte: hvis det får at vide, at det standser, kører det i ring for evigt, og hvis det får at vide, at det kører i ring, standser det. Begge svar er forkerte, så afgøreren kan ikke findes. Stopproblemet er uafgørligt, og dermed også Entscheidungsproblem: ingen algoritme kan afgøre ethvert matematisk spørgsmål.

Travle bævere

I 1962 gjorde Tibor Radó stopproblemet til en leg: blandt alle maskiner med n tilstande og symbolerne 0 og 1, der standser, når de startes på et tomt bånd, hvilken skriver så flest ettaller, og hvor mange trin kan sådan en maskine tage? Disse tal, værdierne for de travle bævere, vokser hurtigere end enhver beregnelig funktion, fordi en måde at beregne dem på ville løse stopproblemet. De kendte værdier er 6, 21 og 107 trin for to, tre og fire tilstande; for fem tilstande tager Heiner Marxens og Jürgen Buntrocks mester 47.176.870 trin, en værdi, der blev bevist i 2024 af onlinesamarbejdet bbchallenge med et computerkontrolleret bevis. For seks tilstande kendes maskiner, der kører flere trin, end der kan skrives ned med almindelig notation.

Udforsk det

Åbn Turingmaskine-simulatoren for at køre otte færdige programmer eller skrive dit eget. Følg hovedet trin for trin, og se, hvilken regel der bruges, se tælleren, der aldrig standser, tjek palindromer, og kør de travle bævere: de 107 trin for mesteren med fire tilstande kan være i diagrammet, og de 47 millioner trin for mesteren med fem tilstande tager et par sekunder ved den højeste hastighed.

Ofte stillede spørgsmål

Blev Turingmaskinen nogensinde bygget?

Ikke som Turing beskrev den, da dens bånd er endeløst, men idéen blev snart fulgt af rigtige computere med lagret program, som Turing selv var med til at designe efter Anden Verdenskrig. Hobbyfolk har siden bygget fungerende modeller af træ, af LEGO og endda i Game of Life, alle med et endeligt bånd, hvilket er nok til enhver beregning, der bliver færdig.

Hvad er forskellen på trintallene 14 og 21 for tre tilstande?

Der er to spørgsmål om travle bævere: flest skrevne ettaller og flest tagne trin. For tre tilstande skriver maskinen i simulatoren det maksimale antal på seks ettaller på 14 trin, mens en anden maskine med tre tilstande tager det maksimale antal på 21 trin, men kun efterlader fem ettaller. For to, fire og fem tilstande vinder én maskine begge dele.

Betyder Turing-komplet kraftfuld?

Det betyder i stand til at beregne alt, hvad der kan beregnes, med nok tid og hukommelse, og det siger intet om hastighed. En Turingmaskine skal bruge mange trin til simpel aritmetik, og nogle systemer er Turing-komplette næsten ved et tilfælde, som kortspil, regnearksformler og redstone i Minecraft.

Hvorfor kan en computer ikke bare køre et program for at se, om det standser?

Når du kører det, ser du, at et program standser, hvis det gør, men hvis det ikke er standset endnu, kan du ikke vide, om det aldrig vil gøre det eller bare skal bruge mere tid. Turings bevis viser, at ingen smartere metode virker for alle programmer, selv om spørgsmålet kan besvares for mange bestemte programmer.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Åbn Turingmaskine-simulatoren