Geschlossenheit lässt sich erkaufen

1 Zwei gerade Zahlen

Sommer 1954, Institute for Advanced Study in Princeton. Dort steht ein Röhrenrechner, einer der ersten überhaupt. Sein Speicher fasst insgesamt 1.024 Maschinenwörter. Das Programm selbst, die Formeln, die es bearbeiten soll, und alles, was während der Rechnung entsteht: Mehr Platz gibt es dafür nicht.

Ein sechsundzwanzigjähriger Logiker schreibt ein Programm für diesen Rechner. Er heißt Martin Davis.

Computer rechnen damals fast ausschließlich mit Zahlen. Dieses Programm entscheidet über Aussagen. Man gibt ihm einen Satz über ganze Zahlen, und es arbeitet sich nach unabänderlich festgelegten Regeln Schritt für Schritt voran. Das zugrunde liegende Entscheidungsverfahren garantiert, dass eine idealisierte Maschine mit unbegrenztem Speicher irgendwann anhält und die richtige Antwort liefert. Dem wirklichen Rechner kann vorher der Speicher ausgehen. Den Ausdruck „künstliche Intelligenz“ gibt es noch nicht.

Die größte Leistung seines Programms, schreibt Davis viele Jahre später, habe darin bestanden, zu beweisen, dass die Summe zweier gerader Zahlen wieder gerade ist.

Das ist Selbstironie, aber keine Übertreibung. Eine Maschine, die einen ganzen Raum füllt, beweist in ihrer Sternstunde etwas, das jedes Grundschulkind weiß.

Damit stehen zwei Fragen im Raum. Warum lässt sich ausgerechnet dieser kleine Ausschnitt der Mathematik einer Maschine anvertrauen, mit der Gewissheit, dass wahr ist, was sie wahr nennt? Und wenn sie das entscheiden kann, weshalb bringt sie im besten Fall so wenig zustande? Auf die zweite Frage wird der Rechner bald selbst antworten, weit ernüchternder, als es die selbstironische Bemerkung vermuten lässt. Die Antwort auf die erste liegt fünfundzwanzig Jahre zurück, in Warschau.

Dienstag, der 24. September 1929, halb elf am Vormittag. Der Erste Mathematikerkongress der slawischen Länder geht in Warschau in seinen zweiten Tag. Den ersten Vortrag in der ersten Sektion hält ein Student, der noch nicht einmal seinen Magisterabschluss hat. Er heißt Presburger, studiert Mathematik an der Universität Warschau und ist vierundzwanzig Jahre alt.

Ein kurzer Blick auf diesen Kongress lohnt sich. Zur Eröffnung spricht Fraenkel über Cantor; Tarski hält gleich zwei Vorträge. Die meisten Teilnehmer kommen aus Polen, einige aber auch aus Japan oder aus dem amerikanischen Texas. Im Tagungsband dürfen die Beiträge in fünf europäischen Sprachen erscheinen, am häufigsten sind Deutsch und Französisch. Nach dem Kongress fährt eine Gruppe im Schlafwagen weiter nach Posen. Dort spricht Kuratowski über Topologie.

Presburgers Vortrag erscheint später im Tagungsband: zehn Seiten Text, dazu eine unnummerierte Seite Nachtrag. Der Titel lautet sinngemäß: Über die Vollständigkeit eines Systems der Arithmetik ganzer Zahlen, in dem die Addition die einzige Operation ist. Gleich am Anfang steht eine unscheinbare Fußnote. Das Ergebnis stammt vom Mai 1928. Die Frage hatte Tarski gestellt.

Diese Frage hat eine Vorgeschichte. Hilbert und seine Schule beschäftigen sich in jenen Jahren mit einem großen Vorhaben: Gibt es ein einheitliches mechanisches Verfahren, das für jede vorgelegte Formel der Logik erster Stufe entscheidet, ob sie allgemeingültig ist? Dafür gibt es einen Namen: das Entscheidungsproblem. Computer gibt es noch nicht. Ein mechanisches Verfahren ist eine Vorschrift auf Papier, so lückenlos festgelegt, dass auch jemand ohne jede Ahnung von Mathematik sie abarbeiten und die richtige Antwort erhalten kann. Hilberts Schule will eine solche Vorschrift für die gesamte Mathematik.

Tarski schneidet ein winziges Stück aus dieser Aufgabe heraus und gibt es einem Studenten. Presburgers Antwort lautet: Für dieses Stück geht es. Es gibt einen kleinen Bereich der Arithmetik ganzer Zahlen, in dem sich von jedem Satz feststellen lässt, ob er wahr oder falsch ist. Ein einziges Verfahren genügt: Welchen Satz man ihm auch vorlegt, nach endlich vielen Schritten liegt die Antwort vor. Genau dieses Verfahren wird Davis fünfundzwanzig Jahre später in Elektronenröhren zum Laufen bringen. Bevor man die Maschine bauen konnte, war sie schon auf Papier gebaut.

In den vorangegangenen Folgen ging es fast durchweg um das Gegenteil. Die Mengenlehre hatte Widersprüche hervorgebracht, der Streit um die Grundlagen hatte zwanzig Jahre gedauert, und ein Satz besagte: Lassen sich die Axiome einer Arithmetik nach einem festen Verfahren aufzählen, so kann sie, sobald sie hinreichend stark ist, nicht zugleich widerspruchsfrei und vollständig sein. Hier aber legt ein Student in einem überfüllten Hörsaal auf zehn Seiten einen Bereich der Arithmetik vor, in dem genau das nicht geschieht. Das Ergebnis gewinnt er 1928, den Kongressvortrag hält er 1929. Das ist drei beziehungsweise zwei Jahre vor der Veröffentlichung jenes Satzes im Jahr 1931.

Die Frage lohnt sich also: Wie schwach muss eine Arithmetik sein, damit sie vollständig ist und zugleich eine einheitliche Entscheidungsmaschine mitliefert? Die Antwort lautet nicht einfach: Man streiche die Multiplikation. Sie ist erheblich verwickelter. Und interessanter.

2 Was sich nicht sagen lässt

Angenommen, es gibt nur Münzen im Wert von drei und von fünf Einheiten. Lässt sich damit ein bestimmter Betrag genau bezahlen? Elf geht. Sieben geht nicht. Gibt es dann eine Grenze, oberhalb deren jeder Betrag möglich ist? Ja: Von acht an lässt sich jeder Betrag bilden.

All das lässt sich in Presburgers Sprache sagen. Und all das lässt sich mit seinem Verfahren entscheiden.

Seine Arithmetik handelt von ganzen Zahlen und kennt als Operation nur die Addition. Zur Sprache gehören das Pluszeichen, Null und Eins, Gleichheit und Größenvergleiche sowie Wörter wie „es gibt“ und „für alle“. Das Dreifache einer Zahl lässt sich durchaus ausdrücken: Man addiert sie zu sich selbst und fügt sie ein drittes Mal hinzu. Schon bei der Aufstellung seiner Axiome hält Presburger fest, dass solche Schreibweisen mangels eines Multiplikationszeichens als eine feste Anzahl wiederholter Additionen zu verstehen sind. Mehrere Zahlen ergeben zusammen eine andere; eine Zahl übersteigt eine andere um einen bestimmten Betrag; bei Division durch sieben bleibt der Rest drei; mehrere ganze Zahlen erfüllen gleichzeitig eine Reihe solcher Bedingungen. Die Sprache kann all das ausdrücken, das Verfahren all das entscheiden. Hier liegt kein Trümmerstück vor. Es ist eine kleine, ganze Welt.

Was fehlt, ist die Multiplikation zweier Variablen. Deshalb lassen sich bestimmte Beziehungen in dieser Sprache überhaupt nicht ausdrücken: dass eine Zahl das Produkt zweier anderer Zahlen ist; dass sie eine Quadratzahl ist; dass sie eine Primzahl ist; dass eine Zahl eine andere teilt, wobei beide variabel sind.

„Nicht ausdrücken“ ist hier wörtlich zu nehmen. Es bedeutet nicht, dass der Beweis schwierig wäre. Es bedeutet, dass es keine Formel dieser Sprache gibt, die die betreffende Eigenschaft allgemein erfasst. Die Zahlenmengen, die sich in ihr beschreiben lassen, haben eine sehr geordnete Gestalt: Ab einem gewissen Punkt wiederholen sich ihre Muster periodisch. Quadratzahlen und Primzahlen folgen keinem solchen Muster. Deshalb haben sie in dieser Welt nicht einmal einen Namen. „Ist diese Zahl eine Primzahl?“ gehört zu den ältesten Fragen der Zahlentheorie. In Presburgers Welt lässt sie sich gar nicht stellen.

Verloren geht Ausdruckskraft, nicht Beweiskraft. Das ist zweierlei.

Drei Begriffe sind hier auseinanderzuhalten; im weiteren Verlauf werden sich ihre Wege trennen. Vollständigkeit bedeutet: Für jeden Satz ihrer Sprache kann die Theorie entweder ihn selbst oder seine Verneinung beweisen. Es bleibt kein Satz übrig, der sich, wie in Folge 17, weder beweisen noch widerlegen lässt. Entscheidbarkeit bedeutet etwas anderes: Es gibt ein einheitliches mechanisches Verfahren, das jeden vorgelegten Satz dieser Sprache nach endlich vielen Schritten mit der richtigen Antwort abschließt.

Zwischen beidem liegt eine kurze Brücke. Ist eine Theorie vollständig, und lassen sich ihre Axiome der Reihe nach aufzählen, dann lassen sich auch ihre sämtlichen Beweise der Reihe nach auflisten. Bei einem vorgelegten Satz arbeitet man die Liste ab, bis entweder der Satz selbst oder seine Verneinung als bewiesenes Ergebnis auftaucht. Wegen der Vollständigkeit muss eines von beiden irgendwann erscheinen. Das Verfahren hält also an. Presburger schreibt gleich zu Beginn seiner Arbeit, dass sein Vollständigkeitsbeweis aufgrund seines effektiven Charakters zugleich ein Verfahren liefert, mit dem sich die Wahrheit eines Satzes entscheiden lässt. Ein Beweis, der nebenbei eine Maschine mitliefert.

Das Wort „vollständig“ hat dabei eine Einschränkung, die leicht überhört wird. Es besagt nicht, dass die Theorie alles weiß. Es besagt nur, dass sie über alles entscheiden kann, was sich in ihrer Sprache sagen lässt. Was diese Sprache nicht ausdrücken kann, danach kann die Theorie nicht einmal fragen. Je weniger ein System sagen kann, desto leichter ist es also vollständig. Das klingt wie ein Lob. Tatsächlich ist es die erste Zeile der Rechnung.

Der dritte Begriff heißt Durchführbarkeit. Dass es ein Verfahren gibt, bedeutet noch nicht, dass es mit der Zeit, dem Speicher und den Maschinen, die Menschen zur Verfügung stehen, tatsächlich ausführbar ist. Die ersten beiden Begriffe bezeichnen logische Eigenschaften. Der dritte fragt weiter: nach Komplexität und nach wirklichen Ressourcen. Ein Rechner mit 1.024 Speicherwörtern wird diesen Unterschied bald unübersehbar machen.

3 Ein Wort verschwindet

Das Verfahren im Kern jener Maschine heißt Quantorenelimination. Bei der Presburger-Arithmetik erweitert man dazu gewöhnlich zunächst die Sprache um Kongruenz- oder Teilbarkeitsprädikate für feste Moduln. In dieser äquivalenten Erweiterung lassen sich dann die Quantoren beseitigen.

In einem Satz können Wendungen wie „es gibt eine Zahl“ oder „für alle Zahlen“ vorkommen. Bei der Quantorenelimination errät man nicht, welche Zahl gemeint sein könnte. Man ersetzt den ganzen Satz durch eine genau gleichbedeutende Aussage, in der die betreffende Zahl nicht mehr vorkommt.

Das einfachste Beispiel: Gibt es eine ganze Zahl, die, zu sich selbst addiert, eine vorgegebene Zahl ergibt? Die Frage enthält ein „Gibt es eine ganze Zahl“. Beseitigt man es, bleibt eine Bedingung allein für die vorgegebene Zahl. Sie lautet: Diese Zahl ist gerade.

Mehr geschieht hier nicht. Aus „Es gibt eine ganze Zahl, deren Summe mit sich selbst jene Zahl ergibt“ wird „Jene Zahl ist gerade“. Die gesuchte ganze Zahl taucht nicht mehr auf, und die neue Aussage lässt sich unmittelbar überprüfen. Solche kleinen Beispiele stehen schon in Presburgers Arbeit: Eine Additionsgleichung mit einem „es gibt“ wird in Bedingungen umgeschrieben, die nur noch von Resten und den übrigen Zahlen handeln. Auch der stolzeste Erfolg von Davis’ Rechner betrifft gerade Zahlen. In seinen Röhren vollzieht sich genau diese Art von Ersetzung, Schritt für Schritt.

Ein zweites Beispiel, diesmal aus einer anderen Welt: Gibt es eine reelle Zahl, deren Produkt mit sich selbst eine vorgegebene Zahl ergibt? Nach der Elimination bleibt die Bedingung, dass die vorgegebene Zahl größer oder gleich null ist. Die gesuchte Zahl ist verschwunden. Übrig bleibt eine Aussage allein über die gegebene Zahl.

Wiederholt man diesen Vorgang, wird aus einem Satz ohne freie Variablen schließlich eine Bedingung, deren Wahrheit oder Falschheit sich unmittelbar feststellen lässt. So entsteht das Entscheidungsverfahren. Tarskis Durchbruch besteht darin, denselben Gedanken auf die Welt der Polynomgleichungen und -ungleichungen über den reellen Zahlen auszudehnen. Dort gibt es Addition, Multiplikation, Größenvergleiche und Quantoren. Und trotzdem lassen sich die Quantoren beseitigen.

Damit kommt nebenbei eine ganze Disziplin hinzu: die Geometrie. Mit elementarer Geometrie meint Tarski diejenigen Fragen, die sich mithilfe von Koordinaten in algebraische Aussagen über reelle Zahlen übersetzen lassen. Man legt ein rechtwinkliges Koordinatensystem fest und beschreibt Punkte durch reelle Koordinaten. Abstände, Kollinearität, senkrechte Geraden, Kreise: Solche Beziehungen lassen sich durch endlich viele Polynomgleichungen oder -ungleichungen ausdrücken. Damit fallen auch die entsprechenden geometrischen Aussagen in den Zuständigkeitsbereich der Maschine. Allgemeine Aussagen über beliebige Punktmengen oder beliebige Funktionen gehören nicht dazu. Die gewählte Sprache bestimmt die Reichweite, nicht das Wort „Geometrie“ auf dem Türschild der Disziplin.

Selbstverständlich ist das keineswegs. „Es gibt“ klingt zunächst nach einer Suche in einem unendlichen Bereich. Eine Maschine kann aber nicht unendlich viele Zahlen nacheinander durchprobieren: Findet sie die gesuchte Zahl nicht, hört sie nie auf. Den Quantor zu eliminieren heißt, diese womöglich endlose Suche durch eine endliche, direkt überprüfbare Aussage zu ersetzen. Warum gerade dieser kleine Bereich einer Maschine überlassen werden kann, ist damit zur Hälfte beantwortet: Jedes „es gibt“ lässt sich darin beseitigen. Ob eine solche Ersetzung möglich ist, hängt davon ab, wie regelmäßig die betreffende Welt gebaut ist. Wo sie regelmäßig genug ist, gelingt die Ersetzung. Wo nicht, gelingt sie nicht.

Das Verfahren liefert Antworten, kein Verständnis. Die entstehenden Ausdrücke können ungeheuer groß werden; sie müssen auch nicht wie ein Beweis aussehen, den ein Mensch schön fände. Doch Quantorenelimination leistet noch etwas, das über Ja und Nein weit hinausgeht. Sie zeigt, welche Menge von Gegenständen eine Aussage mit „es gibt“ und „für alle“ in der betreffenden Welt überhaupt beschreibt. Gerade diese Auskunft über die Struktur wird die spätere Modelltheorie als den wichtigsten Ertrag der Quantorenelimination ansehen.

4 Wo die Grenze liegt

Wenn sich eine Maschine dadurch gewinnen lässt, dass man die Multiplikation streicht, liegt die nächste Frage nahe: Verläuft die Grenze am Malzeichen?

Nein. Zwei bekannte Beispiele widerlegen das von zwei Seiten. Das erste ist die Skolem-Arithmetik: Man behält bei den natürlichen Zahlen nur die Multiplikation und nimmt die Addition heraus. Auch diese Theorie ist entscheidbar. Das zweite Beispiel ist noch schlagender: Tarskis reelle Zahlen. Hier bleiben Addition und Multiplikation erhalten, Größenvergleiche kommen noch hinzu, und die Theorie ist trotzdem entscheidbar.

Die Addition allein lässt sich zähmen. Die Multiplikation allein ebenfalls. Erst wenn beide auf den ganzen Zahlen zusammenkommen, schlägt die Sache um.

Der Grund liegt nicht im Zeichenvorrat. Addition und Multiplikation ganzer Zahlen reichen zusammen aus, um außerordentlich reichhaltige Codierungen aufzubauen. Endliche Folgen, Beweise, Schritt für Schritt ausgeführte Berechnungen: All das lässt sich dann in Beziehungen zwischen ganzen Zahlen übersetzen. Genau diese Fähigkeit braucht die Codierung aus Folge 17. Die Presburger-Arithmetik bringt sie nicht mit; in ihr lässt sich nicht einmal die Multiplikation zweier Variablen definieren. Unterhalb der Schwelle bleibt sie also bei der dritten der drei Voraussetzungen aus jener Folge. An Widerspruchsfreiheit und effektiver Axiomatisierbarkeit fehlt es ihr nicht. Sie erreicht die nötige Ausdrucksstärke nicht.

Tarski formuliert den Gegensatz in seinem Buch ganz unverblümt: Ist eine Theorie stark genug, alle einschlägigen Aussagen der üblichen Arithmetik ganzer Zahlen mit Addition und Multiplikation zu umfassen, dann gibt es für sie kein solches einheitliches Entscheidungsverfahren.

Er führt auch ein besonders schönes Experiment an dieser Grenze vor. In jener Sprache der reellen Zahlen lässt sich die Eigenschaft „Diese Zahl ist ganzzahlig“ nicht allgemein definieren. Dürfen die Variablen dagegen von vornherein auf ganze Zahlen beschränkt werden, kommen Fragen hinzu wie diese: Gibt es ganze Zahlen, bei denen die Summe der dritten Potenzen zweier Zahlen gleich der dritten Potenz einer dritten Zahl ist? Mit solchen Fragen schleicht sich die ganzzahlige Arithmetik in die Sprache ein, und die einheitliche Entscheidbarkeit geht verloren. Derselbe Ausdruck, nur der Wertebereich der Variablen wechselt von reell zu ganzzahlig, und sein logisches Schicksal ist ein anderes.

Schwer und leicht liegen nicht in den Zeichen. Sie liegen darin, wo man die Variablen laufen lässt.

Was jenseits dieser Schwelle möglich ist, wird später endgültig geklärt. Unter den Beteiligten ist ein bekanntes Gesicht. Das zehnte Problem auf Hilberts Liste von 1900 fragt nach einem Verfahren, das für eine beliebige Polynomgleichung mit ganzzahligen Koeffizienten entscheidet, ob sie ganzzahlige Lösungen besitzt. Genau hier werden Variablen miteinander multipliziert, deren Werte ganze Zahlen sind. Seit seiner Zeit als Doktorand lässt diese Frage Martin Davis nicht mehr los. Als er im Sommer 1954 in Princeton die Maschine diesseits der Schwelle in Röhren verwirklicht, sucht er auf der anderen Seite schon seit Jahren.

Mehr als ein Jahrzehnt lang bereitet er dort zusammen mit Putnam und Julia Robinson den Weg. Das letzte Stück fügt Matijassewitsch hinzu. Der erinnert sich genau: Am 29. Januar 1970 stellt er die Lösung in Leningrad zum ersten Mal öffentlich vor. Unter den Zuhörern sitzt Tseitin. Die Antwort lautet: Ein allgemeines Verfahren gibt es nicht. Derselbe Mann hat auf der einen Seite der Schwelle eine Maschine gebaut und auf der anderen dazu beigetragen, zu beweisen, dass sich die Maschine nicht bauen lässt.

Die Schwelle ist deshalb keine sauber gezogene Linie. 1936 zeigen Church und Turing, dass es für die allgemeine Logik erster Stufe kein einheitliches Entscheidungsverfahren gibt. Hilberts Hoffnung, eines für die gesamte Mathematik zu finden, ist damit dahin. Was unterhalb der Schwelle liegt, kommt jedoch aus ganz verschiedenen Richtungen: lineare Arithmetik, Algebra der reellen Zahlen, algebraisch abgeschlossene Körper und später zahlreiche Strukturen aus der Automatentheorie. Ebenso verschieden sind die Gründe ihrer Entscheidbarkeit. Manche verdanken sie der Ordnung, andere der algebraischen Abgeschlossenheit, wieder andere Automaten oder der Quantorenelimination. 1950 zeigt Trachtenbrot zudem, dass sich das allgemeine Entscheidungsproblem auch dann nicht lösen lässt, wenn man nur endliche Strukturen betrachtet. Die Geschichte der Logik hinterlässt also keine Gerade, an deren einem Ende entscheidbar und am anderen unentscheidbar steht. Sie hinterlässt eine Landkarte. Auf ihr sucht man zugleich nach möglichst großen entscheidbaren Ausschnitten und nach möglichst kleinen Erweiterungen, die Unentscheidbarkeit herbeiführen.

5 Warschau und ein Buch, das nicht erscheinen konnte

Presburger war kein Student irgendwo am Rand, dem zufällig eine bemerkenswerte Arbeit gelungen war. Warschau war damals einer der Orte in Europa, an denen sich die logische Forschung am stärksten konzentrierte. Der größere Zusammenhang hieß Lemberg-Warschauer Schule. Begründet hatte sie Twardowski; zu ihren prägenden Gestalten zwischen den Weltkriegen gehörten Ajdukiewicz, Kotarbiński, Leśniewski, Łukasiewicz und Tarski. Ihre Blüte fiel genau in jene einundzwanzig Jahre zwischen den Kriegen, von der Wiedererrichtung des polnischen Staates bis zum Kriegsausbruch. Nach und nach wurde die Logik ihr sichtbarster Zweig. Verengt man den Blick auf den Warschauer Kreis der Logiker, stehen Łukasiewicz, Leśniewski und Tarski im Mittelpunkt. Um sie herum arbeiten Lindenbaum, Presburger und zahlreiche Studierende.

Presburger packte in diesem Kreis mit an. Die Vorlesungen zur mathematischen Logik von Łukasiewicz hat Presburger auf Grundlage des mündlichen Unterrichts ausgearbeitet.

Auch die Zeitschriftenlandschaft war dicht. Die polnische Mathematik besaß mit den Fundamenta Mathematicae ein eigenes Fachorgan; in Lemberg und Krakau erschienen zwei weitere. Und Warschau und Wien waren keine voneinander abgeschnittenen Inseln. Tarski reiste 1930 nach Wien, Carnap kam im selben Jahr nach Warschau, 1935 fuhr Tarski erneut nach Wien. Die Wiener Namen aus den Folgen 15 und 17 und die Warschauer Namen dieser Folge gehörten damals zu ein und demselben Netz.

Tarskis persönliche Lebensumstände verschwinden dagegen vollständig, wenn man nur spätere Publikationsdatenbanken betrachtet. Geboren wurde er als Teitelbaum. 1923 nahm er zusammen mit seinem Bruder den Namen Tarski an und trat zugleich zum Katholizismus über, obwohl er selbst nicht religiös war. Es gab dafür mehr als einen Grund. Er wollte Pole sein; zugleich wusste er, wie schwer ein Jude im damaligen Polen an eine Universitätsstelle gelangte. Nach seiner Promotion in Warschau 1924 unterrichtete er lange Mathematik an einer höheren Schule und hatte daneben nur eine kleine Lehrposition an der Universität Warschau. Seine Bewerbung um eine Professur in Lemberg scheiterte 1939. Eine ganze Reihe logischer Ergebnisse von Weltrang stammte in jenen Jahren von einem Mann, der zugleich Schulunterricht gab.

Sein Entscheidungsverfahren für die Algebra der reellen Zahlen fand er 1930. Die historischen Anmerkungen am Ende des Buches greifen noch weiter zurück: Ein Teil der Ergebnisse war bereits in seinen Vorlesungen von 1926 bis 1928 vorgekommen. Warschauer Studierende, die damals in seinem Hörsaal saßen, hatten also schon etwas davon gehört. Wer nicht dort saß, musste noch zwanzig Jahre warten, bis er es lesen konnte.

Dann begann die eigene Geschichte dieses Buches. Es sollte 1939 bei einem Pariser Verlag erscheinen. Der Krieg verhinderte es. Wieder aufgenommen wurde das Vorhaben von einer amerikanischen Forschungseinrichtung: 1948 interessierte sich das RAND-Projekt der US-Luftwaffe für das Entscheidungsproblem. Man holte das neun Jahre liegengebliebene Manuskript hervor; McKinsey wirkte an der Bearbeitung und Überarbeitung mit. Gedruckt wurde es als nummerierter RAND-Bericht. Im Mai 1951 folgte eine revidierte Ausgabe, nach der das Werk später meist zitiert wurde. Sieben oder acht Jahre nach der ersten Ausgabe sollte auf einem Rechner derselben Einrichtung ein andersartiges Programm zum Beweisen von Sätzen laufen.

Zwischen Tarskis Entdeckung des Verfahrens und der international zugänglichen Veröffentlichung des Buches lagen achtzehn Jahre. Warum es nach 1939 nicht weiterging, ist klar: wegen des Krieges. Warum es auch in den neun Jahren von 1930 bis 1939 nicht gedruckt wurde, dafür findet sich bis heute keine Erklärung.

Alle Jahreszahlen dieses Abschnitts lassen sich nachprüfen. Eine einzige nicht.

Presburger wurde am 27. Dezember 1904 in Warschau geboren. 1923 schloss er die Schule ab und ging an die Universität Warschau. Nur eine eigens seiner Person gewidmete Studie liegt vor: Zygmunts Biografie von 1991, die sich hauptsächlich auf erhaltene Studienakten der Universität Warschau stützt. Diese Akten wurden später hochauflösend gescannt, geordnet und öffentlich zugänglich gemacht: Einschreibeformulare, belegte Lehrveranstaltungen, Abschlussunterlagen. Dass Presburger im Oktober 1930 den Magistergrad in Mathematik erhielt, lässt sich heute noch Blatt für Blatt nachvollziehen.

Danach reißt die Spur ab. Presburger war polnischer Jude und wurde Opfer des nationalsozialistischen Holocaust. Meist wird sein Tod ungefähr auf 1943 datiert. Selbst in der wissenschaftlichen Biografie steht hinter dieser Jahreszahl ein Fragezeichen. Wann genau und wo er starb und was ihm zuletzt widerfuhr, ist nicht so sicher belegt wie seine Studienzeit.

Zehn Seiten, geschrieben von einem Mann in seinen Zwanzigern, werden seit mehr als siebzig Jahren von immer neuen Maschinen ausgeführt. Wie er selbst ums Leben kam, lässt sich nicht aufschreiben.

6 Ein anderer Weg

Zurück zu dem Rechner im Sommer 1954.

Das Entscheidungsverfahren ist da, die Maschine ebenfalls. Doch Davis stößt bald an eine Wand. Auf Papier besteht das Verfahren nur aus wenigen Schritten. Im Rechner muss eine Formel aber zunächst in eine bestimmte Normalform gebracht werden, und diese Umformung bläht sie auf. Kombinationen von Bedingungen schichten sich übereinander; aus einer kurzen Zeile kann ein um ein Vielfaches längerer Ausdruck werden. Die 1.024 Speicherwörter reichen rasch nicht mehr aus. Hier beginnt Davis’ spätere Skepsis gegenüber noch aufwendigeren Entscheidungsverfahren.

An dieser Maschine wird zum ersten Mal handgreiflich: Entscheidbar heißt noch lange nicht bezahlbar.

Zwei Jahre später setzt eine andere Gruppe am entgegengesetzten Ende an. Newell und Shaw von RAND entwickeln zusammen mit Simon vom Carnegie Institute of Technology ein Programm zum Beweisen logischer Sätze. Es nimmt sich die Aussagen am Anfang von Whiteheads und Russells Principia Mathematica vor. Statt einer Vorschrift zu folgen, die ein Ergebnis garantiert, sucht es gezielt. Was dem Ziel näherzukommen scheint, wird zuerst versucht; wird der Suchbaum zu groß, werden einige Zweige abgeschnitten. Findet das Programm einen Beweis, legt es ihn vor. Findet es keinen, kann es nur sagen, dass es keinen gefunden hat. Zwischen „nicht gefunden“ und „nicht vorhanden“ liegt genau das, was Davis’ Maschine besitzt und dieser Maschine fehlt: eine Garantie. Der Name „künstliche Intelligenz“ ist damals noch kein Jahr alt.

Die eine Seite garantiert eine Antwort, sprengt aber bald den verfügbaren Speicher. Die andere verzichtet auf die Garantie, immer einen Beweis zu finden, um den Speicher nicht zu sprengen. Was sie als Beweis findet, muss dennoch verlässlichen Schlussregeln genügen. Hier gabeln sich die Wege.

An dieser Weggabelung steht ein Chinese. Wang Hao wird 1921 in Jinan geboren, schließt sein Studium an der Vereinigten Südwestuniversität in Kunming ab und geht später in die USA, um mathematische Logik zu betreiben. Im Sommer 1958 schreibt er im IBM-Forschungslabor in Poughkeepsie im Staat New York mehrere Programme für einen damaligen Großrechner. Eines davon beweist sämtliche mehr als zweihundert Sätze der ersten fünf Kapitel der Principia Mathematica. Es braucht insgesamt rund siebenunddreißig Minuten. Zwölf Dreizehntel dieser Zeit entfallen auf Einlesen und Ausdrucken. Für die Beweise selbst bleiben weniger als drei Minuten.

Er veröffentlicht die Ergebnisse in einer Arbeit, deren Titel sinngemäß Auf dem Weg zu einer mechanisierten Mathematik lautet. Das klingt, als hätte Hilberts alte Hoffnung nur eine neue Formulierung bekommen. An einer Stelle wird Wang ausgesprochen deutlich. Newell und seine Kollegen hätten beim Vergleich von Heuristik und Algorithmus einen besonders ungeschickten Algorithmus als Maßstab gewählt. Ausgerechnet an einem besonders ineffizienten Verfahren die Überlegenheit der Heuristik über Algorithmen vorführen zu wollen, lasse sich schwerlich als fair bezeichnen.

Aus seinen Ergebnissen zieht er noch eine Lehre. Selbst in einem recht reichhaltigen Gebiet nutzen die tatsächlich bewiesenen Sätze meist nur einen kleinen Teil dessen, was dieses Gebiet insgesamt hergibt. Wenig sagen zu können ist eine Voraussetzung dafür, dass eine Maschine entscheiden kann. Doch was Menschen tatsächlich beweisen wollen, kommt meistens ohnehin mit wenig aus.

1983 erhält Wang den ersten Meilensteinpreis für maschinelles Theorembeweisen, vergeben von der International Joint Conference on Artificial Intelligence. Fast zwanzig Jahre später schreibt Davis über diese frühe Geschichte. Unter dem Titel steht: „Dem Andenken an Wang Hao“.

7 Der Preis steht auf einem anderen Blatt

Nach der Gabelung verlaufen die beiden Wege fast zwanzig Jahre getrennt.

Auf dem heuristischen Weg entstehen immer neue Programme, die Versprechen werden immer größer. 1973 beauftragt der britische Science Research Council den angewandten Mathematiker Lighthill mit einer umfassenden Bewertung der künstlichen Intelligenz. Ein Ausdruck kehrt in seinem Bericht ständig wieder: kombinatorische Explosion. Bei kleinen, sauber abgegrenzten Aufgaben leisten die Programme Erstaunliches. Sobald man sie auf die Größenordnungen der wirklichen Welt loslässt, vervielfachen sich die zu durchsuchenden Möglichkeiten so sehr, dass kein Ende mehr absehbar ist.

Im Jahr darauf kommt von der anderen Seite eine noch ernüchterndere Nachricht. 1974 fragen Fischer und Rabin nicht, ob Presburgers Verfahren schnell ist. Sie fragen, ob irgendein Verfahren grundsätzlich sehr viel schneller sein könnte. Die Antwort lautet nein. Welches allgemeine Verfahren man für diese Arithmetik auch entwirft, es gibt stets Formeln, bei denen sich die erforderliche Schrittzahl mit jedem kleinen Stück zusätzlicher Eingabe erneut quadriert. Das nennt man eine doppelt exponentielle untere Schranke. Oppen liefert 1978 auch eine obere Schranke. Damit ist das Problem zwischen zwei außerordentlich hohen Mauern eingeklemmt.

Das heißt nicht, dass jede Formel einer bestimmten Länge so schwer ist. Es heißt, dass jedes allgemeine Verfahren mit derart schlechten Eingaben rechnen muss. Und es liegt nicht daran, dass jemand sein Programm schlecht geschrieben hätte. Die Schwierigkeit gehört zum Problem selbst. Fischer und Rabin untersuchen daneben die Länge von Beweisen: Unter geeigneten Voraussetzungen gibt es beweisbare Sätze, deren Beweise zwangsläufig außerordentlich lang sein müssen. Damit zerfällt die Sache noch einmal in drei Fragen: Lässt sich ein Satz entscheiden? Lässt er sich beweisen? Und kann ein Mensch tatsächlich einen Beweis in die Hand bekommen, den er auch zu Ende lesen kann?

Die beiden Wege treffen sich vor derselben Wand wieder. Lighthill beschreibt die Wand, an die ein Forschungsgebiet stößt, wenn es die Größenordnungen der wirklichen Welt bewältigen soll. Fischer und Rabin sagen: Selbst wenn man sich in den kleinsten, saubersten, am besten abgesicherten Bereich der Arithmetik zurückzieht, steht die Wand noch da.

Bei den reellen Zahlen wiederholt sich die Geschichte. Tarskis Verfahren beweist, dass eine Entscheidungsmethode existiert; ein praktisch ausführbarer Algorithmus ist es damit noch nicht. Das erste vollständige Verfahren, das diesen Namen auch in der Praxis verdient, wird gewöhnlich Collins im Jahr 1975 zugeschrieben. Es zerlegt den mehrdimensionalen reellen Raum in endlich viele Bereiche, in denen die eingegebenen Polynome jeweils ihr Vorzeichen beibehalten. Fragen über unendlich viele Punkte lassen sich dadurch anhand repräsentativer Prüfungen in endlich vielen Bereichen entscheiden. Das Verfahren wird später zu einer Grundlage von Computeralgebrasystemen. Doch die Zahl der entstehenden Bereiche kann mit der Zahl der Variablen doppelt exponentiell wachsen. Davenport und Heintz zeigen 1988, dass auch dies nicht allein an diesem einen Verfahren liegt: Die allgemeine Quantorenelimination über den reellen Zahlen ist selbst mit Schwierigkeiten dieser Größenordnung belastet. Die Verbesserungen der folgenden Jahrzehnte zielen vor allem darauf, unnötige Arbeit zu vermeiden, nicht darauf, die untere Schranke zu widerlegen: bessere Projektionen, Zerlegungen nur dort, wo die konkrete Aufgabe sie wirklich braucht.

In der Geometrie versucht jemand einen anderen Tausch. Zwischen 1976 und 1977 beginnt Wu Wenjun in Peking, Beweise geometrischer Sätze auf den Computer zu bringen. Später schreibt er in einem Vorwort, Tarskis Mechanisierungssatz umfasse zwar einen weiten Bereich der elementaren Geometrie, sei aber viel zu ineffizient. Wu überführt geometrische Aufgaben in Systeme von Polynomgleichungen. Aussagen, in denen Größenvergleiche eine Rolle spielen, lässt er zunächst beiseite. Der Kreis der möglichen Fragen wird etwas kleiner, und die Maschine kommt voran. Auf diese Weise gelingt ihr der Beweis einer Reihe durchaus nichttrivialer geometrischer Sätze.

Wu nennt das mathematische Mechanisierung. Seine Anregung, schreibt er, stamme aus der Mathematik des alten China. Die Neun Kapitel über die Rechenkunst und Liu Huis Kommentar aus dem Jahr 263 gelten ihm als klassische Vertreter eines östlichen Systems mechanisierter mathematischer Algorithmen. Liu Hui aus Folge 5 wird hier von einem Mathematiker des zwanzigsten Jahrhunderts als Vorgänger anerkannt. Im selben Vorwort hält Wu auch fest, dass Wang Haos Maschine in drei Minuten mehr als zweihundert Aussagen bewiesen hatte.

Zwischen Entscheidbarkeit und Brauchbarkeit bleibt also ein Spalt. Mathematische Entscheidbarkeit fragt, ob es ein einheitliches Verfahren gibt, das garantiert irgendwann anhält und richtig antwortet. Sie verspricht keine Sekunden, keine hundert Jahre, nicht einmal, dass die Ressourcen dieses Universums für die Ausführung reichen. Technische Brauchbarkeit fragt dagegen, ob ein Programm bei den tatsächlich auftretenden Aufgaben mit einer gegebenen Maschine, gegebener Zeit und gegebenem Speicher häufig schnell zu nützlichen Ergebnissen kommt. Auf die eine Frage kann die Antwort ja lauten und auf die andere nein. Oft genug tut sie das.

Auch umgekehrt gilt die Unterscheidung. Dass der ungünstigste Fall verheerend aussieht, macht ein Verfahren noch nicht nutzlos. Viele Entscheidungsverfahren benötigen im theoretisch schlimmsten Fall ungeheure Ressourcen und bewähren sich trotzdem bei den Aufgaben, die in der Praxis anfallen. Hier kehrt Wang Haos Lehre wieder. Die meisten wirklichen Aufgaben liegen nicht in jener schlimmsten Ecke.

8 Eine Rechnung mit drei Spalten

Zurück zum Titel. Lässt sich Geschlossenheit erkaufen? Ja, gleich zweimal. Und man erhielt nicht beide Male dasselbe.

Presburger gewann einen vollständigen und entscheidbaren Ausschnitt aus der Arithmetik ganzer Zahlen. Der Preis: Weite Teile der Zahlentheorie lassen sich darin nicht ausdrücken. Tarski gewann ein einheitliches Entscheidungsverfahren für die Algebra der reellen Zahlen und damit auch für die elementare Geometrie. Er hatte nichts gestrichen; bei ihm lag der Preis anderswo. Seine Sprache kann von sich aus nicht sagen: „Diese Zahl ist ganzzahlig.“ In keinem der beiden Fälle fand ein Handel statt. Beide Male untersuchte jemand einen bestimmten mathematischen Gegenstand und entdeckte, dass dieser Gegenstand bemerkenswert regelmäßig gebaut war. Das Wort „erkaufen“ beschreibt die Gestalt, die wir im Rückblick erkennen. Es bedeutet nicht, dass damals jemand an einer Kasse stand.

Am längsten leben diese beiden Ergebnisse in zwei späteren Disziplinen weiter. Tarskis Quantorenelimination wird zu einer grundlegenden Technik der Modelltheorie; reelle Zahlen und algebraisch abgeschlossene Körper gehören zu den elementaren Beispielen ihrer Lehrbücher. Presburgers Arithmetik geht in die Programmverifikation ein. Ob ein Programm korrekt arbeitet, hängt oft von Array-Indizes, Schleifenzählern und linearen Beziehungen zwischen ganzen Zahlen ab. Genau für solche Aussagen ist sie geschaffen. 1972 arbeitet Cooper Presburgers Verfahren zu einer auf Computern praktisch brauchbaren Fassung um. Seine Arbeit heißt sinngemäß Theorembeweisen in der Arithmetik ohne Multiplikation und erscheint in der Reihe Machine Intelligence. Manche Programme, die Mathematikern heute helfen, Beweise Zeile für Zeile zu überprüfen, führen ein eigenes Modul ausdrücklich unter der Bezeichnung „Entscheidungsverfahren für die Presburger-Arithmetik“. Darin arbeitet Coopers Version.

Was lässt sich daraus mitnehmen?

Dass ein System auf jede Frage antworten kann, die sich in seiner Sprache stellen lässt, klingt nach einer Stärke. Es ist zugleich ein Verzeichnis dessen, was diese Sprache nicht sagen kann. Wer eine Denkweise beurteilen will, sollte zuerst zählen, wie viele Fragen sie nicht beantworten kann, und erst dann, wie viele sie beantwortet. Wer alles beantworten kann, hat meistens zu wenig gefragt.

Seit jenem Rechner von 1954 lässt sich jede Maschine, die gebaut wird, um Fragen zu beantworten, in dasselbe Rechnungsbuch eintragen. Es hat drei Spalten. In der ersten steht, was man die Maschine fragen kann. In der zweiten, welche Garantie für ihre Antworten gilt. In der dritten, was eine einzige Antwort kostet.

Presburgers zehn Seiten besagen: Engt man die erste Spalte hinreichend ein, kann man die zweite vollständig ausfüllen. Tarskis Bemerkung in seinem Buch und die Ergebnisse von Church und Turing aus dem Jahr 1936 besagen: Lässt man in der ersten Spalte alle Fragen der ganzzahligen Arithmetik mit Addition und Multiplikation zu, kann die zweite nicht mehr vollständig ausgefüllt werden. Fischer und Rabin zeigen: Selbst wenn die erste Spalte so schmal bleibt wie bei Presburger und die zweite lückenlos gefüllt ist, kann in der dritten ein Preis stehen, den niemand aufbringen kann.

Davis’ Maschine füllte die Garantiespalte aus und scheiterte an den Kosten. Das Programm von 1956 ließ dort eine Lücke, um bei den Kosten zu sparen. Wang Hao brachte im selben Gebiet Garantie und bezahlbaren Aufwand zusammen, weil das Gebiet klein genug war. Wu Wenjun nahm einen Teil der möglichen geometrischen Fragen heraus, und die Kosten wurden tragbar. Seither bewegen sich die Maschinen zwischen diesen drei Spalten. Manche halten an der Garantie fest und erweitern den Bereich des Fragbaren Stück für Stück. Ein Verfahren, das Davis später mit Putnam und anderen entwickelte, entscheidet beispielsweise, ob eine Menge logischer Bedingungen zugleich erfüllt werden kann. Seine Nachfahren werden in großem Umfang zur Prüfung von Chips und Software eingesetzt. Andere Maschinen lassen sehr viele Fragen zu und lassen die Garantiespalte leer. Vieles von dem, was später künstliche Intelligenz heißt, wird auf diese Weise verbucht.

Eine Seite, auf der alle drei Spalten vollständig ausgefüllt wären, hat noch niemand vorgelegt. Dass jedenfalls die Spalten des Fragbaren und der Garantie nicht beide lückenlos sein können, sagt ein mathematischer Satz.

In dieser Folge hielt der Krieg ein Buch von der Druckerei fern und brach das Leben eines Menschen ab. Das Manuskript fand sich später wieder. Von Presburgers letzten Tagen blieb nur eine Jahreszahl mit einem Fragezeichen. In der nächsten Folge drehen wir die Zeit zurück auf 1933 und kehren an eine Universität zurück.

Mit Zahlen wird weitergerechnet. Was als Mathematik zählt, ist noch immer nicht ausgemacht.

Quellen und weiterführende Lektüre

Die folgenden Quellen belegen historische Einzelheiten und unterschiedliche Deutungen im Text. Sammlungsnachweise, antike literarische Zeugnisse und moderne Rekonstruktionen sind nicht dieselbe Art von Beleg.

• Presburgers Originalarbeit in kommentierter Übersetzung
• Stanford Encyclopedia of Philosophy: Alfred Tarski
• Tarskis RAND-Bericht zum Entscheidungsverfahren
• Wang Hao: Auf dem Weg zu einer mechanisierten Mathematik, Originalaufsatz
• Oppen: Obere Komplexitätsschranke von 1978
• Brown und Davenport zur Komplexität der Quantorenelimination
• Wu Wenjuns Vorwort zur Reihe über mathematische Mechanisierung