Den vigtigste maskine, der aldrig blev bygget

Beregning er et velkendt begreb, som de fleste af os forstår intuitivt. Tag funktionen f(x) = x + 3. Hvornår x er tre, f(3) = 3 + 3. Seks. Let. Det virker indlysende, at denne funktion er beregnelig. Men nogle funktioner er ikke så enkle, og det er ikke så let at afgøre, om de kan beregnes, hvilket betyder, at de måske aldrig giver os et endeligt svar.

I 1928 foreslog de tyske matematikere David Hilbert og Wilhelm Ackermann et spørgsmål kaldet beslutningsproblem ("beslutningsproblem"). Med tiden ville deres spørgsmål føre til en formel definition af beregnelighed, en der gjorde det muligt for matematikere at besvare et væld af nye problemer og lagde grundlaget for teoretisk datalogi.

Definitionen kom fra en 23-årig studerende ved navn Alan Turing, som i 1936 skrev et banebrydende papir som ikke kun formaliserede begrebet beregning, men også viste sig at være et grundlæggende spørgsmål i matematik og skabte det intellektuelle grundlag for opfindelsen af ​​den elektroniske computer. Turings store indsigt var at give et konkret svar på beregningsspørgsmålet i form af en abstrakt maskine, som senere blev kaldt Turing-maskinen af ​​hans doktorgradsrådgiver, Alonzo Church. Det er abstrakt, fordi det ikke fysisk eksisterer (og ikke kan) som en håndgribelig enhed. I stedet er det en konceptuel beregningsmodel: Hvis maskinen kan beregne en funktion, så kan funktionen beregnes.

Sådan fungerer det. En Turing-maskine kan læse og ændre symboler på et uendeligt langt bånd, som dikteret af en tabel med regler. Båndet består af "celler", som hver kan gemme præcis ét symbol, og maskinen læser og omskriver cellernes indhold med et båndhoved. Hver regel i tabellen bestemmer, hvad maskinen skal gøre baseret på både dens nuværende tilstand og det symbol, den læser. Maskinen kan gå ind i en endelig tilstand ("accepter tilstand" eller "afvis tilstand"), hvorefter den standser, accepterer eller afviser input. Eller det falder ind i en uendelig løkke og fortsætter med at læse båndet for evigt.

Den bedste måde at forstå en Turing-maskine på er at overveje et simpelt eksempel. Lad os forestille os en, der er designet til at fortælle os, om en given input er tallet nul. Vi bruger inputnummeret 0001 ledsaget af tomme symboler (#), så "#0001#" er den relevante del af vores bånd.

Maskinen starter i den oprindelige tilstand, som vi kalder q0. Den læser cellen længst til venstre på vores bånd og finder et tomt felt. Reglerne siger: "Når du er i tilstand q0, hvis symbolet er #, lad det være som det er uden ændringer, flyt en celle til højre og skift maskinens tilstand til q1." Efter dette trin er maskinen i tilstand q1, og dens hoved læser det andet symbol, 0.

Nu leder vi efter en regel, der gælder for disse forhold. Vi finder en, der siger: "Forbliv i tilstand q1 og flyt hovedet en celle til højre." Dette efterlader os i samme position (i tilstand q1, læser "0"), så vi bliver ved med at bevæge os til højre, indtil hovedet til sidst læser et andet tal, 1.

Når vi konsulterer tabellen igen, finder vi en ny regel: "Hvis vi støder på en 1, overgang til q2, som er en 'afvis' tilstand." Maskinen stopper og svarer "Nej" til det oprindelige spørgsmål: "Er '0001' nul?"

Hvis input i stedet er "#0000#", vil maskinen støde på et # efter alle disse nuller. Når vi konsulterer tabellen, finder vi en regel, der siger, at dette betyder, at maskinen går ind i tilstanden q3, en "accepter"-tilstand. Nu svarer maskinen "Ja" til spørgsmålet "Er '0000' nul?"

Med sin abstrakte maskine etablerede Turing en beregningsmodel for at besvare Entscheidungsproblemet, som formelt spørger: Givet et sæt matematiske aksiomer, er der en mekanisk proces - et sæt instruktioner, som vi i dag vil kalde en algoritme - som altid kan afgøre, om et givet udsagn er sandt?

Sig, at vi vil finde en algoritme, der kan fortælle os, om en bestemt skakposition er mulig. Her er aksiomerne skakreglerne, der styrer lovlige træk. Kan vi følge en begrænset trin-for-trin sekvens af procedurer for at nå frem til den position? Selvom nogle positioner kan tage længere tid end vores levetid at analysere - en algoritme kan generere alle mulige positioner og sammenligne hver af dem med inputtet - findes sådanne algoritmer i skakspillet. Som et resultat siger vi, at skak er "afgørligt".

Men i 1936 beviste Church og Turing - ved hjælp af forskellige metoder - uafhængigt, at der ikke er nogen generel måde at løse alle tilfælde af Entscheidungsproblemet på. For eksempel er nogle spil, såsom John Conways Game of Life, uafgørlige: Ingen algoritme kan afgøre, om et bestemt mønster vil fremkomme fra et indledende mønster.

Turing viste, at en funktion kan beregnes, hvis der findes en algoritme, der kan udføre den ønskede opgave. Samtidig viste han, at en algoritme er en proces, der kan defineres af en Turing-maskine. Derfor er en beregnelig funktion en funktion, der har en Turing-maskine til at beregne den. Dette kan virke som en omstændelig måde at definere beregningsevne på, men det er det bedste, vi har. "Det er ikke sådan, at du har et valg om at definere det på en anden måde," sagde Michael Sipser, en teoretisk datalog ved Massachusetts Institute of Technology. "Jeg tror, ​​det er almindeligt accepteret, at Church-Turing-afhandlingen siger, at den uformelle forestilling om algoritme svarer til, hvad enhver 'rimelig' beregningsmodel kan gøre." Andre matematikere er kommet med forskellige beregningsmodeller, der ser ganske anderledes ud på overfladen, men som faktisk er ækvivalente: De kan udføre enhver beregning, som Turing-maskiner kan gøre, og omvendt.

Kun få år efter havde Kurt Gödel bevist, at matematik var det ufuldstændig, Church og Turing viste med dette arbejde, at nogle problemer i matematik er uafklarelige - ingen algoritme, uanset hvor sofistikeret den end er, kan fortælle os, om svaret er ja eller nej. Begge var ødelæggende slag for Hilbert, som havde håbet, at matematik ville have ryddelige, idealiserede svar. Men det er måske lige så godt: Hvis der fandtes en generel løsning på Entscheidungsproblemet, ville det betyde, at alle problemer i matematik kunne reduceres til simple mekaniske beregninger.

Ud over at besvare disse grundlæggende spørgsmål førte Turings maskine også direkte til udviklingen af ​​moderne computere gennem en variant kendt som den universelle Turing-maskine. Dette er en speciel slags Turing-maskine, der kan simulere enhver anden Turing-maskine på ethvert input. Den kan læse en beskrivelse af andre Turing-maskiner (deres regler og inputbånd) og simulere deres adfærd på sit eget inputbånd, hvilket producerer det samme output, som den simulerede maskine ville producere, ligesom nutidens computere kan læse ethvert program og udføre det. I 1945 foreslog John von Neumann en computerarkitektur - kaldet von Neumann-arkitekturen - der gjorde det universelle Turing-maskinkoncept muligt i en virkelig maskine.

Hvornår Sanjeev Arora, en teoretisk datalog ved Princeton University, underviser i dette koncept, han understreger et bredere filosofisk billede. "Der er to begreber om 'universelt'," sagde han. "En forestilling om det universelle er, at den kan køre enhver anden Turing-maskine. Men den anden, større forestilling om 'universel' er, at den kan køre enhver beregning, som du vil finde på i universet." I den klassiske fysiks verden kan enhver fysisk proces modelleres eller simuleres ved hjælp af algoritmer, som igen kan simuleres af en Turing-maskine.

En anden bemærkelsesværdig og stadig mere anvendelig variant er den probabilistiske Turing-maskine. I modsætning til en almindelig Turing-maskine - som har en veldefineret reaktion på hvert input - kan en probabilistisk Turing-maskine have flere reaktioner baseret på sandsynligheder. Det betyder, at det kan give forskellige resultater for det samme input på forskellige tidspunkter. Overraskende nok denne slags probabilistisk strategi kan være mere effektiv end en rent deterministisk tilgang til visse problemer. Idéer fra probabilistiske Turing-maskiner har vist sig at være praktisk anvendelige inden for områder som kryptografi, optimering og maskinlæring.

Disse abstrakte maskiner er måske det bedste bevis på, at det at stille grundlæggende spørgsmål kan være blandt de mest nyttige ting, en videnskabsmand kan gøre.