On Computable Numbers

Voller Titel: On Computable Numbers, with an Application to the Entscheidungsproblem. Turing war 23, reichte den Aufsatz im Mai 1936 ein und veröffentlichte ihn in den Proceedings of the London Mathematical Society. Die Aufgabe war Hilberts Entscheidungsproblem: Gibt es ein mechanisches Verfahren, das entscheidet, ob eine beliebige mathematische Aussage aus den Axiomen folgt? Um das zu beantworten, musste er erst definieren, was „mechanisches Verfahren“ überhaupt heißt – und tat das mit einer gedachten Maschine mit unendlichem Band, Lesekopf und Zustandstabelle.

Alles Weitere folgt aus dieser Definition: eine universelle Maschine, die jede andere simulieren kann, wenn man ihre Beschreibung aufs Band schreibt, der Beweis, dass keine Maschine entscheiden kann, ob eine beliebige Maschine je anhält, und damit ein Nein an Hilbert. Alonzo Church war mit dem Lambda-Kalkül Monate früher zum selben Ergebnis gekommen, was die Veröffentlichung fast kippte – Turing musste einen Anhang ergänzen, der beide Formulierungen als gleichwertig zeigte. Das eigentliche Vermächtnis ist nicht der Beweis, sondern der Seitenhieb auf die universelle Maschine: eine Maschine, deren Programm Daten ist.