Turings bestående betydelse

När Alan Turing föddes för 100 år sedan, den 23 juni 1912, var en dator ingen sak – det var en person. Datorer, av vilka de flesta var kvinnor, anlitades för att utföra upprepade beräkningar i timmar i sträck. Praktiken daterades tillbaka till 1750-talet, när Alexis-Claude Clairaut rekryterade två andra astronomer för att hjälpa honom att rita omloppsbanan för Halleys komet. Clairauts tillvägagångssätt var att dela upp tiden i segment och, med hjälp av Newtons lagar, beräkna förändringarna av kometens position när den passerade Jupiter och Saturnus. Teamet arbetade i fem månader och upprepade processen om och om igen medan de långsamt ritade upp himlakropparnas förlopp.

Idag kallar vi denna process för dynamisk simulering; Clairauts samtida kallade det en styggelse. De önskade en vetenskap om grundläggande lagar och vackra ekvationer, inte tabeller och taltabeller. Ändå gjorde hans team en nära förutsägelse av Halleys komet perihelium. Under det följande och ett halvt århundradet kom beräkningsmetoder att dominera astronomi och ingenjörskonst.

Den här historien var en del av vårt marsnummer 2012

• Se resten av frågan
• Prenumerera

När Turing började på King's College 1931 hade mänskliga datorer använts för en mängd olika ändamål - och ofta hjälptes de av räknemaskiner. Hålkort användes för att kontrollera vävstolar och tabulera resultaten av den amerikanska folkräkningen. Telefonsamtal kopplades med hjälp av nummer som slogs på en ringsignal och tolkades av serier av 10-stegs reläer. Kassaapparater fanns överallt. En miljonär var inte bara en mycket rik person – det var också en mekanisk räknare som kunde multiplicera och dividera med häpnadsväckande hastighet.

Alla dessa maskiner var i grunden begränsade. De var inte bara långsammare, mindre pålitliga och dramatiskt sämre i minne än dagens datorer. Avgörande var att beräknings- och växlingsmaskinerna på 1930-talet – och de som skulle introduceras under många år framöver – var och en byggd för ett specifikt syfte. Vissa av maskinerna kunde utföra manipulationer med matematik, vissa kunde till och med följa en föränderlig sekvens av instruktioner, men varje maskin hade en ändlig repertoar av användbara operationer. Maskinerna var inte för allmänna ändamål. De var inte programmerbar.

Saker granskade

• Turings katedral: Ursprunget till det digitala universum

  George Dyson
  Pantheon Books, 2012

• När datorer var människor

  David alan Grier
  Princeton University Press, 2005

  
  
  

• Alan Turing: The Enigma

  Andrew Hodges
  Simon & Schuster, 1983

Samtidigt hade matematiken problem.

I början av 1920-talet hade den store tyske matematikern David Hilbert föreslagit att formalisera all matematik i termer av ett litet antal axiom och en uppsättning konsekventa bevis. Hilbert föreställde sig en teknik som kunde användas för att validera godtyckliga matematiska påståenden – att ta ett påstående som x + y = 3 och x – y = 3 och avgöra om det var sant eller falskt. Denna teknik skulle inte förlita sig på insikt eller inspiration från matematikerns sida; den måste vara repeterbar, lärbar och okomplicerad nog att följas av en dator (i Hilberts mening av ordet). Ett sådant system som bevisar påståenden skulle verkligen vara kraftfulla saker, för många aspekter av den fysiska världen kan lätt beskrivas som en uppsättning ekvationer. Om man kunde tillämpa en repeterbar procedur för att ta reda på om ett matematiskt påstående var sant eller falskt, skulle grundläggande sanningar om fysik, kemi, biologi – till och med det mänskliga samhället – inte kunna upptäckas genom experiment i labbet utan av matematiker vid en svart tavla .

Men 1931 presenterade en österrikisk logiker vid namn Kurt Gödel sin förödande ofullständighetsteorem. Den visade att för vilket användbart matematiskt system som helst är det möjligt att skapa påståenden som är sanna men som inte kan bevisas. Sedan kom Turing, som drev den sista insatsen genom Hilberts projekt – och på så sätt satte vägen för framtidens datorer.

Som Turing visade är problemet inte bara att vissa matematiska påståenden är obevisbara; i själva verket kan ingen metod utformas som i alla fall kan avgöra om ett givet påstående är bevisbart eller inte. Det vill säga, alla påståenden på tavlan kan vara sanna, kan vara falska, kan vara obevisbara ... och det är ofta omöjligt att avgöra vilket. Matematiken var i grunden begränsad – inte av det mänskliga sinnet utan av själva matematikens natur.

Det lysande, häpnadsväckande var hur Turing gick till väga för sina bevis. Han uppfann en logisk formalism som beskrev hur en mänsklig dator, lärd att följa en komplex uppsättning matematiska operationer, faktiskt skulle utföra dem. Turing förstod inte hur mänskligt minne fungerade, så han modellerade det som ett långt band som kunde röra sig fram och tillbaka och där symboler kunde skrivas, raderas och läsas. Han visste inte hur mänskligt lärande fungerade, så han modellerade det som en uppsättning regler som människan skulle följa beroende på vilken symbol som för närvarande står framför henne och någon form av inre sinnestillstånd. Turing beskrev processen så exakt i detalj att det inte ens behövdes en mänsklig dator för att utföra den – en maskin kunde göra det istället. Turing kallade denna teoretiska enhet för den automatiska maskinen eller a-maskinen; idag kallar vi det en Turing-maskin.

I en tidning från 1936 visade Turing att a-maskinen kunde lösa alla datorproblem som kan beskrivas som en sekvens av matematiska steg. Dessutom visade han att en a-maskin kunde simulera en annan a-maskin. Det som gav a-maskinen denna kraft var att dess band kunde lagra både data och instruktioner. Med vetenskapshistorikern George Dysons ord innehöll bandet båda siffrorna som betyda saker och siffror som do saker.

Turings arbete var omvälvande. Det klargjorde för designers av tidiga elektroniska datorer att beräkningsmaskiner inte behövde ett stort lager av snygga instruktioner eller operationer – allt de behövde var några register som alltid var tillgängliga (sinnetillståndet) och ett minneslager som kunde hålla både data och kod. Konstruktörerna kunde fortsätta i den matematiska säkerheten att maskinerna de byggde skulle kunna lösa alla problem som människorna kunde programmera.

Dessa insikter gav den matematiska formuleringen för dagens digitala datorer, även om det var John von Neumann som tog upp Turings idéer och är krediterad för maskinernas design. Von Neumanns design hade en central kärna som hämtade både instruktioner och data från minnet, utförde matematiska operationer, lagrade resultaten och sedan upprepade. Maskinen kan också fråga innehållet på flera platser i minnet vid behov. Det vi nu kallar von Neumann-arkitekturen är hjärtat i varje mikroprocessor och stordator på planeten. Den är dramatiskt effektivare än a-maskinen, men matematiskt sett är den samma.

För övrigt hjälper denna väsentliga egenskap hos datorer till att förklara varför cybersäkerhet är ett av de mest oroande problemen i modern tid. För det första visade Turing att alla a-maskiner är likvärdiga med varandra, vilket är det som gör det möjligt för en angripare att ta över en måldator och få den att köra ett program som angriparen själv väljer. Dessutom, eftersom det inte alltid är möjligt att urskilja vad som kan bevisas, kan en Turing-maskin inte – oavsett hur mycket minne, hastighet eller tid den har – utvärdera en annan Turing-maskins design och på ett tillförlitligt sätt avgöra om den andra maskinen, när den ges eller inte, någon indata kommer någonsin att avsluta sina beräkningar. Detta gör perfekt virusdetektering omöjlig. Det är omöjligt för ett program att utvärdera en tidigare osynlig mjukvara och avgöra om den är skadlig utan att faktiskt köra den. Programmet kan vara godartat. Eller det kan köras i flera år innan det torkar användarens filer. Det finns inget sätt att veta säkert utan att köra programmet.

1938 började Turing arbeta med den brittiska regeringen och hjälpte till slut med att designa en serie maskiner för att knäcka de koder som användes av tyskarna under andra världskriget. Den bästa källan till den historien är Andrew Hodges biografi Alan Turing: The Enigma. Tyvärr avklassificerades inte vissa detaljer om Turings krigstidsarbete förrän 2000, 17 år efter Hodges bok (och nästan 50 år efter att Turing begick självmord). Som ett resultat har hans fullständiga bidrag inte blivit väl berättade.

Många datorhistorier ger intrycket att det var en enkel uppsättning tekniska beslut att använda hålkort, sedan reläer, sedan rör och slutligen transistorer för att bygga datorer. Men det var det inte. Maskiner för allmänt bruk krävde Turings grundläggande insikt om att data och kod kan representeras på samma sätt. Och tänk på att alla dagens datorer utvecklades med hjälp av långsammare datorer, som i sin tur designades med långsammare datorer fortfarande. Om Turing inte hade gjort sin upptäckt när han gjorde det, kan datorrevolutionen ha försenats med årtionden.

BARN medverkande redaktör Simson L. Garfinkel är docent i datavetenskap vid Naval Postgraduate School. Hans åsikter representerar inte den officiella politiken för USA:s regering eller försvarsdepartementet.

Dölj