Den viktigaste maskinen som aldrig byggdes

Beräkning är ett bekant begrepp som de flesta av oss förstår intuitivt. Ta funktionen f(x) = x + 3. När x är tre, f(3) = 3 + 3. Sex. Lätt. Det verkar uppenbart att denna funktion är beräkningsbar. Men vissa funktioner är inte så enkla, och det är inte så lätt att avgöra om de kan beräknas, vilket innebär att de kanske aldrig ger oss ett slutgiltigt svar.

1928 föreslog de tyska matematikerna David Hilbert och Wilhelm Ackermann en fråga som kallas avgörbarhetsproblemet ("beslutsproblem"). Med tiden skulle deras fråga leda till en formell definition av beräkningsbarhet, en som gjorde det möjligt för matematiker att svara på en mängd nya problem och som lade grunden för teoretisk datavetenskap.

Definitionen kom från en 23-årig student vid namn Alan Turing, som 1936 skrev ett brytningspapper som inte bara formaliserade begreppet beräkning, utan också visade sig vara en grundläggande fråga inom matematiken och skapade den intellektuella grunden för uppfinningen av den elektroniska datorn. Turings stora insikt var att ge ett konkret svar på beräkningsfrågan i form av en abstrakt maskin, senare kallad Turing-maskinen av hans doktorandrådgivare, Alonzo Church. Det är abstrakt eftersom det inte existerar (och kan inte) fysiskt existera som en påtaglig enhet. Istället är det en konceptuell beräkningsmodell: Om maskinen kan beräkna en funktion är funktionen beräkningsbar.

Så här fungerar det. En Turing-maskin kan läsa och ändra symboler på ett oändligt långt band, enligt en tabell med regler. Bandet består av "celler", som var och en kan lagra exakt en symbol, och maskinen läser och skriver om cellernas innehåll med ett tejphuvud. Varje regel i tabellen bestämmer vad maskinen ska göra baserat på både dess nuvarande tillstånd och symbolen den läser. Maskinen kan gå in i ett slutligt tillstånd ("acceptera tillstånd" eller "avvisa tillstånd") då den stannar, accepterar eller avvisar inmatningen. Eller så hamnar den i en oändlig slinga och fortsätter att läsa bandet för alltid.

Det bästa sättet att förstå en Turing-maskin är att överväga ett enkelt exempel. Låt oss föreställa oss en som är utformad för att berätta för oss om en given ingång är talet noll. Vi kommer att använda inmatningsnumret 0001 tillsammans med tomma symboler (#), så "#0001#" är den relevanta delen av vårt band.

Maskinen startar i initialtillståndet, som vi kallar q0. Den läser cellen längst till vänster på vårt band och hittar ett tomt utrymme. Reglerna säger: "När i tillstånd q0, om symbolen är #, lämna den som den är utan modifiering, flytta en cell till höger och ändra maskinens tillstånd till q1." Efter detta steg är maskinen i tillstånd q1 och dess huvud läser den andra symbolen, 0.

Nu letar vi efter en regel som gäller för dessa förhållanden. Vi hittar en som säger, "Fortsätt i tillstånd q1 och flytta huvudet en cell åt höger." Detta lämnar oss i samma position (i tillstånd q1, läser "0"), så vi fortsätter att flytta till höger tills huvudet slutligen läser en annan siffra, 1:an.

När vi konsulterar tabellen igen hittar vi en ny regel: "Om vi ​​stöter på en 1, övergång till q2, vilket är ett "avvisande" tillstånd." Maskinen stannar och svarar "Nej" på den ursprungliga frågan, "Är '0001' noll?"

Om istället inmatningen är "#0000#", kommer maskinen att stöta på ett # efter alla dessa nollor. När vi konsulterar tabellen hittar vi en regel som säger att detta betyder att maskinen går in i tillstånd q3, ett "acceptera" tillstånd. Nu svarar maskinen "Ja" på frågan "Är '0000' noll?"

Med sin abstrakta maskin etablerade Turing en beräkningsmodell för att svara på Entscheidungsproblemet, som formellt frågar: Givet en uppsättning matematiska axiom, finns det en mekanisk process - en uppsättning instruktioner, som vi idag skulle kalla en algoritm - som alltid kan avgöra om ett givet påstående är sant?

Säg att vi vill hitta en algoritm som kan berätta om en viss schackposition är möjlig. Här är axiomen schackreglerna som styr lagliga drag. Kan vi följa en ändlig steg-för-steg-sekvens av procedurer för att komma fram till den positionen? Även om vissa positioner kan ta längre tid än vår livstid att analysera – en algoritm kan generera alla möjliga positioner och jämföra var och en av dem med indata – finns sådana algoritmer i schackspelet. Som ett resultat säger vi att schack är "avgörbart".

Men 1936 bevisade Church och Turing – med olika metoder – oberoende att det inte finns något generellt sätt att lösa varje instans av Entscheidungsproblemet. Till exempel är vissa spel, som John Conways Game of Life, oavgjorda: Ingen algoritm kan avgöra om ett visst mönster kommer att visas från ett initialt mönster.

Turing visade att en funktion är beräkningsbar om det finns en algoritm som kan utföra den önskade uppgiften. Samtidigt visade han att en algoritm är en process som kan definieras av en Turing-maskin. Därför är en beräkningsbar funktion en funktion som har en Turing-maskin för att beräkna den. Det här kan tyckas vara ett omständligt sätt att definiera beräkningsbarhet, men det är det bästa vi har. "Det är inte som att du har ett val att definiera det på något annat sätt," sa Michael Sipser, en teoretisk datavetare vid Massachusetts Institute of Technology. "Jag tror att det är allmänt accepterat att Church-Turing-avhandlingen säger att den informella föreställningen om algoritm motsvarar vad varje "rimlig" beräkningsmodell kan göra." Andra matematiker har kommit på olika beräkningsmodeller som ser ganska olika ut på ytan men som faktiskt är likvärdiga: De kan göra vilken beräkning som helst som Turing-maskiner kan göra, och vice versa.

Bara några år efter att Kurt Gödel hade bevisat att matematik var det Ofullständig, Church och Turing visade med detta arbete att vissa problem i matematik är oavgjorda - ingen algoritm, hur sofistikerad den än är, kan säga oss om svaret är ja eller nej. Båda var förödande slag för Hilbert, som hade hoppats att matematiken skulle ha snygga, idealiserade svar. Men det är kanske lika bra: Om det fanns en generell lösning på Entscheidungsproblemet skulle det innebära att alla problem i matematik kunde reduceras till enkla mekaniska beräkningar.

Utöver att svara på dessa grundläggande frågor ledde Turings maskin också direkt till utvecklingen av moderna datorer, genom en variant som kallas den universella Turing-maskinen. Detta är en speciell typ av Turing-maskin som kan simulera vilken annan Turing-maskin som helst på vilken ingång som helst. Den kan läsa en beskrivning av andra Turing-maskiner (deras regler och inmatningsband) och simulera deras beteenden på sitt eget inmatningsband, vilket ger samma utdata som den simulerade maskinen skulle producera, precis som dagens datorer kan läsa vilket program som helst och köra det. 1945 föreslog John von Neumann en datorarkitektur - kallad von Neumann-arkitekturen - som gjorde det universella Turing-maskinkonceptet möjligt i en verklig maskin.

När Sanjeev Arora, en teoretisk datavetare vid Princeton University, lär ut detta koncept, han betonar en bredare filosofisk bild. "Det finns två begrepp om "universell", sa han. "En föreställning om det universella är att den kan köra vilken annan Turing-maskin som helst. Men den andra, större uppfattningen om "universell" är att den kan köra vilken beräkning som helst som du kommer att komma på i universum." I den klassiska fysikens värld kan vilken fysisk process som helst modelleras eller simuleras med hjälp av algoritmer, som i sin tur kan simuleras av en Turing-maskin.

En annan anmärkningsvärd och allt mer användbar variant är den probabilistiska Turing-maskinen. Till skillnad från en vanlig Turing-maskin - som har en väldefinierad reaktion på varje ingång - kan en probabilistisk Turing-maskin ha flera reaktioner baserat på sannolikheter. Detta innebär att det kan ge olika resultat för samma input vid olika tidpunkter. Överraskande, den här typen av probabilistisk strategi kan vara mer effektivt än ett rent deterministiskt tillvägagångssätt för vissa problem. Idéer från probabilistiska Turing-maskiner har visat sig vara praktiskt användbara inom områden som kryptografi, optimering och maskininlärning.

Dessa abstrakta maskiner är kanske det bästa beviset på att att ställa grundläggande frågor kan vara bland det mest användbara en vetenskapsman kan göra.