Zusammenfassung

Zwei Ereignisse im 20. Jahrhundert veränderten das Bild der Mathematik nachhaltig. Zuerst bewies Kurt Gödel, dass es kein endlich axiomatisierbares Kalkül geben kann, in dem alle wahren Aussagen über natürliche Zahlen beschreibbar sind. Einige Jahre später wies Alan Turing die Existenz von nicht berechenbaren Funktionen nach. Die ursprünglichen Aussagen wurden in der Folgezeit nicht nur bestätigt, sondern weiter verschärft und mit umfangreichen konkreten Beispielen belegt. Gleichzeitig begann aber auch die Suche nach Auswegen aus den Beschränkungen.

 

In diesem Beitrag werden die Hintergründe dieser Ergebnisse und ihre Entwicklung erläutert. Ziel ist dabei, ein Verständnis für die Zusammenhänge zu schaffen, um die Diskussionen zu diesem Thema besser beurteilen zu können und sich ein Bild von den Auswirkungen zu machen.

 

Einleitung

Die Suche nach Erkenntnis über die Welt und allen in ihr erkennbaren Strukturen basiert in weiten Teilen auf Erfahrung. Wir erkennen Gesetzmäßigkeiten wie kausale Zusammenhänge, statistische Häufungen und Korrelationen oder logische Beziehungen und strukturieren so Zusammenhänge, um damit Voraussagen über zukünftige Ereignisse abzuleiten. Diese Gesetzmäßigkeiten können in vielen Fällen intuitiv erfasst werden, führen aber in kanonischer Fortsetzung zu einer strukturierten und abstrakten Beschreibung der erkannten Zusammenhänge. Geschichtlich kommt es zunächst zu einer starken Überlagerung mit mythischen, aber auch religiösen Vorstellungen. Daneben entwickelt sich die Mathematik, nicht zuletzt wegen ihrer Neutralität und Exaktheit, zu einem Werkzeug zur Modellierung abstrakter Zusammenhänge, aber auch von Naturereignissen. Von dauerhafter Bedeutung für die Entwicklung der Mathematik sind Aristoteles und Euklid – insbesondere unter den hier zu betrachtenden Aspekten. Aristoteles erarbeitet in seinen logischen Schriften eine Argumentationstheorie und begründet mit der Syllogistik die formale Logik. Euklid formalisiert große Teile der damals bekannten Mathematik, insbesondere führt er für die Geometrie ein formales System ein. Dazu benutzt er in seinem Werk Die Elemente Definitionen, Postulate (nach Aristoteles Grundsätze) und Axiome (nach Aristoteles allgemeine und unbezweifelbare Grundsätze), die eine strenge Beweisführung ermöglichen. Diese grundlegenden Arbeiten, die für über 2000 Jahre weitgehend unverändert blieben, bildeten die Basis für umwälzende Veränderungen in der Mathematik, die Ende des 19. Jahrhunderts begannen.

 

Doch bevor hierauf eingegangen wird, soll zunächst die Bedeutung des Ansatzes von Aristoteles und Euklid genauer herausgearbeitet werden. Ein axiomatisches System (Kalkül), zusammen mit den Schlussregeln der Logik, (plus weiteren technischen Details, auf die hier nicht eingegangen werden soll) erlaubt es, alle Annahmen der Beweisführung offen zu legen, Schlussfolgerungen zu formalisieren und damit Fehler auf ein Minimum zu reduzieren bzw. für andere leicht auffindbar zu machen. Die Mathematik, die sich im Laufe der vergangenen Jahrtausende bereits als ein perfektes Werkzeug zur Modellierung naturwissenschaftlicher Zusammenhänge erwiesen hatte, wird damit aufgrund der vollständigen Transparenz in ein faktisch fehlerfreies Werkzeug verwandelt. Durch die Formalisierung ergibt sich darüber hinaus die Möglichkeit, von dem zu untersuchenden Gegenstand noch weiter zu abstrahieren. So wird hier nicht mehr über Zahlen gesprochen, sondern über Zeichen, die anhand festgelegter Regeln kombiniert werden. Dies wird sich insbesondere im Zusammenhang mit Rechnern als nützlich erweisen, doch dazu später. Abstraktion an sich ist aber schon ein mächtiges Werkzeug. Sie erlaubt über Dinge zu reden, die es in der Natur nicht gibt. So erschließt sich das Konzept der negativen Zahlen bereits manchem Fünfjährigen, auch wenn niemand jemals „-10 Äpfel“ gesehen hat. Ebenso traut man Schülern der 5. Jahrgangsstufe bereits unendliche Mengen zu, auch wenn es nach heutigem Wissensstand wohl keine unendlichen Mengen im physikalischen Universum gibt. Doch zurück zum Gedanken der Axiomatisierung. Hieran wird ein Grundgedanke aller modernen Wissenschaften deutlich: Man geht davon aus, dass sich alle beobachteten Phänomene, egal wie komplex, auf einige wenige und intuitiv nachvollziehbare Grundannahmen zurückführen lassen. Anders formuliert, lässt sich jede Aussage über die Natur aus wenigen Grundannahmen mit Hilfe logischer Schlussfolgerungen ableiten. Nicht umsonst gilt deshalb die Mathematik als die Basis aller Naturwissenschaften. Angesichts der Möglichkeiten, die eine Axiomatisierung der Mathematik bietet, ist der Gedanke naheliegend, nicht nur die Geometrie, so wie bei Euklid, sondern ausnahmslos alle Bereiche, wie etwa die natürlichen Zahlen, durch geeignet gewählte Axiome und Kalküle zu beschreiben. Neben einer exakten Fundierung verbindet sich hiermit ein anderer verlockender Gedanke: Sollte es bei einer geeigneten Wahl von Axiomen möglich sein, alle mathematischen Wahrheiten herleiten zu können? Falls sich alle mathematischen Aussagen auf einfachere, nicht mehr reduzierbare Aussagen, die Axiome, zurückführen lassen, dann besteht die Aufgabe folglich nur in einer geeigneten Auswahl von Axiomen. Einer der ersten, der diesen Vollständigkeitsanspruch formuliert, ist Kant [Kant 1781 A 476/B 504]: „Gleichwohl gibt es Wissenschaften, deren Natur es so mit sich bringt, daß eine jede darin vorkommende Frage, aus dem, was man weiß, schlechthin beantwortlich sein muß, daraus die Frage entspringt, und wo es keineswegs erlaubt ist, unvermeidliche Unwissenheit vorzuschützen, sondern die Auflösung gefordert werden kann.“ Wenig später konkretisiert er diese Aussage auf die Mathematik.

 

René Descartes und Gottfried Wilhelm Leibniz leisten wichtige Beiträge zur Logik, die Ende des 19. Jahrhunderts von George Boole, Gottlob Frege und Guiseppe Peano weiterentwickelt und für unterschiedliche Teile der Mathematik umgesetzt werden. Parallel zu dem Erstarken des axiomatischen Ansatzes entstehen aber an zwei Fronten Probleme, die das ganze Vorhaben ins Wanken zu bringen drohen. Zum einen taucht die Frage nach der „natürlichen“ Gültigkeit von Axiomen auf. Konkret entzündet sich die Diskussion an dem so genannten Parallelenaxiom von Euklid. Eine übliche Definition dieses Axioms lautet [Henn, 2003]: „In einer Ebene α gibt es zu jeder Geraden g und jedem Punkt S außerhalb von g genau eine Gerade, die zu g parallel ist und durch den Punkt S geht.“ Nikolai Lobatschewski formuliert 1826 eine Geometrie, in der die übrigen Axiome der euklidischen Geometrie gelten, das Parallelenaxiom jedoch nicht. Die sich hieraus ergebende Geometrie ist zunächst nicht unmittelbar intuitiv, hat aber durchaus reale Anwendungen und wird für eine Reihe von Anwendungen genutzt, wie etwa der Kartographie, und bildet darüber hinaus wichtige mathematische Grundlagen der Allgemeinen Relativitätstheorie. Das zweite Problem entsteht durch Paradoxien, insbesondere die von Bertrand Russell und Ernst Zermelo entdeckte Russellsche Antinomie. Ausgangspunkt ist hier die Menge aller Mengen, die sich nicht selbst enthalten, bezeichnet als R. Auf den ersten Blick scheint R keine großen Probleme in sich zu bergen. Stellt man jedoch einige Fragen zu den Eigenschaften dieser Menge, dann sieht die Situation anders aus. So insbesondere die Frage, ob R sich selbst enthält. Angenommen, R enthält sich selbst, dann gilt aufgrund der Definition, dass R sich nicht enthält, was der Annahme widerspricht. Angenommen es gilt das Gegenteil und R enthält sich nicht selbst, dann erfüllt R die Mengeneigenschaft, so dass R sich doch selbst enthält, also der Annahme widerspricht. Wie auch immer man den Sachverhalt betrachtet, es führt zu einem Widerspruch. Konfrontiert mit solchen Herausforderungen, steht die Mathematik zur Wende in das 20. Jahrhundert an einem Scheideweg.

 

David Hilbert nimmt sich dieser Problematik an. Es geht ihm zum einen um geeignete Axiome und Schlussregeln, die von allen Mathematikern akzeptiert werden, denn sein Ziel ist es auch, die unterschiedlichen Strömungen in der Mathematik, mit Hilfe der finitistischen Beweisführung auf eine gemeinsame Basis zu stellen. Über allem aber steht das Ziel, eine widerspruchsfreie und vollständige Mathematik zu schaffen, und zwar unter Verwendung eines formalen logischen Kalküls. Widerspruchsfreiheit und Vollständigkeit sind nun zwei zentrale Begriffe, die an dieser Stelle zunächst näher erläutert werden sollen. Widerspruchsfreiheit in einem Kalkül bedeutet, dass nicht gleichzeitig eine Aussage und deren Negation hergeleitet, d. h. bewiesen werden können. Fallss ein syntaktisch korrekter Satz in einem gegebenen Kalkül ist (was noch nichts über die Beweisbarkeit dieses Satzes aussagt), dann darf die Aussage s˄¬s nicht in dem Kalkül herleitbar sein. Nun wäre es scheinbar kein Problem, wenn dies bei einer einzigen Aussage auftreten würde, doch lässt sich ein einziges Mal eine solche widersprüchliche, d. h. falsche Aussage herleiten, dann kann in dem Kalkül jede beliebige Aussage hergeleitet werden. Die (syntaktische) Vollständigkeit besagt, dass für jeden Satz s eines Kalküls entweder s oder sein Negat ¬s herleitbar ist. Ist ein Kalkül vollständig, dann kann also für jede Aussage prinzipiell entschieden werden, ob sie herleitbar ist, d. h. bei einem gegebenen Modell (Interpretation), ob die Aussage wahr ist oder nicht. Unter der Annahme, man hat ein Kalkül, mit dem man die gesamte Mathematik beschreiben kann, folgt aus der syntaktischen Vollständigkeit, dass jede mathematische Aussage prinzipiell entscheidbar ist. Man hat damit also so etwas wie ein mathematisches Orakel, dem man eine beliebige Aussage vorlegt, und erhält als Antwort, ob die Aussage wahr oder falsch ist. So etwas wäre zweifellos der Traum eines jeden Mathematikers, aber auch Naturwissenschaftlers, denn die Mathematik ist die Basis aller Naturwissenschaften. Dabei ist offensichtlich, dass die Vollständigkeit nur in Kombination mit der Korrektheit Sinn macht, denn ohne Korrektheit ist jede Folgerung eines Kalküls wertlos.

 

Kehren wir zu David Hilbert zurück. Sein Anspruch, ein vollständiges und widerspruchsfreies Kalkül zu entwickeln, ist zweifellos ein erstrebenswertes Ziel. Und er verfolgt es mit großem Einsatz und Vehemenz. In einer bekannten Rede sagt er [Hilbert 1930]: „Wir dürfen nicht denen glauben, die heute mit philosophischer Miene und überlegenem Tone den Kulturuntergang prophezeien und sich in dem Ignorabimus gefallen. Für uns gibt es kein Ignorabimus, und meiner Meinung nach auch für die Naturwissenschaft überhaupt nicht. Statt des törichten Ignorabimus heiße im Gegenteil unsere Losung [John Stillwell 2013]: Wir müssen wissen und wir werden wissen.“ Doch noch während Hilbert diese Rede vorträgt, hält ein junger Mathematiker einen zunächst wenig beachteten Vortrag, der die Welt der Logik und Mathematik für immer verändert: Kurt Gödel.

 

Unvollständigkeit in der Logik

Viele Mathematiker schließen sich zu Beginn des 20. Jahrhunderts der Suche von Hilbert an, dennalle wollten den goldenen Gral der Mathematik finden. So liefert Mojżesz Presburger 1929 denBeweis dafür, dass ein Kalkül basierend auf ganzen Zahlen und der Addition vollständig ist. Dieses Kalkül, heute Presburger-Arithmetik genannt, kann jedoch nur einen recht kleinen Teil der Mathematik darstellen. Zur gleichen Zeit arbeitet jedoch Gödel an der so genannten Peano- Arithmetik, kurz PA. Es handelt sich hierbei scheinbar um einen ebenfalls kleinen Teil der Mathematik, da sie der Presburger-Arithmetik unter Hinzunahme der Multiplikation entspricht. Das Gegenteil ist jedoch der Fall. PA ist ein überaus mächtiges Kalkül, das, wie wir später sehen werden, der Ausdrucksfähigkeit eines beliebigen Computers entspricht. Für dieses Kalkül beweist Gödel zunächst 1929 die (semantische) Vollständigkeit. Diese semantische Vollständigkeit bedeutet, dass eine Aussage, die in allen Modellen des Kalküls wahr ist, auch in dem Kalkül hergeleitet werden kann. Durch diesen Erfolg angespornt versucht Gödel auch die syntaktische Vollständigkeit von PA zu beweisen. Das Ergebnis ist jedoch ernüchternd: Er zeigt stattdessen, dass PA unvollständig ist.1 In seinem berühmt gewordenen 1. Gödelschen Unvollständigkeitssatz beweist er nicht nur, dass PA unvollständig ist, sondern er kann sogar eine konkrete Aussage angeben, die in PA weder bewiesen noch widerlegt werden kann. In seinem 2. Unvollständigkeitssatz beweist Gödel weiterhin, dass die Konsistenz von PA, das heißt, deren Widerspruchsfreiheit, nicht innerhalb des Kalküls bewiesen werden kann.

 

Diese Ergebnisse erschütterten die Welt der Mathematik, denn sie rührten an ihren Grundfesten. Um dies besser zu verstehen, wollen wir das Ergebnis und die daraus folgenden Konsequenzen genauer untersuchen. Der 1. Unvollständigkeitssatz von Gödel lässt sich weiter verschärfen: Jedeendlich (d. h. durch ein endliches Verfahren) axiomatisierbare Erweiterung von PA ist unvollständig. Das Problem an PA ist also nicht eine zu schwach ausgefallene Ausstattung mit Axiomen, die sich durch eine geeignete Erweiterung einfach beseitigen ließe. Man überschreitet im Gegenteil – hervorgerufen durch die für PA hinzugekommenen Axiome – eine Grenze zu einem sehr mächtigen Teil der Mathematik, der es erlaubt, Aussagen zu formulieren, deren Wahrheitswert nicht mehr bestimmt werden kann. Wählt man die Axiome etwas schwächer, z. B. durch Weglassen der Axiome für die Multiplikation, so kann für jede Aussage deren Wahrheitswert bestimmt werden. In PA ist das aber nicht mehr möglich. Nun ist aber gerade die Überprüfung der Wahrheit einer Aussage das zentrale Ziel der Mathematik. Somit stellt sich sehr schnell die Frage, ob man einen Weg aus diesem Dilemma finden kann.

 

Betrachtet man die Verschärfung des 1. Unvollständigkeitssatzes, so fällt das Wort „endlich“ bei einer Erweiterung um Axiome auf. Könnte dies eine Hintertür sein, um die Aufgabe zu bewältigen? Grundsätzlich ist zu beachten, dass die Anzahl der Axiome durchaus unendlich sein kann und trotzdem der Satz noch gültig ist, d. h. das Kalkül nicht vollständig gemacht werden kann. „Endlich“ bedeutet hier, dass es möglich sein muss, ein endliches Verfahren anzugeben, das diese Axiome erzeugt (aufzählt), etwa durch ein Computerprogramm. Was würde nun geschehen, wenn man geeignete Axiome verwenden würde, die sich nicht mehr endlich erzeugen ließen? In diesem Fall erhielte man eine vollständige Erweiterung von PA. Allerdings stellt das keine Lösung für das Problem dar, da es keine Möglichkeit gibt, diese Axiome zu erzeugen, denn gäbe es diese, dann hätte man ja ein endliches Verfahren, das sie benennt, und man unterläge folglich wieder dem Unvollständigkeitssatz, unter der Annahmen, dass die Church-Turing-These stimmt (siehe unten).

 

Die aktuelle Forschung beschäftigt sich damit, die zusätzlichen Axiome so auszuwählen, dass bereits durch eine geringe Anzahl die Ausdrucksfähigkeit stark erhöht wird. Diese mächtigeren Kalküle erlauben z. B. die Konsistenz der jeweils schwächeren Kalküle zu beweisen. Um ihre eigene Konsistenz zu beweisen, werden allerdings wieder noch mächtigere Kalküle benötigt – eine Kette, die nicht endet. Ein anderes Problem entsteht bei dem schrittweisen Hinzufügen weiterer Axiome. Bestimmte Sätze, die man in einem gegebenen Kalkül beweisen will, sind aber in diesem Kalkül nicht herleitbar. Dass dieser Umstand eintritt, folgt zwingend aus dem Unvollständigkeitssatz. Eine Frage, deren Wahrheitswert man bestimmen, d. h. beweisen wollte, muss in diesem Fall mit Hilfe eines weiteren Axioms festgelegt werden. Ein prominentes Beispiel hierfür ist die so genannte Kontinuumshypothese (CH). In der berühmten Liste der 23 ungelösten mathematischen Probleme, die David Hilbert auf dem internationalen Mathematikerkongress 1900 in Paris vorträgt, steht die Kontinuumshypothese an erster Stelle. Es handelt sich also zweifellos um eine Frage, die Mathematiker gerne beantwortet haben wollen. Worum geht es dabei? In der Mathematik unterscheidet man unendliche Mengen bezüglich ihrer Mächtigkeit (sehr informell ausgedrückt, geht es bei der Mächtigkeit um die „Anzahl“ von Elementen einer Menge). Die unendliche Menge mit der geringsten Mächtigkeit sind die natürlichen Zahlen. Man spricht hier auch von abzählbar unendlich, da man alle Elemente nacheinander abzählen kann, auch wenn diese Abzählung nie zu einem Ende kommt. Die reellen Zahlen dagegen können nicht abgezählt werden. Das bedeutet, es gibt kein Verfahren, mit dem man nacheinander alle reellen Zahlen abzählen könnte. Man bezeichnet sie deshalb als überabzählbar. Die Frage ist nun, gibt es eine Unendlichkeitzwischen den natürlichen Zahlen und den reellen Zahlen? Die Kontinuumshypothese besagt nun, es gibt keine Menge, deren Mächtigkeit zwischen der Mächtigkeit der natürlichen Zahlen und der Mächtigkeit der reellen Zahlen liegt. Aus den Ergebnissen von Kurt Gödel (1938) und Paul Cohen (1960) folgte nun, dass die CH nicht aus der sogenannten Zermelo-Fraenkel-Mengenlehre mit Auswahlaxiom (ZFC)2 hergeleitet werden kann – genauso, wie auch ihre Negation nicht hergeleitet werden kann. In dieser Situation ist der Mathematiker also aufgefordert, aufgrund seiner Erfahrung und Intuition zu entscheiden, ob die CH gültig ist, also der Mengenlehre hinzugefügt werden soll – oder nicht, dann muss ihr Negat hinzugefügt werden. Eine Entscheidung muss aber zwingend getroffen werden, wenn man ein vollständiges System erhalten möchte.

 

Fassen wir noch einmal zusammen. Man kann mit endlichen Mitteln kein formales System entwickeln, das vollständig ist oder seine eigene Konsistenz beweisen könnte. Es wird also immer Fragen in der Mathematik geben, die in dem gegebenen System nicht beantwortet werden können. Wie geht man mit dieser Situation um? Die Antwort aus der Mathematik ist mehr als überraschend. S. Barry Cooper z. B. schreibt in [Cooper 2004, S. 124]: „So, is Hilbert's Programme completely killed of by Gödel's Theorem? No – we still can argue that all the mathematics we really need to know is computably derivable3, via a suitable axiom system, say.“ Gödel formuliert es in [Gödel 1995, S. 307] so: „It is safe to say that 99.9 % of present-day mathematics is contained in the first three levels of this hierarchy4. So for all practical purposes, all of mathematics can be reduced to a finite number of axioms.“ Der Mathematiker wird hier zum Pragmatiker. Diese Argumentation kann in den letzten Jahren in vielen wissenschaftlichen Veröffentlichungen gefunden werden. Wenige scheinen die Grundlage und die Tragweite der Argumentation zu bedenken. Eine seltene Ausnahme macht hier Gödel selbst, wenn er im Anschluss an den oben zitierten Abschnitt nochmals auf die Wahl der 99.9 % eingeht: „However, this is a mere historical accident, which is of no importance for the questions of principle. Moreover, it is not altogether unlikely that this character of present-day mathematics may have something to do with another character of it, namely, its inability to prove certain fundamental theorems ...“. Eine wichtige These, auf die wir später nochmals eingehen werden.

 

Als weitere Alternative sucht man die Lösung des Problems in der Intuition des menschlichen Geistes5. Da nachweislich kein Formalismus eine vollständige Bestimmung aller mathematischen Aussagen erlaubt, nutzen wir die Leistungsfähigkeit des Menschen. Hierzu muss, neben der Annahme, der menschliche Geist übersteige die Möglichkeiten jedes formalen Systems, zusätzlich angenommen werden, die Theoreme, die Menschen herleiten, seien (immer) korrekt. Denn ohne die zugesicherte Korrektheit wären sie wertlos. Potenziell falsche Theoreme müssten dann zu ihrer Überprüfung, wie in den empirischen Wissenschaften üblich, falsifizierbar sein. Hierzu wäre es aber notwendig, sie in einer wie auch immer gearteten formalisierten Form zu beschreiben. Zu einem solchen Formalismus würde sich dann aber auch wiederum ein Kalkül beschreiben lassen, das dann notwendigerweise unvollständig wäre. Da der Anspruch an die Korrektheit menschlicher Schlussfolgerung für viele doch sehr hoch gegriffen ist, schlägt Gödel deshalb einen pragmatischen Weg vor: „...or in other terms, we could perceive to be true only one proposition after the other, for a finite number of them. The assertion, however, that they are all true could at most be known with empirical certainty, on the basis of a sufficient number of instances ...“ [Gödel 1995, S. 309].

 

Alle vorgestellten Alternativen sind nicht sehr befriedigend oder Erfolg versprechend, es sei denn, man zieht sich auf den Standpunkt zurück, nur die (für den Mathematiker) interessanten Aussagen zu untersuchen. Welche der heute offenen mathematischen und naturwissenschaftlichen Fragen aufgrund dieser Problematik nicht verstanden sind, ist offensichtlicherweise nicht bekannt. Auch ist nicht bekannt, ob durch diese Begrenzung ein vollständiges Beschreiben der Naturgesetze nicht möglich ist. Aus philosophischer Sicht kann aber schon an dieser Stelle gesagt werden, dass eine platonistische Sichtweise der Mathematik6 grundsätzlich nicht mehr möglich ist, unabhängig davon, ob man diese Sichtweise präferiert. Es gibt definitiv Dinge, die nicht erkannt werden können – auch wenn bis heute kein Beispiel für eine Aussage gefunden wurde, die absolut unbeweisbar ist.7

 

Die Grenzen der Berechenbarkeit

Parallel zu den Veränderungen in der Mathematik entsteht in den dreißiger Jahren des letzten Jahrhunderts eine neue Wissenschaftsdisziplin, die Informatik. Innerhalb weniger Jahre entstehen mehrere mathematische, d. h. formal definierte, Modelle von Computern. Das Neue an dieser Entwicklung ist die freie Programmierbarkeit. Sie ermöglicht es, gegenüber früheren Versuchen wie die von Pascal und Leibniz, eine beliebige mathematische Rechenvorschrift zu nehmen, diese in die Sprache des jeweiligen Rechnermodells umzusetzen und dort auszuführen. Dabei erfolgt die Ausführung der Programme zunächst nicht auf realen Rechnern, denn zu dieser Zeit können diese Modelle auch nicht ansatzweise realisiert werden. Den ersten funktionstüchtigen programmgesteuerten Rechenautomaten der Welt baut Konrad Zuse 1941, wobei die mathematischen Modelle von Church (λ-Kalkül) und Turing schon 1933 bzw. 1936 vorgestellt werden. Trotz der enormen Entwicklung, die seit dieser Zeit bei Rechnern stattfindet, ist zu beachten, dass selbst heute keines dieser theoretischen Modelle umsetzbar ist – denn sie setzten potenziell (abzählbar) unendlich viel Speicher voraus. Damit ist auch in der Zukunft nicht zu erwarten, dass jemals ein solcher Rechner realisiert werden kann.8 Das Besondere an den Entwicklungen in den dreißiger Jahren ist die rasante Durchdringung des neuen Gebietes. Man beschäftigt sich nicht nur mit den Fragen, was man berechnen kann, sondern stellt schon sehr früh die Frage, was nicht berechnet werden kann. Turing hat bereits 1936, also gleichzeitig mit der Einführung der Turingmaschine, die Antwort auf diese Frage gefunden: Er gibt ein konkretes Beispiel für eine nicht berechenbare Funktion an.

 

Um sein Vorgehen und die sich daraus ergebenden Konsequenzen besser zu verstehen, müssen wir uns erst einige Grundlagen ansehen. Zur Verdeutlichung soll die Turingmaschine dienen, an der aufgrund ihrer einfachen Struktur vieles gut erklärt werden kann. Dabei hat, wie wir später sehen werden, die Auswahl des Rechnertyps keine Auswirkung auf die Ergebnisse. Jede Turingmaschine besteht aus einer Anzahl von Aktionen, einer endlichen Menge von Zuständen und einem Speicher – neben dem Programm natürlich. Der Speicher wird als potenziell unendlich angenommen, da ein endlicher Speicher die Mächtigkeit, d. h. die Menge an berechenbaren Funktionen, signifikant einschränken würde.9 Den Speicher der Turingmaschine stellt man sich wie ein endloses Band vor, das an einer Stelle von einem Schreib- /Lesekopf modifiziert bzw. gelesen wird. Das Band ist in Zellen eingeteilt, die leer oder mit einem Strich versehen sind. Die Aktionen sind so gewählt, dass alle gewünschten Funktionen berechnet werden können. Erstaunlich ist, mit wie wenigen und dabei einfachen Aktionen man auskommt. Insgesamt verfügt eine Turingmaschine über fünf Aktionen, die dabei noch sehr elementar sind. Eine Aktion ist z. B. die aktuelle Speicherzelle des Bandes mit einem Strich zu versehen oder den Lesekopf um eine Position nach links oder rechts zu verschieben. Eingaben, d. h. Folgen von Strichen, die Zahlen repräsentieren, werden zu Beginn von extern, also dem „Anwender“, auf das Band geschrieben. Nach dem Ende der Berechnung10 wird das Ergebnis auf das Band, nun als Ausgabemedium verwendet, geschrieben. Die Striche auf dem Band kodieren in einfacher Form natürliche Zahlen: Die Anzahl der Striche entspricht der Zahl. Der Trick an der Verwendung von natürlichen Zahlen ist, dass man andere Arten von „Objekten“ mit ihnen kodieren kann; ein Verfahren, das heute in allen Bereichen der Digitaltechnik angewandt wird. Niemand wundert sich heute mehr darüber, dass Texte, Musik, Bilder und Filme von einem Rechner verarbeitet werden, wo ein Rechner doch nur mit (binären) Zahlen arbeiten kann. Der Begriff Rechner wird gar nicht mehr verwendet, da die Verwendung eines Computers intuitiv nichts mit Rechnen zu tun hat. Aber hinter all dem steht die Idee, einem Buchstaben, einer Farbe oder einer Intensität eine Zahl, d. h. einen Code, zuzuordnen und diese Zahl dann zu verarbeiten.

 

Turing nun kodiert aber nicht Texte oder Bilder, sondern Programme, also die Folge von Aktionen, die eine Turingmaschine zum Leben erweckt. Diese Kodierung ermöglicht es, Programme als Eingaben eines (anderen) Programms zu verwenden, denn sie stellen damit genauso Zahlen als Eingabe dar, wie bei einer „normalen“ Berechnung. Hierzu entwickelt er ein Universalprogramm, das im Stande ist, das kodierte Eingabeprogramm wieder zurück in seine Befehle zu zerlegen und diese dann schrittweise auszuführen.11 Was ist nun das Entscheidende an diesem Ansatz? Das Universalprogramm erlaubt es nicht nur, Programme auszuführen, sondern auch deren Eigenschaften automatisiert zu untersuchen. Wie wir noch sehen werden, gibt es eine ganze Reihe wichtiger Eigenschaften von Programmen, aber Turing stellt eine spezielle Frage, deren Tragweite zunächst nicht offensichtlich ist: Terminiert ein Programm bei einer gegebenen Eingabe, d. h., überführt der Ablauf des Programms die Maschine in einen speziellen Haltezustand? Um die Reichweite der vermeintlich einfachen Frage zu verstehen, kehren wir an die Ausgangsfrage zurück: Gibt es Funktionen, die nicht berechnet werden können? Turing beweist, dass das Halteproblem, also die Frage, ob ein beliebiges Programm zusammen mit einer Eingabe nach endlicher Zeit anhält, nicht berechenbar ist.

 

Den Beweis führt Turing über einen Widerspruch. Er nimmt an, es gäbe ein Universalprogramm, das das Halteproblem lösen könne. Dann konstruierte er daraus ein spezielles Universalprogramm: Dieses nahm das zu untersuchende Programm, zusammen mit seiner Eingabe, und untersuchte es. Falls es feststellte, dass es terminiert, dann sollte das Universalprogramm in eine Endlosschleife gehen, also nicht terminieren. Wenn das zu untersuchende Programm nicht terminiert, dann sollte das Universalprogramm eine „1“ auf das Band schreiben und anhalten. Nach all der Vorbereitung können wir die eigentliche, interessante Frage stellen: Was geschieht, wenn dieses Universalprogramm seine eigene Kodierung als Eingabe bekommt – hält es an oder nicht? Nehmen wir an, es hielte, dann würde das Universalprogramm aufgrund seiner Konstruktion in eine Endlosschleife gehen und nicht anhalten. Nehmen wir an, das Programm hielte nicht an, dann würde das Universalprogramm anhalten und „1“ als Ergebnis liefern. Wir haben also in jedem Fall einen Widerspruch. Dieser Widerspruch kann nur an der falschen Annahme liegen, es gäbe das Universalprogramm. Folglich gibt es kein Turingprogramm, das das Halteproblem lösen kann. Allgemeiner formuliert: Wir haben eine Funktion natürlicher Zahlen gefunden, die mit einer Turingmaschine nicht berechnet werden kann.

 

Hier schließen sich nun einige wichtige Fragen mit weitreichenden Folgen an: Gilt diese Aussage nur für Turingmaschinen, oder hat sie allgemeine Gültigkeit – und was bedeutet dann ein verallgemeinerter Begriff der Berechenbarkeit? Gibt es neben dem Halteproblem andere, interessantere Funktionen, die nicht berechnet werden können? Beginnen wir mit der ersten Frage, da sie Grundlage für alles Weitere ist. Parallel zu Turing entstehen auch andere Formalisierungen von Rechnerkonzepten, so z. B. das λ-Kalkül und μ-rekursive Funktionen. Zum einen beweist man, dass alle Funktionen, die in einem Konzept darstellbar sind, auch in den anderen Konzepten dargestellt werden können. Man weist also die Äquivalenz der Konzepte nach – eine Tatsache, die aufgrund der Unterschiedlichkeit nicht offensichtlich ist. Diese Äquivalenzbetrachtungen werden naturgemäß in den danach folgenden Jahrzehnten fortgesetzt, doch mit unverändertem Ergebnis. Alle weiteren Konzepte lieferten keine zusätzlichen Ausdrucksmöglichkeiten und waren zu den bekannten äquivalent. Doch wie sollte man den Beweis führen, dass es keine mächtigeren Konzepte gibt? In Ermangelung eines solchen Beweises formuliert man eine These, die heute Church-Turing- These genannt wird: „Die Klasse der Turing-berechenbaren Funktionen ist genau die Klasse der intuitiv berechenbaren Funktionen.“ Nimmt man diese These als richtig an, und davon gehen heute praktisch alle Wissenschaftler aus, so ergeben sich daraus zwei wichtige Folgerungen: Zum ersten sind alle Rechnermodelle für Untersuchungen zur Berechenbarkeit gleichwertig und können somit beliebig gewählt werden. Neben dieser mehr technischen Folgerung ist aber entscheidend, dass man anhand eines beliebigen Konzeptes alle Möglichkeiten der Berechenbarkeit in einer allgemeingültigen Form untersuchen kann.

 

Damit kann nun die Frage nach weiteren, nicht berechenbaren Funktionen gestellt werden. Um es gleich vorweg zu nehmen, es sind sehr viele. In der Literatur wurden im Laufe der letzten 70 Jahre mehrere tausend nicht berechenbare Funktionen beschrieben. Viele davon betreffen eher spezielle Probleme, andere dagegen sind sehr grundsätzlich und haben weitreichende Auswirkungen, z. B. auch für Mathematik und Physik. Teilweise ist die scheinbare Einfachheit von unlösbaren Aufgaben fast erschreckend. Als ein Beispiel hierfür soll das sogenannte Game of Life dienen. Man kann es sich wie ein Spielfeld mit einem regelmäßigen Gitter vorstellen. Jedes Element auf dem Feld ist entweder lebendig oder tot, der Zustand des ganzen (potenziell unendlich großen) Spielfeldes wird Generation genannt. Das Game of Life beginnt mit einer beliebig wählbaren Generation und läuft dann anhand der Regeln mit einer Folge von sich daraus ergebenden Generationen ab. Insgesamt gibt es vier Regeln: Wenn sich in der direkten Nachbarschaft einer lebenden Zelle weniger als zwei lebendige Zellen befinden, dann stirbt sie aus Einsamkeit. Sind mehr als drei Nachbarn vorhanden, dann stirbt sie wegen Überbevölkerung, bei zwei und drei Nachbarn bleibt die Zelle am Leben. Eine tote Zelle mit genau drei Nachbarn wird in der Folgegeneration geboren. Diese Regeln sind nicht wirklich komplex, und man würde nicht erwarten, hier ein unberechenbares System vor sich zu haben. Nun gibt es einige interessante Fragen zu dem Verhalten von Generationen: Kann von einer gegebenen Generation aus eine andere, vorgegebene Generation erreicht werden? Oder gibt es Generationen, die von einer Anfangsgeneration aus nicht erreicht werden können?12 Für beide Fragestellungen existiert kein Verfahren, das eine Antwort für beliebige Konfigurationen beantworten könnte.

 

Berechenbarkeit hat in der Informatik große Bedeutung. Hier geht es ja in der täglichen Softwareentwicklung um Fragen wie: Wird eine gegebene Variable korrekt vorbesetzt? Wird eine bestimmte Stelle eines Programms erreicht? Liefern zwei Programme das gleiche Ergebnis? Hat das Programm minimale Größe? Ganz zu schweigen von der Frage, ob ein Programm gemäß einer vorgegebenen Spezifikation implementiert wurde. Alles Fragen, deren Lösung in der Praxis mehr als nützlich wären. Auch hier gibt es kein Verfahren – und wird es auch nie geben –, das eine dieser Fragen für ein beliebiges Programm beantworten kann. Aufgrund dieser Situation geht man in der Informatik mittlerweile pragmatisch an diese Aufgabenstellungen heran und versucht mit Hilfe von Heuristiken, wenigstens Näherungen zu bekommen. Jeder Computeranwender hat schon mehrfach mit den Konsequenzen dieser unvollständigen Ansätze zu tun gehabt, wenn ein Programm nicht mehr reagiert oder der ganze Computer hängt oder abgestürzt ist. In Deutschland gibt es sogar Gerichtsurteile, die festhalten, dass es keine korrekten Programme gibt. Und es mag überraschen, dass eine Beweisführung der Korrektheit bereits bei kleinen Programmen scheitern kann. Das ist einer der wenigen Fälle, wo die Berechenbarkeit sogar schon Einzug in das Rechtswesen gefunden hat.

 

Das wohl bekannteste Beispiel für Unberechenbarkeit aus der Mathematik sind die diophantischen Gleichungen. Der Name geht auf den griechischen Mathematiker Diophantus von Alexandria zurück, der vermutlich im 3. Jahrhundert n. Chr. lebte und als „Vater der Algebra“ gilt. In seinem berühmten Werk Arithmetica beschäftigte er sich mit der Lösung für Polynome rationaler Zahlen.13Solche Polynome sind Funktionen, die aus der Schulmathematik bekannt sind. Hierzu einige Beispiele. X12 − X2 = 0 besitzt als Lösung die Zahlenpaare (1,1), (2,4), (-2,4), (3,9), (-3,9), usw., allgemein: (±n,n2). X16 + X22 + X310 = − 7 besitzt keine Lösung, da die linke Seite der Gleichungimmer ≥ 0 ist. 4X = 5 besitzt keine Lösung, da bei diophantischen Gleichungen nur ganzzahlige Lösungen gesucht sind. Formal definiert man die Aufgabe wie folgt: Gesucht ist ein Verfahren, das bestimmt, ob es ganzzahlige Lösungen für f(x1,x2,x3,...,xn) = 0 gibt, wobei f eine Polynomfunktion mit ganzzahligen Koeffizienten ist. Diese Aufgabe ist das 10. Problem aus Hilberts berühmter Liste von 1900. 1970 findet Juri Wladimirowitsch Matijassewitsch den aufsehenerregenden Beweis dafür, dass diese Aufgabe nicht berechenbar ist. Das Erstaunliche ist auch hier wieder die Einfachheit der Aufgabe. Jeder kennt diese Art von Formel und ist im Stande, sie zu berechnen. Doch die Suche nach Nullstellen ist eine ganz andere Sache. Für viele Polynome kennt man natürlich Lösungen und schon Schüler lernen einige davon kennen, doch ein Verfahren für beliebige Polynome kann es nicht geben. Als Hilbert 1900 diese Aufgabe als Herausforderung für die Mathematiker stellte, hatte er größtes Vertrauen darauf, dass es nur eine Frage der Zeit sei, eine Lösung zu finden. Doch die Grundlagen der Mathematik haben sich anders entwickelt als angenommen.

 

Das Besondere an diophantischen Gleichungen ist ihre Ausdruckstärke, die sie trotz ihrer Einfachheit haben. Um dies zu erläutern, müssen wir zuerst den Begriff der berechenbaren Mengeneinführen. Eine berechenbare Menge ist der Wertebereich einer berechenbaren Funktion, also die Menge aller Zahlen, die eine Funktion zu ihren Eingaben liefert. Wenn man so etwas definiert, dann liegt es nahe, dass es nicht möglich ist, beliebige Mengen von ganzen Zahlen zu berechnen. Das ist auch so, wie sich aus der Tatsache ableiten lässt, dass es überabzählbar viele Mengen von ganzen Zahlen gibt, während es nur abzählbar viele berechenbare Funktionen geben kann. Berechenbare Mengen sind eine äquivalente Charakterisierung von Berechenbarkeit. Nun definiert jede diophantische Gleichung eine Menge, nämlich ihre Lösungsmenge, d. h. die Menge der ganzen Zahlen, für die die Gleichung gültig ist. Die entscheidende Aussage ist: Die Lösungsmengen diophantischer Gleichungen sind äquivalent zu der Menge der berechenbaren Mengen. Folglich kann zu jeder beliebigen berechenbaren Funktion eine diophantische Gleichung angegeben werden, die die gleiche Lösungsmenge hat. Man kann also jedes Programm als diophantische Gleichung formulieren, ein nicht offensichtlicher Zusammenhang. Doch damit nicht genug. Jedes naturwissenschaftliche Problem, das sich als eine beliebige, d. h. a priori nicht bestimmbare, diophantische Gleichung darstellen lässt, ist auch nicht berechenbar.

 

Dem aufmerksamen Leser mag sich die Frage aufdrängen, warum es so viele nicht berechenbare Funktionen gibt, während es in der Logik bisher nicht gelungen ist, eine nicht beweisbare Aussage zu finden. Der Grund hierfür liegt in der etwas anderen Fragestellung. Die Aufgabe, die der Informatiker stellt, ist schwieriger als die Frage des Logikers. Der Logiker fragt nach der Wahrheit einer Aussage. Um die Fragestellung der Logik leicht mit der Aufgabestellung der Informatik vergleichen zu können, wählen wir folgende Form: f(x) = y, wobei x und y vorgegeben sind. Der Logiker will dabei wissen, ob für gegebene x und y die Aussage wahr ist. Der Informatiker dagegen sucht nach einem y für ein beliebiges x. Das ist eine deutlich anspruchsvollere Aufgabe. Während bei der Überprüfung der Wahrheit eine Aussage untersucht wird, muss im Falle der Berechnung eine Funktion gefunden werden, die für alle x ein geeignetes Ergebnis liefert. Dieser Unterschied ist aber nur formaler Natur und täuscht die leichtere Lösbarkeit mathematischer Fragen vor. Man kann nämlich jede Funktion als eine (unendliche) Menge von Zahlenpaaren auffassen. Man nimmt einfach zwei beliebige Zahlen und setzt sie in x und y ein und fragt nach der Wahrheit dieser Aussage; so erhält man die Formulierung der Logik. Könnte also die Logik den Wahrheitswert all dieser so erzeugten Aussagen bestimmen, dann könnte man auf diese Weise auch jede Funktion berechnen. Hieraus folgt unmittelbar, dass der Wahrheitswert nicht für alle Aussagen bestimmt werden kann. Für Logiker (und Mathematiker) stellen diese beliebigen Zahlenpaare jedoch keine interessante Fragestellung dar. Folglich machen sie sich über die Unberechenbarkeit keine Gedanken.

 

Wir haben bisher gesehen, dass es berechenbare Funktionen, aber auch nicht berechenbare Funktionen gibt. Um ein Gefühl dafür zu bekommen, wie viele Funktionen diese beiden Gruppen enthalten, wollen wir uns die arithmetische Hierarchie ansehen. Die arithmetische Hierarchie ordnet Aussagen (Formeln) bzgl. ihrer Komplexität von berechenbaren, hin zu immer unberechenbareren Ausdrücken an. Dabei bezieht sich Komplexität hier nicht darauf, wie komplex ihre Struktur ist, sondern wie „zeitaufwändig“ die Berechnung der Aussage ist.14 Die entscheidende Ursache für dieKomplexität von logischen Ausdrücken sind die verwendeten Quantoren ∃ und ∀. Aus Sicht der Informatik kann man sie sich wie eine unendliche Schleife über alle möglichen Werte einer Variablen vorstellen. Die einfachsten Aussagen haben keine Quantoren bzw. lassen sich in einer Form ohne Quantoren darstellen.15 Sie werden mit Σ0 und Π0 bezeichnet, wobei der Index 0 anzeigt, dass keine Quantoren verwendet werden. Diese Klasse bildet die unterste Stufe in der Hierarchie, und aus ihr werden die höheren Stufen iterativ erzeugt:

 

Falls φ äquivalent zu einer Aussage ∃ xΨ ist, wobei Ψ zur Klasse Πn gehört, dann gehört φ zu Σn+1.

 

Falls φ äquivalent zu einer Aussage ∀ xΨ ist, wobei Ψ zur Klasse Σn gehört, dann gehört φ zu Πn+1.

 

In anderen Worten sind die Aussagen in Σn äquivalent zu Aussagen, die mit einem Existenzquantor beginnen und dann n-1 Mal in Folge Allquantor und Existenzquantor abwechseln. Analog beginntdie Folge bei Πn mit einem Allquantor.

 

Nach diesen Vorbereitungen kommt nun die interessante Frage nach der Berechenbarkeit derAussagen in den unterschiedlichen Stufen der arithmetischen Hierarchie. Die unterste Stufe, Σ0 undΠ0, ist vollständig berechenbar. Diese Ausdrücke entsprechen den sog. total berechenbaren Funktionen, das sind Funktionen, die für jede beliebige Eingabe ein Ergebnis liefern. Endlosschleifen, die das Halteproblem hervorrufen, treten hier nicht auf. Das ist also genau die Art von Funktionen, die man sich wünscht, und es wäre schön, wenn alle Funktionen in diese Klasse gehören würden. Doch leider ist dem nicht so. Die erste Stufe mit höherer Komplexität ist dieKlasse Σ1. Das sind Ausdrücke mit einem16 Existenzquantor. Es geht hier also um die Frage, ob es (mindestens) einen Wert gibt, für den ein gegebener Ausdruck wahr wird. Man muss also alle Werte systematisch überprüfen, bis die Aussage bei einem Wert wahr wird – oder auch nie. Im Sinne von Funktionen bedeutet dies, die Funktion terminiert, wenn ein Wert gefunden wird, rechnet aber unendlich lange, falls es keinen solchen Wert gibt. Diese Klasse von Funktionen wird partiell berechenbar genannt, da sie teilweise terminiert. Damit hat man eine Klasse, die immerhin teilweise ein Ergebnis liefert. Damit kommen wir zu der nächstkomplexeren Klasse, nämlich Π1. Hier ist die Gesamtaussage wahr, wenn für alle Werte der Variable, über die quantifiziert wird, die Unteraussage wahr ist. Da man aber nicht unendlich viele Fälle überprüfen kann, wird man nie eine wahre Aussage als Ergebnis erhalten können. Im besten Fall bekommt man das Ergebnis falsch, nämlich dann, wenn es ein Gegenbeispiel gibt. Es handelt sich also um Aussagen, die nie (als wahr) berechnet werden können. Geht man nun in der Hierarchie weiter nach oben, dann wird die Situation nicht besser, sondern man erhält Ausdrücke, die immer noch unberechenbarer werden – und das bis ins Unendliche. Von dieser Hierarchie kann also nur die unterste Klasse total berechnet werden, die erste Stufe ist partiell berechenbar, alles andere ist nicht berechenbar. Der Statistiker würde es so formulieren: Wenn man zufällig einen Ausdruck auswählt, dann ist er mit Wahrscheinlichkeit 1 nicht berechenbar. Ein recht ernüchterndes Ergebnis.

 

Um aus diesem Dilemma herauszukommen, könnte man sich überlegen, die Rechnermodelle, in unserem Fall die Turingmaschine, durch mächtigere Konzepte zu erweitern – ungeachtet dessen, ob so etwas in diesem Universum machbar ist.17 Zunächst sind die Ein- und die Ausgabe einer Turingmaschine endlich. Hieraus folgt, dass keine Berechnungen auf reellen Zahlen ausgeführt werden können. Hier wäre allerdings die Frage, wie eine solche reelle Zahl eingegeben werden könnte. Weiterhin sind die Programme und die Programmzustände endlich. Dies stellt eine weitere signifikante Einschränkung dar. Aber auch hier stellt sich die Frage, wer ein unendliches Programm schreiben könnte. Davon abgesehen würde uns ein unendliches Programm nur eine Stufe in der arithmetischen Hierarchie weiter nach oben bringen. Mit diesem geringen Mehrwert ist unendlicher Aufwand wohl nicht zu rechtfertigen. Um sich diese Problematik noch einmal anders zu verdeutlichen: Es gibt überabzählbar viele Funktionen ganzer Zahlen. Diese könnte man selbst mit einem (abzählbar) unendlichen Programmspeicher nicht darstellen.

 

Die markanteste Einschränkung ist die Berechnungsdauer: Ein Programm muss nach endlich vielen Schritten terminieren und ein Ergebnis liefern – oder für immer weiter rechnen, ohne irgendein Ergebnis zu liefern. Nun hat man bereits sehr früh untersucht, welche Auswirkungen es auf die Berechenbarkeit hätte, wenn man diese Grenze der endlichen Ausführungsschritte verschieben könnte [Turing 1939]. In der Zwischenzeit sind ganz unterschiedliche theoretische Modelle hierzu entstanden. Man kann es sich vereinfacht so vorstellen: Das erweitere Turing-Modell ist in der Lage, unendlich viele Rechenschritte auszuführen, und kommt danach an eine festgelegte Programmzeile, in der der Ausgang der unendlichen Berechnungsfolge untersucht wird. Da man hiermit die Wahrheit unendlich vieler Ausdrücke überprüfen kann, ist eine solche „beschleunigte“ Turingmaschine in der Lage, Σ1- und Π1 -Formeln auszuwerten. Für Σ2- und Π2 -Formeln reicht die Beschleunigung um eine Unendlichkeit nicht mehr aus, da man zwei verschachtelte Quantoren hat. Hier muss die Turingmaschine zweimal unendlich viele Anweisungen in endlicher Zeit ausführen. Mit jeder weiteren unendlichen Anzahl von Operationen steigt man also um eine Stufe in der arithmetischen Hierarchie auf. Um alle Ausdrücke berechnen zu können, braucht man also unendlich oft unendlich viele Rechenschritte – das ist ziemlich viel. Hätte man diese Rechenleistung zur Verfügung, dann – aber auch nur dann – könnte man das berechnen, was mittrue first order Arithmetic bezeichnet wird. Doch davon sind wir weit entfernt. In [Cooper 2004, S. 204] wird die true first order logic so bewertet: „It is of course far from being computably axiomatisable, and its set of theorems is so far from being Σ1 that it cannot be described in the language of PA using any number of quantifiers.“

 

Folgerungen und Ausblicke

In der Wissenschaft sind nach wie vor zwei extreme Haltungen zu finden, unabhängig davon, ob die Erkenntnisse von Entscheidbarkeit und Berechenbarkeit beachtet werden. Auf der einen Seite steht der Ignorabimus, der in der viel diskutierten Rede von Heinrich du Bois-Reymond 1872 postuliert wird [Bois-Reymond 1871]. Er sagt über den Wissenschaftler: „Im Rückblick auf die durchlaufene siegreiche Bahn trägt ihn [...] das stille Bewußtsein, daß, wo er jetzt nicht weiß, er wenigstens unter Umständen wissen könnte, und dereinst vielleicht wissen wird. Gegenüber dem Rätsel aber, was Materie und Kraft seien, und wie sie zu denken vermögen, muß er ein für allemal zu dem viel schwerer abzugebenden Wahrspruch sich entschließen: Ignorabimus.“ Du Bois-Reymond konkretisiert den Ignorabimus in seinem Vortrag von 1880 auf 7 Welträthsel [Bois-Reymond 1880]. Er benennt hier beispielsweise das Bewusstsein als eine nicht formalisierbare Erfahrung.

 

Als extreme Gegenposition tritt hier David Hilbert auf. In seinem schon zitierten Vortrag [Hilbert 1930] sagt er: „Wir dürfen nicht denen glauben, die heute mit philosophischer Miene und überlegenem Tone den Kulturuntergang prophezeien und sich in dem Ignorabimus gefallen. Für uns gibt es kein Ignorabimus, und meiner Meinung nach auch für die Naturwissenschaft überhaupt nicht. Statt des törichten Ignorabimus heiße im Gegenteil unsere Losung: Wir müssen wissen, wir werden wissen.“

 

Doch wie sieht die Situation heute aus, nachdem die Ergebnisse von Gödel weiterentwickelt wurden und die Ergebnisse der Informatik, ausgehend von Turing, hinzugekommen sind? Wir wollen die Folgerungen vorsichtig und schrittweise ziehen, denn zu viel Falsches wurde in den vergangenen Jahrzehnten aus den Unvollständigkeitssätzen gefolgert – auch von schillernden Persönlichkeiten der modernen Wissenschaft [Franzen 2005]. Beginnen wir mit du Bois-Reymond. Hier muss klar die Frage nach der Begründung für seine 7 „Welträthsel“ gestellt werden. Die Grundlage hier ist ausschließlich die Intuition, genauer gesagt der Mangel an Wissen, aus dem ein Nicht-Wissen-Können abgeleitet wird. Das ist keine tragbare Basis, unabhängig davon, ob die Annahmen falsch oder richtig sind. Auf der Gegenseite ist die Haltung von Hilbert genauso wenig haltbar. Denn hier ist grundsätzlich gezeigt, dass mathematische Erkenntnis begrenzt ist. Dieser Nachweis wurde mittlerweile sogar für unterschiedliche Bereiche geführt.

 

Unsere Aufgabe wird also sein, den Bereich zwischen den beiden Extrempositionen noch klarer zu zeichnen. Unsere Kritik an du Bois-Reymond basiert ja auf seiner fehlenden Begründung. Genau hier liegt aber die Chance – und Aufgabe – der Berechenbarkeitsforschung. Wir können heute Probleme benennen, die nicht berechenbar sind. Doch diese Forschung steckt noch immer in den Anfängen, da die zugrundeliegende Mathematik teilweise extrem anspruchsvoll ist. So erforderte der Beweis zur Unlösbarkeit von Hilberts 10. Problem Jahrzehnte an intensiver Forschung und der Zusammenarbeit führender Mathematiker. Ein gutes Verständnis der Grenzen der Berechenbarkeit wird nachhaltigen Einfluss auf den Umgang mit heute noch ungelösten Problemen haben. Momentan wird intensiv in Bereichen geforscht, die potenziell nicht berechenbar sind. Hierzu gehören Hirnforschung, Psychologie, Soziologie, Ökonomie und Biologie, um nur einige zu nennen. Allein schon das Bewusstsein, es könne sich hier um unentscheidbare Probleme handeln, würde dem Dialog zwischen Wissenschaft und Philosophie / Theologie manche Schärfe nehmen.

 

Sehen wir uns die Position Hilberts noch etwas genauer an. Hier wird im Wesentlichen folgendermaßen argumentiert: 99,9 % aller interessanten Teile der mathematischen Fragen lassen sich heute axiomatisieren, und das fehlende „‰“ lässt sich sicher auch noch lösen. Hierzu gibt es eine Reihe Gegenargumente, auf die hier eingegangen werden soll. Was den fehlenden Teil betrifft, so spricht zunächst der Gödelsche Unvollständigkeitssatz dagegen. Um hier einen Ausweg zu finden, der effektiv (berechenbar) ist, darf der fehlende Teil nur eine Untermenge der Mathematik umfassen, denn sonst würde man ein nicht mehr berechenbares Axiomensystem benötigen. Hieraus folgt direkt die Reduktion der Mathematik auf eine „Ingenieurwissenschaft“ – die Ingenieure mögen diesen Vergleich verzeihen. Die Mathematik verliert also ihren Anspruch auf die Suche nach (potenziell allen) mathematischen Wahrheiten und begnügt sich in dieser Begrenzung. Der Ansatz von Gödel [Gödel 1995, S. 309], die Mathematik in eine empirische Wissenschaft umzuwandeln, verstärkt den Eindruck der Ingenieurwissenschaft. Der andere Kritikpunkt bezieht sich auf die Angabe, 99,9 % der interessanten Probleme seien potenziell beweisbar. Hier weist beispielsweise Gödel [Gödel 1995, S. 307] darauf hin, dass diese Zahl einen rein historischen Hintergrund hat und sich nur aus den heute gestellten Fragen ergibt. Den Prozentsatz der lösbaren mathematischen Fragen subjektiv festzulegen, stellt keine belastbare Aussage dar und kann nicht Gegenstand einer Diskussion über dieses Themengebiet sein. Es sei nochmals betont, dass sich darüber hinaus die 99,9 % nicht auf alle wahren Aussagen beziehen, sondern auf den Teil davon, der für Mathematiker interessant ist. Von allen Aussagen über mathematische Objekte werden immer unendlich mal mehr unbeweisbar bleiben als solche, die (potenziell) beweisbar sind. Anders formuliert, im statistischen Sinne sind 0 % (auf beliebig viele Stellen genau) der mathematischen Aussagen formal beweisbar.

 

Noch klarer sieht die Situation im Falle der Berechenbarkeit aus. Hier sind hinreichend viele unberechenbare Funktionen bekannt, einschließlich solcher mit praktischen Auswirkungen in viele Wissenschaften. Dabei ist es wichtig, sich nochmals den Unterschied zwischen Beweisbarkeit (Logik) und Berechenbarkeit (Informatik) klar zu machen. Während in der Logik die Wahrheit einer grundlegenden Aussage untersucht wird, beschäftigt sich die Informatik damit, zu einerbeliebigen (d. h. aktuell vorliegenden) Situation eine Aussage abzuleiten. Wenn also z. B. für ein gegebenes physikalisches System eine Vorhersage gemacht werden soll, etwa in welchem Zustand es sich in 10 Sekunden befindet, dann ist Informatik (Berechenbarkeit) gefragt. Das gleiche gilt für Medizin, Psychiatrie oder Ökonomie, also jeden Bereich, bei dem grundsätzlich Computer eingesetzt werden könnten. Damit stellt Unberechenbarkeit, eine sehr reale Beschränkung unserer Erkenntnis und damit auch unserer Handlungsfähigkeit dar. Selbst wenn die Mathematiker 100 % der für sie interessanten Aussagen axiomatisieren könnten, würde die Unberechenbarkeit noch deutliche Schranken der Erkenntnis vorgeben.

 

Unter diesem Vorzeichen gibt es natürliche vielfältige Überlegungen, ob diese Grenze wirklich endgültig ist. Die eine Richtung geht von der Überlegenheit des menschlichen Geistes über die Rechenmodelle aus, die andere Richtung versucht, die Leistungsfähigkeit der Rechenmodelle über die Turingmaschine hinaus zu entwickeln. Nehmen wir an, der menschliche Geist übersteigt die Leistungsfähigkeit der Turingmaschine. In diesem Fall muss es Aussagen geben, die wahr sind und in keinem formalen System beweisbar sind. Solche Aussagen wurden bisher allerdings nicht gefunden. Beispiele, die in der Literatur benannt werden, beziehen sich auf ein konkretes Kalkül, typischerweise PA. Diese Beispiele haben natürlich keine Aussagekraft, da die verwendeten Kalküle nicht vollständig sind, genauer gesagt, weil Kalküle bekannt sind, in denen diese Aussagen auch formal beweisbar wären. Es fehlt also bisher ein Existenzbeweis. Weiterhin ist zu beachten, dass ein „Vermitteln“ oder „Einsichtig-Machen“ solcher intuitiven Wahrheiten ein im weitesten Sinne formales System erfordert. Dies widerspricht der Annahme des nicht-formellen Beweises. Schließlich ist auch die Frage zu klären, welche Mechanismen in unserem Gehirn zu einer Leistung führen könnten, die über die Leistung eines Computers hinausgeht. Komplexität alleine kann es nicht sein, denn hier sind die theoretischen Rechnermodelle schon reichlich bestückt, z. B. mit unendlich viel Speicher. Auf der anderen Seite ist aber auch klar zu sagen, dass es eine Reihe von Leistungen des menschlichen Geistes gibt, für die keine Ansätze zu Erklärungen vorliegen. Als ein Beispiel hierfür sei die Fähigkeit herausgegriffen, geeignete Axiome einzuführen, wenn bestimmte Aussagen nicht mehr beweisbar sind. Wie kommt der Mensch auf den Gedanken, klären zu wollen, ob es zwischen abzählbar unendlich und überabzählbar unendlich keine weiteren Unendlichkeiten gibt? Solche Fragen haben eine so hohe Abstraktion, dass sie alle bisher untersuchten Konzepte künstlicher Intelligenz bei Weitem übersteigen.

 

Bleibt damit die Frage, ob es gelingt, die Grenzen einer Turingmaschine zu überwinden. Ansätze, die hier vorgeschlagen werden, basieren auf Quanteneffekten und versuchen die Rechengeschwindigkeit ins Unendliche zu steigern. Unter der Annahme, dies würde gelingen – was von vielen als nicht realistisch angesehen wird –, stiege man in der arithmetischen Hierarchie um eine Stufe nach oben. Man würde also für das normale Rechnen sehr viel hinzugewinnen (Bemerkung: Diophantische Gleichungen wären z. B. dann berechenbar), das Problem der Unberechenbarkeit wäre aber nur verschoben, denn man stiege nur um eine Stufe in der arithmetischen Hierarchie auf.

 

Zum Abschluss wollen wir noch einmal zusammenfassen und einige Thesen aufstellen. Der Anspruch der Wissenschaft einer vollständigen Beschreibung der Wirklichkeit oder gar des im platonistischen Sinne darüber Hinausgehenden lässt sich heute nicht mehr rechtfertigen. Nicht alle Grenzen sind bereits bekannt, aber sie werden durch die Forschung immer klarere Formen annehmen. Manch einer mag sie als sehr störend wahrnehmen, denn sie rütteln an manch einem Weltbild. Sie stellen definitiv eine Enttäuschung bzgl. des Anspruchs von Hilbert dar. Falls dies aber im positiven Sinne zu einer Ent-Täuschung wird, dann können falsche Grundannahmen über Bord geworfen werden. So könnten diese Grenzen den alleinigen Wahrheitsanspruch der Wissenschaften relativieren und somit im Dialog mit Religionen Türen wieder öffnen. Der Weg auf der Suche nach der Wahrheit ist damit nach wie vor schwierig, aber auf eine tragfähigere Basis gestellt.

 

Fußnoten

 

Literatur

• [Cooper 2004] S. Barry Cooper, Computability Theory, Chapman & Hall/CRC, 2004.
• [Bois-Reymond 1872] Emil du Bois-Reymond, Über die Grenzen des Naturerkennens, 1872, Nachdruck u.a. in: Emil du Bois-Reymond: Vorträge über Philosophie und Gesellschaft, Hamburg, Meiner, 1974.
• [Bois-Reymond 1880] Ders.: Die sieben Welträthsel, 1880, Nachdruck u.a. in: Emil du Bois- Reymond: Vorträge über Philosophie und Gesellschaft, Hamburg, Meiner, 1974.
• [Feferman 2010] Solomon Feferman (Herausgeber), Charles Parsons (Herausgeber), Stephen G. Simpson (Herausgeber), Kurt Gödel: Essays for His Centennial (Lecture Notes in Logic), Cambridge University Press, 2010.
• [Franzen 2005] Torkel Franzen, Gödel's Theorem – An Incomplete Guide to its Use and Abuse, A K Peters, 2005.
• [Gödel 1995] Kurt Gödel (Autor), Solomon Feferman (Herausgeber), Jr., John W. Dawson (Herausgeber), Warren Goldfarb (Herausgeber), Charles Parsons (Herausgeber), Robert M. Solovay (Herausgeber), Kurt Gödel: Collected Works 3: Unpublished Essays and Lectures Vol 3, Oxford University Press, 1995.
• [Henn, 2003] Hans Wolfgang Henn, Elementare Geometrie und Algebra, Vieweg+Teubner Verlag, 2003.
• [Hilbert 1930] David Hilbert, Naturerkennen und Logik, Vortrag auf dem Kongress der Gesellschaft Deutscher Naturforscher und Ärzte, Königsberg, 1930.
• [Kant 1781] Immanuel Kant, Kritik der reinen Vernunft, Wissenschaftliche Buchgesellschaft, 1983. [Pensore 1989] Roger Penrose, The Emperor's New Mind: Concerning Computers, Minds, and the
• Laws of Physics, Oxford University Press, 1989.
• [Petzold 2008] Charles Petzold, The Annotated Turing: A Guided Tour Through Alan Turing's
• Historic Paper on Computability and the Turing Machine, Wiley Publishing, Inc., 2008.
• [John Stillwell 2013] John Stillwell, Wahrheit, Beweis, Unendlichkeit: Eine mathematische Reise zu
• den vielseitigen Auswirkungen der Unendlichkeit, Springer Spektrum, 2013.
• [Turing 1939] Alan Turing, Systems of logic based on ordinals, Proc. London Math. Soc., 45, 1939.