Über berechenbare Zahlen mit einer Anwendung auf das Entscheidungsproblem (On Computable Numbers, with an Application to the Entscheidungsproblem)

Einführung

Turing, ein junger Fellow des King’s College in Cambridge, stieß 1935 in Max Newmans Vorlesungen über die Grundlagen der Mathematik auf das Problem: Hilbert hatte gefragt, ob es ein mechanisches Verfahren gibt, das von jeder logischen Formel entscheidet, ob sie beweisbar ist. Die London Mathematical Society erhielt den Aufsatz im Mai 1936; er erschien 1936–37 in ihren Proceedings. Turing zerlegt, was ein Mensch tut, der nach einer Regel rechnet, und führt es auf eine Maschine mit endlich vielen Zuständen zurück, die auf einem unbegrenzten Band liest, schreibt und sich bewegt; „berechenbare Zahlen“ sind die reellen Zahlen, deren Dezimalstellen eine solche Maschine ausschreiben kann. Er zeigt, dass eine einzige universelle Maschine jede andere nachahmen kann, wenn sie deren Beschreibung erhält, und dass keine Maschine von jeder Maschine entscheiden kann, ob sie jemals ein bestimmtes Zeichen druckt – daraus folgt die verneinende Antwort auf Hilberts Frage. Alonzo Church hatte dieselbe Antwort kurz zuvor mit seinem Lambda-Kalkül veröffentlicht; in einem Anhang bewies Turing, dass beide Begriffe der Berechenbarkeit gleichwertig sind, und ging im Herbst 1936 nach Princeton, wo er 1938 bei Church promovierte.

Verbindungen

Baut auf

• Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I1931 · Kurt Gödel

Aufgegriffen in

• Rechenmaschinen und Intelligenz1950 · Alan Turing

Weitere Werke von Alan Turing

• 1950Rechenmaschinen und Intelligenz