Alan Turing (1912 – 1954) var en brittisk matematiker, logiker och kryptograf som av många anses vara datavetenskapens fader. Hans bidrag till att bryta den tyska nazistiska Enigma-koden under andra världskriget ansågs vara avgörande för de allierade krigsinsatserna. Alan Turing formulerade flera idéer som nu ligger till grund för datavetenskap och beräkningsbarhetsteori, såsom idén om en Turing-maskin eller Church-Turing-avhandlingen.
En Turing-maskin är en enkel matematisk konstruktion som kan föreställas som ett inspelningsbart band av oändlig längd kopplat till en mekanisk enhet med läs/skrivförmåga. Enheten kan endast utföra tre åtgärder; läs lite av bandet och returnera resultatet; skriv lite på bandet; eller radera en redan existerande bit. Turings Church-Turing-avhandling, formulerad med Alonzo Church, säger att en sådan Turing-maskin teoretiskt kan beräkna vilken algoritm som helst givet tillräckligt med tid och lagringsutrymme. Det står också att alla praktiska datormodeller måste vara en typ av Turing-maskin. I förlängningen betyder detta att den mänskliga hjärnan kan definieras som en Turing-maskin, eftersom den bearbetar information på det enda sätt som information kan bearbetas; genom att läsa, skriva och manipulera minnesbitar.
Church-Turing-avhandlingen hävdar också att vilken algoritm som helst kan köras på vad som helst som kvalificerar sig som en Turing-maskin. Turing hjälpte till att formulera den ursprungliga definitionen av en algoritm, som är ungefär som följer: 1) en algoritm kommer att bestå av en ändlig uppsättning exakta instruktioner som ska exekveras; 2) vara beräkningsbar i ett ändligt antal steg (ett programs oförmåga att avgöra om det kan köras i ett ändligt antal steg kallas för ”stoppproblemet”); 3) vara beräkningsbar i princip med endast en penna, papper och oändlig tid; 4) kräver ingen bakgrundsinformation för att utföra, det vill säga vara fristående.
Alan Turing utbildades vid Cambridge och Princeton under hela 30-talet. År 1936 publicerade Turing en mycket inflytelserik artikel, On computable numbers, med en tillämpning på Entscheidungsproblemet, som svarade på en öppen fråga som ställdes av Kurt Goedel 1931, som visade att det inte finns något algoritmiskt sätt att avgöra om ett givet första ordningens uttalande i symbolisk logik är universellt giltig. 1938 tog Alan Turing sin doktorsexamen från Princeton under Alonzo Church.
Alan Turing tillbringade sina efterkrigsår med att arbeta på några av de första omprogrammerbara digitala datorerna, och producerade en av de första designerna 1946. Han tog också upp problemet med artificiell intelligens och formulerade Turing-testet, ett test för att avgöra om en maskin är eller inte. förtjänar att kallas medveten och intelligent. I Turing-testet skriver en människa in ord på ett tangentbord för att kommunicera med två gömda personer, en en verklig människa, den andra en AI. Om människan inte kan urskilja vilken kommunikant som är människan och vilken som är AI, sägs AI:n ha klarat Turingtestet. Vissa futurister, som vinnaren av National Medal of Technology Ray Kurzweil, har föreslagit att vi kommer att ha en dator som klarar Turing-testet före 2030.
Alan Turing dog 1954, på grund av ett cyanidspetsade äpple. Hans död sägs vara ett självmord, ett resultat av att han blivit åtalad för homosexualitet och tvingades ta hormoner av regeringen.