I. Das Hauptproblem
Beim Rechnen nach Vorschrift fällt eines auf: Man kann rechnen, ohne zu verstehen.
Wer eine Additionsaufgabe vor sich hat und die Zahlen nach dem schriftlichen Verfahren untereinanderschreibt, kann richtig rechnen, ohne zu wissen, wofür sie stehen. Die Vorschrift steht auf dem Papier. Der Mensch braucht sie nur auszuführen.
Gegen Ende des neunzehnten Jahrhunderts begannen Mathematiker, sich eine weiterreichende Frage zu stellen. Geht das mit allen mathematischen Aufgaben? Gibt es für jede beliebige Formel der Logik erster Stufe eine feste Vorschrift, nach der man in endlich vielen Schritten entscheiden kann, ob sie bei jeder Interpretation gilt?
Gesucht war kein kluger Mensch, der die Aufgabe durchdenkt. Auch jemand, der nichts von ihr versteht, sollte sie nach Vorschrift lösen können.
Eine solche Vorschrift nannte man damals ein Verfahren. Ob es sie gibt, war das, was ein Lehrbuch von 1928 als Hauptproblem der mathematischen Logik bezeichnete.
Es gibt sie nicht. Das wurde 1936 bewiesen. Wer es endgültig beweisen wollte, musste zuvor vollständig bestimmen, was ein Verfahren sein kann. Dazu entwarf er eine Maschine.
Diese Maschine wurde später zum Modell des Computers.
1928 erschien in Berlin ein Lehrbuch: Grundzüge der theoretischen Logik, von David Hilbert und Wilhelm Ackermann. Hilbert war Professor für Mathematik in Göttingen und einer der einflussreichsten Mathematiker seiner Zeit. Ackermann war sein Schüler.
Das Buch stellt eine Aufgabe. Für einen gegebenen logischen Ausdruck soll es ein Verfahren geben, nach dem man in endlich vielen Operationen entscheidet, ob er unter jeder Interpretation gilt oder wenigstens unter einer Interpretation gelten kann.
Auf derselben Seite steht eine Wertung: Das Entscheidungsproblem muss als Hauptproblem der mathematischen Logik bezeichnet werden.
Das ist keine Empfehlung. Es ist eine Festlegung. Das Wort lautet »muss«.
Da steht nicht, die Frage sei interessant oder verdiene nähere Untersuchung. Da steht »Hauptproblem«. Legt eine Disziplin ihren Kern an einer Stelle fest, wird die Stelle zum Maßstab für alle weitere Arbeit. Wer das Problem löst, hat getan, was die Disziplin sich vorgenommen hat. Wird aber bewiesen, dass es nicht lösbar ist, muss die Disziplin ihre Gestalt ändern. 1928 sah das Buch dafür keinen Platz vor. Es war ein Lehrbuch. Was darin steht, sollen die Studenten lernen, nicht bezweifeln. Nimmt ein Lehrbuch eine Frage auf, erklärt es sie damit zu einer ordentlichen Aufgabe. Bei einer ordentlichen Aufgabe geht man davon aus, dass es eine Antwort gibt.
Die Forderung hatte eine Vorgeschichte. Im August 1900 hatte Hilbert in Paris eine Liste von Problemen vorgelegt. Das zehnte verlangt ein Verfahren, um für eine beliebig gegebene Gleichung einer bestimmten Art in endlich vielen Operationen zu entscheiden, ob sie eine ganzzahlige Lösung hat. Das ist enger gefasst als die Frage von 1928, denn es geht um eine bestimmte Klasse arithmetischer Gleichungen. Aber die Wörter sind dieselben: Verfahren, endlich viele Operationen, entscheiden. In achtundzwanzig Jahren nahm die Reichweite zu; die Form der Forderung blieb. Im allgemeinen Teil derselben Rede steht, ein klar gestelltes mathematisches Problem solle eine bestimmte Lösung oder einen Beweis seiner Unlösbarkeit erhalten. Der zweite Teil war damals ein Ausweg. Sechsunddreißig Jahre später war er der Haupteingang.
1917 zählte Hilbert in Zürich die Entscheidbarkeit und die Entscheidbarkeit in endlich vielen Operationen zu den Dingen, die zu untersuchen seien. 1922 stand das Wort Entscheidungsproblem schon im Titel eines Aufsatzes von Heinrich Behmann. Darin heißt es, die Entscheidung über wahr oder falsch solle auf mechanisches Rechnen nach festgelegten Anweisungen zurückgeführt werden. Hier steht schon, was gesucht war: eine Reihe von Anweisungen, denen man ohne Nachdenken folgt. Im Wintersemester 1922/23 hielten Hilbert und Paul Bernays in Göttingen eine Vorlesung über die logischen Grundlagen der Mathematik.
Von 1900 bis 1928 wurde die Forderung immer deutlicher. Eines darin blieb undeutlich.
Was ein Verfahren ist.
Was heißt »Operation« in »endlich vielen Operationen«? Wo endet das Mechanische beim mechanischen Rechnen nach Anweisung? Niemand hatte es definiert. 1928 schien es keiner Definition zu bedürfen. Ein Mathematiker erkannte, ob das, was er vor sich hatte, ein Algorithmus war. Was man erkannte, brauchte man nicht zu definieren.
Will man beweisen, dass etwas nicht geht, lässt sich dieser Schritt nicht umgehen. Man muss vorher alle möglichen Fälle lückenlos erfassen. Gelingt das nicht, darf man nicht behaupten, es gebe die gesuchte Sache nicht, sondern nur, dass man sie noch nicht gefunden hat. Nichtfinden ist kein Beweis. Erst wer alle Formen des Möglichen umzeichnet, kann sagen, was darin nicht vorkommt. So ist Turings Manuskript gebaut: einen möglichst großen Käfig bauen und dann beweisen, dass etwas draußen liegt. Je größer der Käfig ist, desto sicherer liegt dieses Etwas draußen. Der neunte Abschnitt erklärt eigens, warum dieser Käfig alles einfängt, was er soll. Turing geht jede denkbare Lücke einzeln durch, und jedes Mal nimmt er etwas von dem Menschen, der vor einer Rechenaufgabe sitzt.
Achtundzwanzig Jahre lang verlangte man auf der einen Seite ein Verfahren und definierte auf der anderen nicht, was für ein Ding ein Verfahren war. Die Forderung stand; das Geforderte hatte noch keine Gestalt. Der Aufbau griff hier nach draußen, nach etwas, für das ihm selbst der Name fehlte. Was später geschah, wurde erst möglich, weil jemand sich umdrehte und dieses namenlose Ding herstellte.
II. Zwei Tagungen
Königsberg, September 1930. In dieser Woche geschahen zwei Dinge, die später oft als eines erzählt wurden.
Von dem einen heißt es später, es habe eine ganze Disziplin umgeschrieben. Damals sagte keiner der Anwesenden auf der Stelle etwas dazu. Erst als der Aufsatz über ein Jahr später gedruckt war, wurde langsam deutlich, was geschehen war. Im Augenblick, in dem etwas geschieht, hat es oft noch keine erkennbare Gestalt. Die erscheint später auf Papier.
Das erste Ereignis war die Zweite Tagung für Erkenntnislehre der exakten Wissenschaften vom 5. bis zum 7. September; veranstaltet wurde sie von einem Kreis der empirischen Philosophie. Unter Mathematikern gab es mehrere unvereinbare Ansichten darüber, wie die Grundlagen zu legen seien. Am fünften bekam jede Richtung eine Stunde. John von Neumann sprach für die von Hilbert. Am sechsten folgten weitere Vorträge. Der vierundzwanzigjährige Wiener Kurt Gödel stellte in zwanzig Minuten eine eben abgeschlossene Arbeit vor.
Am Sonntag, dem siebten, fand eine von Hans Hahn geleitete Diskussion über die Grundlagen der Mathematik statt. Auch von Neumann und Gödel ergriffen das Wort. Gegen Ende teilte Gödel ein Ergebnis mit, das noch nicht offiziell veröffentlicht war.
Das zweite Ereignis war Hilberts Rede am 8. September, Naturerkennen und Logik. Sie gehörte nicht zu jener Tagung, sondern zur anschließenden Versammlung Deutscher Naturforscher und Ärzte in derselben Stadt. Eine etwa vierminütige Rundfunkfassung ist als Aufnahme erhalten. Am Schluss heißt es: »Wir müssen wissen. Wir werden wissen.«
Das war an die Mathematik gerichtet. Hilbert wollte nichts grundsätzlich Unerkennbares anerkennen. Damals war auch die Ansicht verbreitet, manches würden Menschen nie begreifen: Bis hierher und nicht weiter. Gegen dieses »nicht weiter« wandte er sich. Sechs Jahre später kam aus seiner eigenen Disziplin ein Beweis dafür, dass ein bestimmter Weg nicht gangbar ist. Doch der Beweis hat eine andere Form als das »nicht weiter«, gegen das Hilbert sich wandte. Er besagt nicht, dass wir etwas nicht verstehen. Er besagt, dass es das Gesuchte nicht gibt. Die beiden Sätze werden oft verwechselt. In dieser Reihe stehen sie an ganz unterschiedlichen Stellen. Der eine handelt von den Grenzen des Menschen, der andere von der Gestalt der Welt.
Zwischen den Ereignissen lag ein Tag. Später hat man sie oft zu einer Szene zusammengerückt: Kaum war die Verkündung verklungen, da wurde nebenan schon das Ergebnis ausgesprochen, das sie zunichtemachte.
Die Unterlagen der Woche zeigen keine Begegnung zwischen den beiden. Hilbert steht nicht in der Liste der Anwesenden oder Wortmeldungen vom 7. September. Ob Gödel am nächsten Tag im Publikum saß, erwähnt keine Zeile. Zwei Räume, zwei Tagungen. Nirgends steht, dass sie voneinander hörten.
Die spätere Szene macht aus einer verwickelten Sache einen Satz. Auf dem Papier sieht die Woche anders aus: Einige Dutzend Menschen, auf zwei Tagungen verteilt, reden in ihrem Kreis; einer von ihnen sagt am späten Sonntagnachmittag, kurz vor Schluss, etwas, worauf niemand antwortet.
Gödels Aufsatz erschien 1931 in einer mathematischen Monatsschrift. Er handelte von etwas Verwandtem, aber anderem. In der von ihm untersuchten Klasse formaler Systeme gibt es Sätze, die man weder beweisen noch widerlegen kann, sofern das System Arithmetik ausdrücken kann und die einschlägigen Konsistenzbedingungen erfüllt. Ein System ist eben ein solches festgeschriebenes Regelwerk.
Das löste die Aufgabe des Lehrbuchs nicht. Das Entscheidungsproblem verlangt ein Verfahren für jede beliebige Formel der Logik erster Stufe. Der Aufsatz von 1931 handelt dagegen von Sätzen innerhalb einer bestimmten Klasse von Systemen. Bis 1936 blieb die Frage offen.
III. Drei Manuskripte im Jahr 1936
1936 trafen nacheinander drei Manuskripte ein, von drei Menschen, die unterschiedliche Wege gegangen waren. Alle stießen auf dieselbe Frage: Wie lässt sich genau angeben, was Rechnen nach Vorschrift heißt? Einer nahm einen Kalkül von Funktionen und Substitutionen; einer ein Band und eine Tabelle von Verhaltensregeln; einer eine Reihe von Kästchen und einen Menschen, der nach Anweisungen arbeitete. Verwandte Ideen können unabhängig entstehen. Ob sie dasselbe ergeben, muss noch bewiesen werden. Ist das bewiesen, sieht es aus, als wären die Wege immer schon einer gewesen.
Im März veröffentlichte Alonzo Church aus Princeton in der ersten Ausgabe einer neuen Zeitschrift für symbolische Logik eine zweiseitige Notiz, deren Titel das Entscheidungsproblem ausdrücklich nannte. Im April brachte er in einer amerikanischen mathematischen Zeitschrift einen neunzehnseitigen Aufsatz heraus: Ein unlösbares Problem der elementaren Zahlentheorie.
Am 28. Mai erhielt die London Mathematical Society ein Manuskript von Alan Turing, einem dreiundzwanzigjährigen Fellow am King’s College in Cambridge. Der Titel lautete Über berechenbare Zahlen mit einer Anwendung auf das Entscheidungsproblem. Am 12. November wurde es verlesen. Gedruckt umfasste es sechsunddreißig Seiten.
Am 7. Oktober erhielt die Zeitschrift für symbolische Logik das dritte Manuskript. Es war von dem amerikanischen Mathematiker Emil Post und hieß Endliche kombinatorische Prozesse: Formulierung 1. Drei Seiten, der kürzeste der drei Texte. Er erschien in der eben gegründeten Zeitschrift, zu deren Herausgebern der Verfasser der März- und Apriltexte gehörte. Sein Name tritt in diesem Jahr dreimal auf: als Verfasser, als derjenige, den es einzuholen galt, und als Herausgeber, bei dem ein Manuskript eingeht. Im nächsten Jahr erscheint er erneut, als Rezensent und als Betreuer. Auch den Namen der Maschine gab er ihr.
Gleich am Anfang seines Aufsatzes erkannte Turing an, dass Church in seiner jüngsten Arbeit das negative Ergebnis bereits erzielt hatte. Im Anhang bewies er, dass seine Berechenbarkeit und Churchs Definierbarkeit äquivalent waren.
Der Anhang zeigt, dass der Aufsatz nach der Einreichung geändert wurde. Jemand anders hatte das Ergebnis zuerst erzielt; Turing musste deshalb beweisen, dass sein Weg zum selben Ziel führte. Der Beweis war nicht vorgesehen. Die zeitliche Reihenfolge zwang ihn dazu.
Im nächsten Jahr äußerte er sich noch einmal dazu. Zu Beginn eines Aufsatzes von 1937, der beide Formulierungen verglich, schrieb er, seine eigene sei vielleicht überzeugender. Mathematisch waren sie gleichwertig, in ihrer Überzeugungskraft nicht. Der Unterschied lag nicht beim Ergebnis, sondern bei der Gestalt der Begründung.
Als Posts drei Seiten erschienen, bat eine redaktionelle Fußnote um einen Vergleich mit Turings bevorstehendem Aufsatz. Sie stellte eigens klar: Posts Text war zwar später datiert, aber völlig unabhängig entstanden.
Bis dahin stand für 1936 Folgendes fest: Church und Turing hatten unabhängig bewiesen, dass das Entscheidungsproblem unlösbar ist. Post hatte unabhängig ein anderes Rechenmodell vorgestellt und erwartete, es sei äquivalent zu dem, was Gödel und Church Rekursion nannten. Seine drei Seiten waren kein dritter Beweis desselben Ergebnisses.
Dass die beiden formalen Definitionen äquivalent waren, galt später als wichtiges Indiz. Für Turing bestand die Arbeit 1936 zunächst darin, zu beweisen, dass sein Verfahren und das von Church genau dieselbe Klasse erfassten. Erst dann konnte er zeigen, wo die Wege zusammenliefen.
1937 veröffentlichte Turing eine dreiseitige Berichtigung. Bernays, schrieb er, habe ihn auf Fehler im ursprünglichen Text aufmerksam gemacht. Noch im ersten Jahr nach dem Erscheinen hatte jemand Fehler in einer Arbeit entdeckt, die später immer wieder als grundlegend bezeichnet wurde. Sie wurden berichtigt. Maschine und Ergebnis blieben.
IV. Der Mensch, der gerade rechnet
Zu Beginn des neunten Abschnitts räumt Turing ein: Bis dahin habe er nicht bewiesen, dass unter seinen formalen Begriff der Berechenbarkeit alles falle, was man gemeinhin berechenbar nennt.
Er nennt drei Arten von Gründen: unmittelbar an die Intuition zu appellieren, die Äquivalenz verschiedener Definitionen zu beweisen und viele Beispiele anzugeben.
Gegenstand der Analyse in diesem Teil ist ein Mensch, der gerade mit Papier und Zeichen rechnet.
Im Englischen von 1936 bezeichnete das Wort computer einen Menschen. Es war ein Beruf und eine Bezeichnung für den Lebenslauf. Menschen saßen an Tischen, rechneten nach gegebenen Regeln Schritt für Schritt und füllten Tabellen. Tafeln für Astronomie, Schifffahrt und Versicherungen entstanden so. Diese Leute gab es überall. Meist wurden sie für wiederholte Arbeit bezahlt. Sie saßen in Reihen in einem Raum, und jeder rechnete einen Abschnitt. Erst Jahrzehnte später ging das Wort an die Maschine über. Die Menschen bekamen andere Namen oder gar keinen. Wird der Name eines Berufs der Maschine übertragen, zählt seine Arbeit meist nicht länger als Arbeit. Das Pronomen, mit dem Turing in diesem Abschnitt den Rechnenden bezeichnet, lautet »er«.
Turing schreibt sinngemäß: Was der Mensch zu einem bestimmten Zeitpunkt tut, hängt von den Zeichen ab, die er gerade betrachtet. Gleich danach fügt er als zweiten Bestimmungsgrund den augenblicklichen Zustand seines Geistes hinzu.
Das Modell enthält von Anfang an zweierlei: sichtbare Zeichen und einen unsichtbaren Zustand. Was im Abschnitt folgt, zielt darauf, auch den zweiten sichtbar zu machen. Geht das nicht, wird er ersetzt. Damit arbeitet der dritte Begründungsweg im neunten Abschnitt, und damit arbeitet der ganze Aufsatz.
Dann zieht Turing die Grenzen einzeln enger. Er geht dabei jedes Mal davon aus, was ein Mensch tun kann, nicht davon, was sich mathematisch bequem beschreiben lässt.
Papier ist gewöhnlich zweidimensional. Er macht daraus ein Band mit Feldern. Nicht weil Menschen tatsächlich mit Papierstreifen rechnen, sondern weil die zweite Dimension für das Rechnen nicht wesentlich ist. Man kommt ohne sie aus.
Es darf nur endlich viele verschiedene Zeichen geben. Das begründet er nicht mathematisch, sondern aus der Erfahrung. Hält man eine sehr lange Zeichenfolge für ein einziges zusammengesetztes Zeichen, lässt sie sich nicht mehr auf einen Blick erkennen. Sein Beispiel sind zwei sehr lange Folgen von Neunen. Ein Mensch kann nicht mit einem Blick sagen, ob sie gleich sind.
Die Begründung kommt aus der Erfahrung, nicht aus der Form. Für einen Grundbegriff der Disziplin, die am meisten auf Strenge hält, führt er an, dass das menschliche Auge nicht ausreicht. Hier wird die Grenze des Modells an einem Menschen gemessen. Nicht die Physik oder die Logik bestimmt sie, sondern was einer mit einem Blick erkennen kann. Später hat man das oft für eine Eigenschaft der Maschine selbst gehalten.
Die Zahl der Felder, die man im selben Augenblick betrachten kann, hat eine Obergrenze, die er mit einem Buchstaben bezeichnet. Wer mehr sehen will, muss sie nacheinander ansehen.
Auch die Zahl der berücksichtigten Geisteszustände muss endlich sein. Bei unendlich vielen, so seine Begründung, kämen einander manche Zustände beliebig nahe und könnten verwechselt werden. Einen Teil eines komplizierten Zustands kann man auslagern und als weitere Zeichen auf das Band schreiben.
In dem Satz steckt eine Handlung: auslagern. Was im Kopf nicht mehr Platz hat, kommt aufs Papier. Sobald es auf dem Papier steht, braucht es nicht länger im Kopf zu sein. Je weniger im Kopf bleibt, desto weniger muss man voraussetzen. Je weniger man voraussetzt, desto besser hält der Beweis. Deshalb wird in diesem Abschnitt immer weiter nach außen verlagert, vom Kopf aufs Papier, bis innen nichts mehr übrig ist.
Auch dafür, wohin der Blick als Nächstes fällt, gibt es eine Grenze. Ein neu betrachtetes Feld darf nur in einer festen Entfernung von einem eben betrachteten liegen. Turing erörtert einen möglichen Einwand: Ein entferntes Feld mit einer Nummer könnte man scheinbar mit einem Blick erkennen. Seine Antwort ist, dass man eine lange Nummer wiederum Zeichen für Zeichen prüfen muss.
Aus diesen Voraussetzungen macht er eine Maschine, die die Rechenarbeit des Menschen nachbildet. Jedem betrachteten Geisteszustand entspricht eine interne Konfiguration der Maschine. Sie liest die entsprechende Zahl von Feldern und verändert den Ort, den sie beobachtet, innerhalb einer begrenzten Entfernung.
Nachbilden kann sie den hier untersuchten Vorgang des Rechnens mit Zeichen. Was sie nachbildet, ist die Arbeit eines Menschen, der Vorgaben abarbeitet. Es ist eine sehr konkrete, eintönige Arbeit, für die Menschen bis dahin Lohn bekommen hatten.
Im Herbst desselben Jahres schrieb ein anderer auf drei Seiten eine andere Gestalt derselben Sache auf. Posts Zeichenraum bestand aus einer Reihe von Feldern, die sich nach beiden Seiten unbegrenzt fortsetzte. Jedes Feld war entweder leer oder markiert. Den Menschen, der dort arbeitet, nannte er Aufgabenlöser oder Arbeiter. Dieser arbeitet in einem Feld und folgt einer festen Reihe unveränderlicher Anweisungen. Er prüft, ob das Feld eine Markierung hat, löscht oder setzt eine Markierung, geht ein Feld nach rechts oder eines nach links.
Zwischen den beiden Manuskripten lag der Atlantik. Ihre Wörter waren verschieden, ihr Ausgangspunkt derselbe: ein Mensch, ein Stapel Papier, Regeln, die er nicht ändern darf.
Zwei Menschen dachten unabhängig darüber nach, was Rechnen ist. Beiden kam zuerst ein Mensch in den Sinn, der gerade arbeitete. Keine Uhr, kein Webstuhl, keine elektrische Schaltung. Ihr Modell sollte das Rechnen erfassen. Und nichts in der Welt jener Zeit sah dem Rechnen ähnlicher als ein Mensch, der nach Vorschrift eine Aufgabe löste.
V. Der Zettel auf dem Papier
Im neunten Abschnitt gibt es einen dritten Ansatz. In dieser Begründung findet Turing für den Geisteszustand einen Stellvertreter aus Papier. In der ersten Begründung gab es etwas, das kein anderer sehen oder überprüfen konnte. Dabei will der ganze Aufsatz zu einer endgültigen Aussage kommen.
Er nimmt an, der Rechnende könne innehalten, weggehen, alles vergessen und später nach einem Zettel auf dem Papier weiterarbeiten. Zusammen mit den Zeichen auf dem Band wäre dieser Zettel eine deutlichere physische Entsprechung des Geisteszustands.
Turing sagt nicht, dass es keinen Geisteszustand gibt oder dass er unwichtig ist, und untersucht nicht, was er ist. Er findet etwas, das die Begründung auch ohne ihn weitergehen lässt. Vorher lag an dieser Stelle etwas, das andere nicht überprüfen konnten. Jetzt liegt dort ein Blatt Papier. Man kann es jemandem zeigen, abschreiben und nachprüfen. Jemand kann es nehmen und daran weiterarbeiten. Sobald ein anderer weiterarbeiten kann, braucht man den ersten Menschen nicht mehr. 1936 war das ein Schritt in einer Begründung. In den folgenden hundert Jahren war es die Lage vieler Menschen. Hier im Abschnitt ist es erst eine Erleichterung für die Beweisführung, die eine nicht überprüfbare Annahme entbehrlich macht.
Turing lässt den Menschen sogar jedes Mal nur einen Schritt tun, wenn er sich hinsetzt. Danach schreibt er eine neue Anweisung für das Weiterarbeiten auf. Der gesamte Zustand der Rechnung ist in jedem Stadium auf dem Zettel und in den Zeichen des Bandes festgehalten.
Man kann den Menschen durch einen anderen ersetzen. Er setzt sich hin, liest den Zettel, macht einen Schritt, schreibt einen neuen Zettel und geht. Wer den Schritt ausführt, ändert das Ergebnis nicht: Alles steht auf Papier. Der Mensch ist austauschbar geworden. Im ersten Argument brachte er noch seinen eigenen Geisteszustand mit. Im dritten sind er und sein Geisteszustand auf das Papier gewandert. Wer danach an diesem Platz sitzt, spielt keine Rolle mehr.
Dieses Mittel blieb in Gebrauch. Ist etwas nicht zu fassen, aber auch nicht zu umgehen, setzt man einen greifbaren Stellvertreter ein und führt die Begründung weiter. Ob der Stellvertreter taugt, zeigt sich daran, ob die Begründung funktioniert. Was es mit dem Ersetzten selbst auf sich hat, braucht man nicht mehr zu beantworten.
Was Turing tat: Er baute ein Modell einer konkreten Arbeit mit Papier und Stift. Was andere später sagten: Dieses Modell sei ein Modell des Geistes. Zwischen den beiden Sätzen liegt ein ganzer Weg. Auf den sechsunddreißig Seiten von 1936 geht der Text keinen einzigen Schritt darauf.
Hier zeigt sich etwas, dem diese Reihe noch öfter begegnen wird. Ist der Stellvertreter erst in die Begründung eingesetzt, bleibt er dort. Geht die Begründung auf, nimmt der Stellvertreter den Platz des Originals ein. Was er ersetzt, ist weder widerlegt noch anerkannt worden. Es kommt nur nach und nach nicht mehr zur Sprache.
VI. Eine Maschine, die jede andere sein kann
Der sechste Abschnitt heißt Die universelle Rechenmaschine.
Zu Beginn schreibt Turing, es sei möglich, eine einzige Maschine zu entwerfen. Gibt man ihr dann die Standardbeschreibung einer anderen Maschine ein, berechnet sie dieselbe Folge wie die beschriebene Maschine. Im siebten Abschnitt steht die vollständige Verhaltenstabelle.
Sie nimmt die Beschreibung einer anderen Maschine als Daten auf. Beschreibung und Beschriebenes kommen auf dasselbe Band. Die Spezifikation der einen Maschine wird zu Zeichen, die eine andere verarbeitet. 1936 erleichterte das einen Beweis. Später wurde es zur Voraussetzung einer ganzen Industrie.
Eine solche Maschine hat eine besondere Stellung. Sie ist nicht die stärkste von vielen. Sie kann als jede von ihnen arbeiten. Was in dieser Klasse getan werden kann, kann auch sie tun. Hier schließt sich der Aufbau zum ersten Mal in seiner eigenen Klasse. Darin gibt es nichts mehr, das er nicht erreicht.
Bis dahin war der Aufbau überall nach außen gewachsen. Mit jedem Zoll wurde das Draußen um einen Zoll kleiner, und doch blieb draußen immer etwas. Diese Maschine ist anders. Sie füllt ihre Klasse auf einmal aus; sie muss nicht weiter wachsen. Um sie etwas anderes tun zu lassen, braucht man sie nicht umzubauen. Man gibt ihr andere Zeichen. Beim Jacquardwebstuhl konnte man schon die Karten wechseln, beim Holzklavier die Prämissen. Was sich ändern ließ, blieb dort aber jeweils an die eigenen Regeln gebunden. Hier wird die Maschine von ihrer Aufgabe getrennt. Damit ändert sich auch das Wort Maschine: Aus etwas, das für eine bestimmte Sache gebaut ist, wird etwas, das auf einen Auftrag wartet. Wer den Auftrag erteilt, steht noch draußen. Was aufgetragen wird und wer darüber entscheidet, hat die Maschine nicht übernommen; der Aufsatz behandelt beides nicht. Sooft später ein weiteres Stück Arbeit in die Maschine verlegt wird, bleiben beide Fragen an ihrem Platz.
Im selben Aufsatz steht im achten Abschnitt ein negatives Ergebnis: Es gibt kein allgemeines Verfahren, das für jede eingegebene Maschinenbeschreibung stets entscheiden kann, ob die Maschine einer bestimmten, von Turing definierten Klasse angehört. Der elfte Abschnitt überträgt die Unentscheidbarkeit auf die logischen Zeichen des Lehrbuchs von 1928. Am Ende steht das Ergebnis: Für das Problem, das acht Jahre zuvor als Hauptproblem der mathematischen Logik bezeichnet worden war, gibt es keine Lösung.
Beides steht im selben Aufsatz. Der Aufbau schließt sich in seiner Klasse. Zugleich ist bewiesen, dass er ein Draußen hat.
Beides folgt sogar aus denselben Mitteln. Nur weil sich jede Maschine als Zeichenfolge aufschreiben und jener einen eingeben lässt, kann man mit der Folge diese Konstruktion vornehmen. Nur weil sie jede Maschine ihrer Art nachahmen kann, lässt sich die Frage stellen, die sie nicht beantworten kann. Geschlossenheit und Draußen sind hier nicht zwei Ergebnisse, sondern zwei Seiten eines Ergebnisses.
Dieses Draußen ist nicht vorläufig. Es verschwindet nicht mit dem technischen Fortschritt. Auch eine größere, schnellere Maschine kommt nicht hinein. Es ist bewiesen.
Die Grenzen der ersten beiden Folgen hatten Menschen gezogen. Jemand sah auf eine Maschine und sagte: Bis hierher. Hier ist die Grenze kein Urteil eines Menschen; sie folgt aus den eigenen Regeln der Maschine. Niemand kann sie verschieben, indem er anderer Meinung wird. Wenn später jemand sagt, dass die Maschine etwas nicht könne, lässt sich nachfragen: Meint er diese Art des Nichtkönnens oder eine andere? Zum ersten Mal benennt in dieser Reihe nicht ein Mensch, was übrig bleibt. Der Rest folgt aus den Regeln des Aufbaus selbst.
Das später geläufige Halteproblem gibt ein Beispiel für die Form eines solchen Beweises. Angenommen, es gäbe das Entscheidungsverfahren. Dann könnte man damit eine Maschine bauen, die sich selbst in die Quere kommt: Was immer das Verfahren für sie vorhersagt, genau das tut sie nicht. So kann es für diese Maschine keine widerspruchsfreie Antwort geben, obwohl es doch für jede Maschine eine geben müsste. Die Annahme hält also nicht. Das ist ein Diagonalargument. In Turings achtem Abschnitt geht es darum, ob eine Maschine fortgesetzt Ausgaben macht und ob sich entscheiden lässt, ob sie ein bestimmtes Zeichen drucken wird.
Für diesen Schritt kommt die Maschine im Aufsatz zum Einsatz.
Um genau zu sagen, dass etwas nicht geht, muss man zuerst sagen, was es heißt, dass etwas geht. Hier nahm diese Bestimmung die Gestalt einer Maschine an. Das spätere Rechenmodell ist hier ein Glied in einem Beweis für ein negatives Ergebnis.
Die Maschine diente als Beweismittel. Will man zeigen, dass kein Verfahren eine bestimmte Aufgabe lösen kann, muss man zuerst wissen, welche Gestalt Verfahren annehmen können. Erst dann kann man alle möglichen Verfahren im Netz einfangen und die Sache zeigen, die keines von ihnen vermag. Die Maschine ist dieses Netz. Sein Urheber wollte nicht Maschinen fangen, sondern Verfahren. Als das Netz fertig war, blieb es selbst zurück.
VII. Der Name kam später
Auf den sechsunddreißig Seiten kommt das Wort Intelligenz kein einziges Mal vor.
Das Wort Geist kommt vor, fast immer im neunten Abschnitt, im Geisteszustand des Rechnenden. Es ist keine Behauptung, die Maschine habe einen Geist, sondern eine Zustandsvariable des Menschen, die in der dritten Begründung sogleich durch den Zettel ersetzt wird. Später las man den Aufsatz oft gerade umgekehrt: Aus einer Variablen des Menschen wurde ein Versprechen über die Maschine.
Auch das Wort denken kommt vor, in gewöhnlichen Wendungen wie »ich denke« oder »man könnte denken«. Der Aufsatz fragt nicht, ob Maschinen denken können.
Achtzig Jahre lang wurde er später oft als Ausgangspunkt dieser Frage betrachtet. Beantwortet hatte er eine andere: Gibt es das gesuchte Verfahren? Diese Frage war von 1900 bis 1936 gestellt worden, sechsunddreißig Jahre lang. Nach sechsunddreißig Jahren lautete die Antwort nein. Für dieses Nein musste man das Rechnen erst vollständig bestimmen. Als das geschehen war, nahm die negative Antwort ein paar Seiten ein. Die Bestimmung blieb.
Noch ein Ausdruck kommt nicht vor: Turingmaschine. Er selbst schrieb von Rechenmaschinen, automatischen Maschinen, Wahlmaschinen und einer universellen Rechenmaschine.
Der Name stammt aus Churchs Rezension vom März 1937. Ihn gab der Maschine der Kollege, der zwei Monate früher zu demselben Ergebnis gekommen war: im Jahr nach Erscheinen des Textes, als er ihn besprach. Er stellte auch einen direkten Vergleich an. Turing fasse die Berechenbarkeit so, dass ihre Gleichwertigkeit mit der effektiver Berechenbarkeit im üblichen Sinn unmittelbar einleuchte. Das schrieb der Mann, der das Ergebnis zuerst erzielt hatte, zu den Gründungsherausgebern der Zeitschrift gehörte und für die nächsten zwei Jahre Turings Betreuer wurde.
Die übrigen Namen kamen noch später. Churchsche These nannte es der Logiker Stephen Kleene 1952 in einem Lehrbuch der Metamathematik. Die Bezeichnung, die Church und Turing zusammen nennt, steht in Kleenes Buch von 1967. Keiner der drei von 1936 hatte die Namen verwendet. Einunddreißig Jahre später rückten zwei Namen zusammen. Einer der beiden Männer lebte da schon nicht mehr. Andere gaben den Namen, als der Genannte nicht mehr dabei war. In dieser Reihe geschieht das zum dritten Mal.
Über das Benennen hatte Post auf der letzten seiner drei Seiten eine Warnung geschrieben.
Church setzte die effektive Berechenbarkeit einer formalen Klasse gleich. Post nannte das eine Arbeitshypothese, die der weiteren Prüfung bedürfe, und wandte sich ausdrücklich dagegen, die Gleichsetzung unter dem Wort Definition zu verstecken. Am Ende des Satzes steht sinngemäß: So würde uns entgehen, dass sie immer wieder geprüft werden muss.
1936, kaum war die Arbeit getan, wies jemand darauf hin: Nennt man das eine Definition, dann erklärt man es für nicht mehr prüfungsbedürftig.
Post wollte nicht auf ein technisches Detail achten. Eine Definition ist eine Übereinkunft, die der Welt nichts nachweisen muss. Eine Hypothese behauptet etwas und wartet darauf, widerlegt werden zu können. Unter welchem Namen derselbe Satz steht, entscheidet darüber, ob später noch jemand nach ihm sieht. Darum ging es Post: Ein Name darf die Sache nicht für alle abschließen.
Später wechselten sich ausgerechnet Definition und These als Bezeichnungen ab. Als Post den Absatz schrieb, war noch keine der beiden als Name aufgekommen.
VIII. Welche wählte Gödel?
Ende September 1936 ging Turing nach Princeton und studierte dort zwei Jahre bei Church. 1938 promovierte er. Im April desselben Jahres bot von Neumann ihm an, als sein Assistent zu bleiben. Turing lehnte ab und kehrte nach Cambridge zurück.
Gödel war in den beiden Jahren, die Turing in Princeton verbrachte, nicht dort. Von den beiden ist kein Brief aneinander, keine gemeinsame Gesprächsnotiz und kein gemeinsamer Aufsatz erhalten. Spätere Darstellungen stellen die Namen oft nebeneinander, weil sich das so gut fügt.
Vor Turing hatte Gödel Churchs Ansatz für unzureichend gehalten. In einem Brief vom November 1935 schrieb Church, Gödel finde den Vorschlag völlig unbefriedigend, effektive Berechenbarkeit durch Definierbarkeit zu bestimmen. Gödel neige damals eher dazu, effektive Berechenbarkeit zuerst zu axiomatisieren.
1946, bei einer mathematischen Tagung zum zweihundertjährigen Bestehen Princetons, erklärte Gödel, zum ersten Mal liege eine absolute Definition vor, die nicht von der Wahl eines Zeichensystems abhänge. »Absolut« hieß: Wechselt man das formale System, ändert sich der Begriff nicht. Gödel sagte »zum ersten Mal«. Die früheren Versuche waren ihm noch nicht so weit gekommen, auch seine eigenen Vorlesungen in Princeton von 1934 nicht. Jede frühere Bestimmung hing an einem bestimmten Zeichensystem. Wechselte es, musste man von vorn anfangen.
1963 fügte er seinem Aufsatz von 1931 eine Anmerkung bei. Besonders dank Turings Arbeit könne man nun eine genaue und unzweifelhaft angemessene Definition des allgemeinen Begriffs des formalen Systems geben. Ein formales System im eigentlichen Sinn, erläutert Gödel dort weiter, zeichne sich dadurch aus, dass sich seine Schlüsse grundsätzlich vollständig von einem mechanischen Apparat ausführen ließen.
Die Anmerkung von 1963 steht hinter einem Aufsatz von 1931. Zweiunddreißig Jahre später fügte Gödel hinzu, was damals gefehlt hatte: eine Bestimmung des formalen Systems. Möglich wurde sie durch ein Modell von 1936, das für etwas anderes gebaut worden war.
1964 schrieb er ein Nachwort zu seinen Vorlesungsnotizen von 1934. Turings Arbeit habe den Begriff des mechanischen Verfahrens analysiert. Im selben Nachwort ließ er eine andere Frage offen: Kann es endliche, nichtmechanische Verfahren geben?
Wer dem Modell sein Siegel gab, machte im gleichen Dokument klar, dass er daraus keine Bestimmung aller menschlichen Geistesvorgänge machte. Er erkannte etwas Bestimmtes an: Der Begriff des mechanischen Verfahrens war geklärt. Ob es darüber hinaus etwas gab, schrieb er als Frage hin. Er beantwortete sie nicht.
In späteren Gesprächen ging er weiter. Vor Turing, sagte er, habe man den klaren Begriff des mechanischen Verfahrens nicht richtig gesehen. Turing habe die richtige Auffassung gebracht. Die Bestimmung über das, was sich mit einer Turingmaschine ausführen lässt, sei richtig und die einzige.
Ausgerechnet der Mann, der dem Modell sein Siegel gab, ließ hier den Rest stehen.
Gödel erkannte das Modell ohne Abstriche an. Er schrieb »unzweifelhaft angemessen«. An eben dieser Stelle schrieb er die größere Frage auf eine neue Zeile. Er zog sein Urteil nicht bis dorthin weiter.
1947 schrieb der Philosoph Ludwig Wittgenstein in einem Manuskript: Turings Maschinen, das sind die rechnenden Menschen.
Gleich danach sagt er, Turings Gedanke lasse sich auch als Spiel darstellen. Weiter unten schreibt er eine eigene Variante des Diagonalarguments auf und bespricht Fälle, in denen eine Regel zu einer sinnlosen Anweisung wird. Als Wittgenstein den oft zitierten Satz über Menschen und Maschinen schrieb, saß er an einer Diagonalaufgabe.
Aus den ersten drei Jahren nach Erscheinen des Aufsatzes sind nur wenige Leser namentlich bekannt. Newman kannte und besprach ihn vor der Einreichung. Church rezensierte ihn. Bernays ging ihn so genau durch, dass er Fehler fand. Im Februar 1937 bat Turing darum, Wittgenstein einen Sonderdruck zu schicken.
Das ist die Liste: ein Lehrer, ein Konkurrent, ein genauer Leser, der Fehler fand, und ein verschickter Sonderdruck.
1948 veröffentlichte Newman in einer Zeitschrift der Royal Society Allgemeine Grundsätze für den Entwurf universeller Rechenmaschinen und besprach Turings universelle Maschine. Einen universellen elektronischen Computer zu bauen, war inzwischen eine Ingenieuraufgabe. Der Verfasser war derselbe Mann, der Turing zwölf Jahre zuvor von der Frage erzählt hatte. Damals war es im Hörsaal eine Logikaufgabe. Zwölf Jahre später schrieb er eine technische Erläuterung. Die Aufgabe hatte sich nicht geändert, wohl aber, wozu sie diente. Dasselbe Mittel hatte zwölf Jahre vorher bewiesen, dass etwas unmöglich war. Jetzt half es zu erklären, wie man eine Maschine entwirft. Etwas war als nichtexistent erwiesen worden, doch das Werkzeug, das man dazu entworfen hatte, blieb bestehen und wurde gebaut. Das wird in dieser Reihe wieder vorkommen: in anderer Gestalt, nach demselben Muster.
Es gibt keine vollständige Liste der Zuhörer jener Septembertage von 1930. Heute kann niemand aufzählen, vor wem Gödel an jenem Sonntagnachmittag sprach, wer ihn hörte und wer nicht. Die spätere Szene stützt sich ausgerechnet auf eine Liste, die es nicht gibt.
Im Frühjahr 1936 schrieb ein Dreiundzwanzigjähriger ein Manuskript zu Ende, um zu beweisen, dass etwas nicht geht. Aus einem Menschen, der am Tisch saß und rechnete, löste er eine Maschine heraus. Später wurde die Maschine gebaut, bekam verschiedene Namen und diente dazu, eine Frage zu stellen, die in jenem Aufsatz kein einziges Mal vorkam.
Er selbst stellte sie erst vierzehn Jahre später. Da hatte er bereits eine wirkliche Maschine zur Hand. Den Menschen aber, aus dem er sie herausgelöst hatte und der nach Vorschrift am Tisch rechnete, nannte man nicht mehr computer.
Noch werden Maschinen gebaut. Wo aber die Grenze liegt, sagt jede Generation von Neuem.