Im Jahr 1936 veröffentlichte ein 24-jähriger Cambridge-Mathematiker namens Alan Turing eine Arbeit mit dem Titel On Computable Numbers. Um eine Frage zu beantworten, die David Hilbert über die Grundlagen der Mathematik gestellt hatte, tat Turing etwas, das niemand zuvor getan hatte: er gab eine präzise mathematische Definition dafür, was es heißt, irgendetwas zu berechnen. Das Modell — ein unendliches Papierband, ein beweglicher Lesekopf, eine endliche Regeltabelle — war bewusst karg. Es war auch hinreichend. Jede Berechnung, die irgendeine physische Maschine je ausführen könnte, ließe sich grundsätzlich von einer Turing-Maschine ausführen. Die begriffliche Maschine, die dem Digitalzeitalter zugrunde liegen sollte, wurde in einer Arbeit skizziert, die vielleicht zwei Dutzend Leute gelesen haben.
Turings Arbeit bewies drei Resultate von dauerhafter Bedeutung. Erstens die universelle Turing-Maschine: eine einzelne Turing-Maschine kann jede andere Turing-Maschine simulieren, sofern ihr deren Beschreibung als Eingabe vorliegt. Hardware und Software wurden trennbar — eine Maschine plus ein Programm. Das ist die Kernabstraktion jedes modernen Computers. Zweitens das Halteproblem: es gibt keinen Algorithmus, der für ein beliebiges Programm samt Eingabe entscheiden könnte, ob das Programm anhält oder ewig weiterläuft. Der Beweis stützt sich auf ein Diagonalargument — dem Geist nach mit Gödels Unvollständigkeitsbeweis identisch — und setzt eine harte Grenze dafür, was ein Berechnungssystem über sich selbst entscheiden kann. Drittens die Church-Turing-These (gemeinsam mit Alonzo Church, der unabhängig zum Lambda-Kalkül gelangt war): jede Funktion, die sich überhaupt effektiv berechnen lässt, lässt sich auch von einer Turing-Maschine berechnen. Die These ist kein Theorem (effektive Berechnung ist nicht formal definiert), hat aber seit nahezu einem Jahrhundert allen versuchten Gegenbeispielen standgehalten, Quantencomputer eingeschlossen.
Jeder Computer ist eine Turing-Maschine — physisch aufwendiger, im Speicher endlich, weit schneller, doch begrifflich identisch. Die Komplexitätstheorie (P gegen NP und Verwandtes) ruht auf Turings Gerüst. Die gegenwärtige Debatte, ob sich künstliche allgemeine Intelligenz auf klassischer Hardware umsetzen lässt, ist technisch die Frage, ob menschliche Kognition Turing-berechenbar ist — die meisten KI-Forscher nehmen an, dass sie es ist, und die empirische Leistung großer Transformer-Modelle (Abkömmlinge Attention-basierter Architekturen, die auf Turing-berechenbarer Hardware laufen) hat diese Annahme bislang gestützt. Turing selbst wurde 1952 wegen Homosexualität strafrechtlich verfolgt und starb 1954 mit einundvierzig Jahren an Zyanid.