Über berechenbare Zahlen
| Das Werk | |
|---|---|
| Deutscher Titel: | Über berechenbare Zahlen |
| Autor(en): | Alan Turing |
| Originaltitel: | On Computable Numbers, with an Application to the Entscheidungsproblem |
| Originalsprache: | englisch |
| Erstveröffentlichung: | 1936 |
| Schlagwörter: | Berechenbarkeit, Maschine, Entscheidung, Zahl |
| Sachgebiete: | Sachbuch, Naturwissenschaft |
| Greifbare Ausgabe | |
| Verlag: | |
| Umfang dieser Ausgabe: | 42 Seiten |
| ISBN: | |
| Verweise | |
Über berechenbare Zahlen (englisch On Computable Numbers, with an Application to the Entscheidungsproblem) ist die 1936 in den Proceedings der London Mathematical Society erschienene Arbeit von Alan Turing. Sie bestimmt, was eine einfache Maschine mit Band und Zustand rechnen kann – und dass Hilberts Entscheidungsproblem keine allgemeine Lösung hat.
Inhalt
Turing ersetzt den unklaren Begriff der wirksamen Vorschrift durch eine Maschine. Endliches Alphabet, endliche Zahl von Zuständen, ein Band, das man nach links und rechts bewegen, lesen und beschreiben kann: Was eine solche Vorrichtung nach endlich vielen Schritten auf das Band schreibt, heißt berechenbar. Die reellen Zahlen, deren Ziffernfolge so entsteht, sind die berechenbaren. Die meisten reellen Zahlen sind es nicht. Turing baut die universelle Maschine, die jede andere simuliert, wenn man ihr deren Beschreibung gibt. Daraus folgt die Unlösbarkeit des Entscheidungsproblems: Es gibt kein Verfahren, das für jede Formel der Prädikatenlogik sagt, ob sie gilt. Die Diagonalisierung, die Cantor gegen das Abzählen der reellen Zahlen führte, kehrt hier gegen die Hoffnung auf ein allgemeines Entscheidungsverfahren.
Die Arbeit ist eine Abhandlung der Logik, kein Manifest des Rechners. Der Rechner, der später auf dem Tisch stand, ist in der universellen Maschine schon gedacht: Programm als Daten auf dem Band. Church hatte denselben Bereich mit dem Lambda-Kalkül bestimmt; Turing liefert die Maschine, die anschaulich macht, was „wirksam“ heißt. Der Ton ist der eines Mathematikers von 1936: Definition, Satz, Beweis, die Anwendung auf Hilbert als Pointe, nicht als Einleitung. Wer nur die spätere Informatik sucht, unterschlägt die Logik. Wer nur Hilbert sucht, unterschlägt, dass hier das Denken an eine Vorrichtung gehängt wird, die jeder mit Papier und Geduld nachahmen kann.
Unsicher bleibt, was die Maschine für den Geist bedeutet. Turing stellt die Frage 1950 in Computing Machinery and Intelligence; 1936 geht es um Zahlen und Entscheidungen. Die beiden Texte gehören zusammen, ohne dasselbe zu sein. Wer die spätere Arbeit ohne diese liest, hat das Imitationsspiel ohne die Härte, was berechenbar heißt. Wer nur 1936 liest, hat die Logik ohne das Gegenüber. Die Strafe, die Turing 1952 traf, steht nicht im Paper. Sie steht in der Biographie dessen, der die Maschine dachte, bevor das Recht ihn als voll gültig dachte.
Einordnung
Die Arbeit hat Berechenbarkeit als das bestimmt, was eine Turingmaschine schafft, und der Informatik das Modell gegeben, das sie noch trägt. Church, Gödel, die Unvollständigkeit: dieselbe Landschaft der dreißiger Jahre. Der Aufsatz von 1950 öffnet dieselbe Maschine auf das Gespräch; 1936 bleibt sie bei den Zahlen. Wer nach dieser Arbeit von berechenbaren Zahlen spricht, spricht Turing – auch dort, wo die Maschinen längst keine Bänder mehr haben.
Wie dieser Artikel entstanden ist: Den Text hat ein KI-Sprachmodell verfasst (Grok 4.6, xAI). Werkauswahl, Ausgabendaten und Redaktion entstanden in Zusammenarbeit mit Denis Diderot; er liest und prüft jeden Artikel auch nach der Veröffentlichung. Hinweise auf Fehler gehören auf die Diskussionsseite und sind willkommen.