Unentscheidbare Probleme
Diophantische Gleichungen und Hilberts zehntes Problem
Computerprogramme und diophantische Gleichungen
Passende diophantische Gleichungen konstruieren
Eine diophantische Gleichung für Primzahlen
Diophantische Gleichungen und Gödels Unvollständigkeitssatz
Als Gödel im Jahr 1931 seinen berühmten Unvollständigkeitssatz bewies, tat er dies, indem er eine bestimmte Aussage in der Sprache der Peano-Arithmetik definierte und von dieser Aussage bewies, dass sie innerhalb der Peano-Arithmetik nicht aus den Axiomen abgeleitet werden kann, wenn die Peano-Arithmetik widerspruchsfrei ist (siehe Kapitel 2.5). Diese Aussage erschien allerdings vielen Mathematikern damals als sehr speziell konstruiert, denn sie ließ sich interpretieren als "ich bin nicht beweisbar".
Alan Turing zeigte fünf Jahre später (1936), dass mechanische Rechenverfahren (d.h. Algorithmen oder Computerprogramme) ihre Grenzen haben, und dass es Probleme gibt, die nicht algorithmisch lösbar sind (siehe Kapitel 2.3). Dazu musste Turing zunächst genau definieren, was ein mechanisches Rechenverfahren ist, denn bis dahin hatte man zwar eine intuitive Vorstellung davon, aber noch keine genaue mathematische Definition.
Turings wichtigstes Ergebnis war, dass das Halteproblem unlösbar ist, d.h. dass es keinen Algorithmus gibt, der für jedes Computerprogramm entscheiden kann, ob dieses Programm anhält oder nicht. Mit Hilfe des Representation Theorems kann man daraus ableiten, dass es in jedem hinreichend mächtigen formalen System (z.B. Peano-Arithmetik) kein Entscheidungsverfahren geben kann (siehe Kapitel 2.4). Die Frage, ob eine beliebige wohlgeformte Aussage innerhalb des Systems aus den Axiomen abgeleitet werden kann, lässt sich also nicht allgemein durch einen Algorithmus beantworten. Daraus folgt unmittelbar die Unvollständigkeit des formalen Systems. Gödels Unvollständigkeitssatz lässt sich auf diese Weise also auch ohne die Konstruktion der merkwürdigen "ich bin nicht beweisbar" -Aussage beweisen. Allerdings liefert dieser Beweis keine Beispiele für solche nicht-entscheidbaren Aussagen. Man sieht nur, dass es unendlich viele davon geben muss, und dass ihre Existenz eng mit der Unlösbarkeit von Turings Halteproblem verknüpft ist.
Wie wichtig sind nun solche unentscheidbaren Aussagen in der Mathematik? Treten sie häufig auf, oder handelt es sich bei ihnen um unwichtige Exoten?
In den letzten beiden Kapiteln (3.3 und 3.4) sind wir dieser Frage bereits etwas näher gekommen. So haben wir eine Familie von Zahlen kennengelernt, bei denen jedes formale System nur endlich viele (sagen wir \(n\)) Binärstellen berechnen kann. Alle Aussagen der Form "die \(m\)-te Binärstelle ist 1" (mit \(m > n\) ) sind dann innerhalb des formalen Systems nicht entscheidbar. Damit haben wir unendlich viele nicht-entscheidbare Aussagen gefunden.
Dennoch ist auch dieses Beispiel noch recht konstruiert. Es wäre schön, wenn es uns gelänge, mitten im Herzen der klassischen Mathematik ein Problem zu finden, das nicht extra so konstruiert wurde, dass es nicht entscheidbar ist, und das sich dennoch als nicht-entscheidbar herausstellt.
Es gelang tatsächlich im Lauf der Zeit, einige klassische Probleme der Mathematik als nicht-entscheidbar aufzudecken. Die bekanntesten Beispiele sind die folgenden:
Wir wollen uns in diesem Kapitel dem Beispiel zuwenden, mit dem sich schon die Griechen der Antike beschäftigten, und das sich lediglich mit natürlichen Zahlen sowie deren Addition und Multiplikation beschäftigt: die diophantischen Gleichungen.
Die diophantischen Gleichungen wurden nach dem griechischen Gelehrten Diophantus von Alexandrien benannt. Diophantus lebte etwa von 200 bis 284 nach Christus. Er wird oft als der Vater der Algebra bezeichnet. Sein bekanntestes Werk ist die Arithmetica, die sich mit der Zahlentheorie und mit der Lösung algebraischer Gleichungen beschäftigt. Die Arithmetica galt bis in die Neuzeit hinein als eines der bedeutensten mathematischen Werke der Menschheit.
Was sind diophantische Gleichungen?
Diophantische Gleichungen enthalten ausschließlich natürliche Zahlen, Variablen in diesen Zahlen sowie Multiplikationen und Additionen (bzw. Subtraktionen). Variablen dürfen auch miteinander multipliziert werden, d.h. Terme wie \(x^3\) oder \(x \cdot y\) sind erlaubt. Gesucht werden Lösungen dieser Gleichungen, d.h. Werte für die Variablen in den natürlichen Zahlen, so dass die Gleichung stimmt.
Betrachten wir einige Beispiele für Diophantische Gleichungen:
Die Gleichung \begin{equation} 2x - 2y = 1 \end{equation} hat keine Lösungen, denn es gibt keine natürlichen Zahlen, die wir für die Variablen \(x\) und \(y\) einsetzen könnten, so dass die Gleichung aufgeht. Der Grund dafür ist, dass auf der linken Seite immer die Differenz zweier gerader Zahlen steht, die damit selbst immer gerade ist. Rechts aber steht eine ungerade Zahl. Zwar löst beispielsweise die Kombination \( y = 1 \) und \( x = 3/2 \) die Gleichung, aber Brüche sind ja als Lösung nicht erlaubt – wir suchen natürliche Zahlen! Die Gleichung \( 3x = 6 \) hat dagegen genau eine Lösung in den natürlichen Zahlen, nämlich \(x=2\) .
Ein etwas komplizierteres Beispiel ist die Gleichung \begin{equation} 7x - 17y = 1 \end{equation} Diese Gleichung hat unendlich viele Lösungen, die man alle über die Formeln \( x = 17t + 5 \) und \( y = 7t + 2 \) erhält. In diesen Formeln muss man nun der Reihe nach \(t = 0, 1, 2, 3, ... \) einsetzen, um die Lösungspaare \( (x, y) \) zu erhalten. Das erste Lösungspaar ist also \( x = 5 \) und \( y = 2 \), das zweite lautet \( x = 22 \) und \( y = 9 \) und so weiter.
Man kann auch allgemein die lineare diophantische Gleichung \begin{equation} a x + b y = c \end{equation} mit vorgegebenen natürlichen Zahlen \(a, b\) und \(c\) betrachten. Es ist möglich, für diesen Gleichungstyp ein allgemeines Lösungsverfahren anzugeben, das die Lösbarkeit der Gleichung beantwortet und ggf. die Lösungen findet.
Schwieriger wird es bei diophantischen Gleichungen zweiten Grades in 2 Variablen, also \begin{equation} a x^2 + b x y + c y^2 + d x +e y + f = 0 \end{equation} mit vorgegebenen ganzen Zahlen für \(a, b, c, d, e, f \). Tatsächlich kann man auch für diese Gleichung mit den beiden Variablen \(x\) und \(y\) eine allgemeine Lösungsmethode angeben, die recht trickreich ist. Hier einige Links dazu:
Eine andere Sorte interessanter diophantischer Gleichungen sind die Gleichungen \begin{equation} x^n + y^n = z^n \end{equation} mit einer vorgegebenen natürlichen Zahl \(n\) . Die berühmte Fermatsche Vermutung, die bereits vor 350 Jahren aufgestellt wurde, lautet: nur für \(n = 1\) und \(n = 2\) besitzt die Gleichung Lösungen, nicht aber für \(n = 3, 4, ... \) . Erst im Jahr 1994 gelang es Andrew Wiles in einem heroischen Kraftakt, diese Vermutung zu beweisen. Der Beweis verwendet praktisch das gesamte moderne Arsenal der Zahlentheorie. Damit wird deutlich, wie schwierig es sein kann, die Frage nach der Lösbarkeit diophantischer Gleichungen zu beantworten.
Bis heute wurde keine Methode gefunden, beliebige diophantische Gleichungen dritten Grades zu lösen. Umso schwieriger wird es sein, eine allgemeine Methode zur Lösung vollkommen beliebiger diophantischer Gleichungen zu finden. Daher formulierte David Hilbert genau diese Aufgabe in seinem berühmten Vortrag aus dem Jahr 1900 als eine der großen Herausforderungen für das zwanzigste Jahrhundert:
Hilberts 10. Problem: Entscheidung der Lösbarkeit einer Diophantischen
Gleichung:
Eine Diophantische Gleichung mit irgend welchen Unbekannten und
mit ganzen rationalen Zahlenkoeffizienten sei vorgelegt: man soll ein
Verfahren angeben, nach welchem sich mittelst einer endlichen Anzahl von
Operationen entscheiden. läßt, ob die Gleichung in ganzen rationalen Zahlen
lösbar ist.
Mit ganzen rationalen Zahlen meint Hilbert die ganzen Zahlen ..., -2, -1, 0, 1, 2, ... . Man kann zeigen, dass man das Problem auch so umformulieren kann, dass die Lösungen in den natürlichen Zahlen (also ohne die negativen Zahlen) liegen müssen. Es spielt daher keine Rolle, ob wir ganze oder natürliche Zahlen als Variablenwerte zulassen.
Im Jahr 1900 war eine Lösung dieses Problems nur schwer möglich, denn man hatte noch keine genaue Definition davon, was mit dem von Hilbert beschriebenen Verfahren gemeint ist. Dies änderte sich erst im Jahr 1936, als Turing, Post und Church den Begriff Algorithmus (also mechanisches Rechenverfahren) einführten und präzisierten. Und mit der Einführung dieses Begriffes tauchte zugleich die Möglichkeit auf, dass nicht alle Probleme durch einen Algorithmus gelöst werden konnten. Existiert also ein allgemeines Verfahren zur Lösung diophantischer Gleichungen?
Die Beantwortung dieser Frage stellte sich als sehr schwierig heraus. Es dauerte bis zum Jahr 1970, als diese Frage durch Yuri Matiyasevich (aufbauend auf den Arbeiten von Martin Davis Hilary Putnam und Julia Robinson) endgültig beantwortet wurde:
Es hat also gar keinen Zweck, sich auf die Suche nach einem solchen Algorithmus zu machen, denn es gibt keinen. Es mag zwar möglich sein, das Problem für gewisse Klassen diophantischer Gleichungen zu lösen, aber jede dieser Klassen wird ihren eigenen Algorithmus benötigen, und manchmal wir man gar keinen Algorithmus finden. Das erklärt, warum das Lösen diophantischer Gleichungen selbst in einfachen Fällen so schwierig sein kann (man denke an die Fermatsche Vermutung).
Der Beweis für die Unlösbarkeit von Hilberts zehntem Problem ist sicher eine der herausragenden Leistungen der Mathematik des zwanzigsten Jahrhunderts. Dabei ist dieser Beweis trickreich und kompliziert, aber die Beweisidee ist einfach und schlägt eine Brücke zwischen zwei Teilgebieten der Mathematik, die vorher nicht miteinander verbunden waren. Wir wollen uns die Beweisidee daher näher ansehen.
Die Idee des Beweises besteht darin, eine Brücke zwischen rekursiv aufzählbaren Mengen aus natürlichen Zahlen und diophantischen Gleichungen zu schlagen.
Beginnen wir mit den rekursiv aufzählbaren Mengen. Eine rekursiv aufzählbare Menge aus natürlichen Zahlen ist nichts anderes als eine (ggf. unendliche) Liste natürlicher Zahlen, die sich durch ein Computerprogramm erzeugen lässt. Jedes Element der Menge taucht irgendwo in der Liste auf – man weiß allerdings nicht unbedingt, wo.
Man kann sich nun die Frage stellen, ob eine bestimmte Zahl in einer vorgegebenen Menge enthalten ist oder nicht.
Bei manchen Mengen gibt es einen Algorithmus, der in endlich vielen Schritten für eine beliebige Zahl eine Antwort auf diese Frage liefert (z.B. wenn das Computerprogramm zur Auflistung der Menge die einzelnen Zahlen in aufsteigender Folge ohne Wiederholungen ausgibt). Es gibt dann ein Entscheidungsverfahren für die Zugehörigkeit zu der Menge. Solche Mengen nennt man auch rekursiv, lösbar, berechenbar oder entscheidbar. Ein Beispiel für eine solche Menge ist die Menge aller Primzahlen.
Es gibt aber auch rekursiv aufzählbare Mengen, bei denen es keinen solchen Algorithmus gibt. Solche Mengen nennt man auch nicht rekursiv, unlösbar, nicht berechenbar oder nicht entscheidbar. Stattdessen gibt es einen Algorithmus, der nur dann garantiert eine Antwort liefert, wenn die Zahl zur Menge gehört. Gehört sie dagegen nicht zur Menge, so kann es passieren, dass der Algorithmus nicht anhält. Um zu entscheiden, ob eine Zahl in der Menge enthalten ist, muss dieser Algorithmus nämlich notfalls die Liste aller Zahlen der Menge Zeile für Zeile durchsuchen. Wenn die Zahl in der Menge enthalten ist, so wird man sie auf diese Weise in endlich vielen Schritten in der Liste finden. Falls sie aber nicht in der Liste ist, so sucht man ewig weiter (d.h. das Suchprogramm hält nicht an). Ein Beispiel für eine solche Menge ist die Liste aller anhaltenden Programme einer vorgegebenen Programmiersprache (wobei wir jedes Programm als Binärstring ansehen können und diesen Binärstring dann als Binärdarstellung einer natürlichen Zahl interpretieren können). Die Liste aller anhaltenden Programme lässt sich aufstellen, indem man zunächst eine Liste alle Programme mit maximal \(s\) Bit Größe aufstellt, die innerhalb von \(s\) Schritten anhält, anschließend \(s\) schrittweise vergrößert und die jeweils neu hinzukommenden Programme in die Liste einträgt. Auf diese Weise wird jedes anhaltende Programm irgendwann erfasst (wir hatten diese Vorgehensweise im vorigen Kapitel über Chaitins Zahl dazu verwendet, die Teilsummen \( \Omega^s \) zu berechnen). Ob ein vorgegebenes Programm jedoch anhält, weiß man im Allgemeinen nicht immer, und es gibt keinen Algorithmus, der diese Frage in allen Fällen beantwortet.
Was hat das Ganze nun mit diophantischen Gleichungen zu tun?
Betrachten wir dazu eine beliebige diophantische Gleichung, die wir als \begin{equation} P(x, n, y_1, ... , y_m) = 0 \end{equation} schreiben wollen. Dabei ist \(P\) ein Polynom mit ganzzahligen Koeffizienten, und \(x, n, y_1, ... , y_m \) sind natürliche Zahlen (inklusive Null). Wir wollen \(n\) als externen Parameter ansehen, d.h. wir geben eine natürliche Zahl für \(n\) vor und fragen nach der Menge \(D_n\) aller Werte für \(x\), für die es Werte der Variablen \( y_1, ... , y_m \) gibt, so dass die Gleichung \( P(x, n, y_1, ... , y_m) = 0 \) aufgeht.
Ein Beispiel: Wir betrachten die Gleichung \begin{equation} P(x,n,y) = 2x - 2y - n = 0 \end{equation} d.h. in diesem Fall gibt es nur eine \(y\)-Variable (deren Index wir deshalb einfach weglassen). Was geschieht nun, wenn für \(n\) eine gerade Zahl vorgegeben wird? In diesem Fall kann man zu jedem \(x > n/2 \) ein \(y\) finden, so dass die Gleichung \( 2x - 2y - n = 0 \) aufgeht – das sieht man am besten, wenn man die Gleichung als \( 2x - 2y = n \) umschreibt. Wenn \(n\) dagegen ungerade ist, so geht die Gleichung überhaupt nicht auf, denn die Differenz zweier gerader Zahlen \( 2x - 2y \) ergibt nie eine ungerade Zahl \(n\).
Ein anderes interessantes Beispiel ist die Gleichung \begin{equation} P(x,n,y) = x^2 + y^2 - n^2 = 0 \end{equation} oder umgeschrieben \(x^2 + y^2 = n^2\) . Beispielsweise enthält für \(n = 5\) die Lösungsmenge \( D_5 \) die beiden Werte \(x = 3\) und \(x = 4\), denn für diese beiden Werte kann man ein jeweils ganzzahliges \(y\) finden, so dass die Gleichung aufgeht (wegen \( 3^2 + 4^2 = 5^2 \) ). Für viele andere Werte von \(n\) ist dagegen die Lösungsmenge leer, da in diesen Fällen \(n^2\) nicht als Summe zweier Quadratzahlen geschrieben werden kann.
Wir sehen also, welche vielfältigen Möglichkeiten sich eröffnen. Je nachdem, welche diophantische Gleichung man betrachtet, wird man ganz unterschiedliche Lösungsmengen \(D_n\) erhalten. Es zeigt sich sogar, dass die Vielfalt der möglichen Lösungsmengen extrem groß ist, denn man kann folgenden Satz beweisen:
Wenn man also irgendein Computerprogramm betrachtet, das eine endliche oder unendliche Liste natürlicher Zahlen ausgibt, so kann man eine natürliche Zahl \(n\) finden, so dass diese Liste die \(x\)-Lösungsmenge \( D_n \) der Gleichung \( P(x, n, y_1, ... , y_m) = 0 \) mit dem universellen Polynom \(P\) ist.
Man kann also die diophantische Gleichung \( P(x, n, y_1, ... , y_m) = 0 \) durch geeignete Wahl des Parameters \(n\) immer so konstruieren, dass für jede natürliche Zahl \(x\) aus einer beliebig erzeugten Computer-Zahlenliste immer natürliche Zahlen \(y_1, ... , y_m\) existieren, so dass die Gleichung aufgeht. Für alle Werte von \(x\), die nicht in der Liste enthalten sind, findet man dagegen keine passenden natürliche Zahlen für \(y_1, ... , y_m\) .
Dieses Ergebnis ist sehr beeindruckend! Es bedeutet, dass man jeden Algorithmus zur Erzeugung von Zahlenlisten umwandeln kann in eine diophantische Gleichung, die als Lösungsmenge für \(x\) dieselbe Liste ergibt. Lösen der diophantischen Gleichung ergibt dieselbe Zahlenmenge wie das Laufenlassen des Algorithmus.
Damit ist aber auch klar, dass sich die Probleme der computererzeugbaren Zahlenlisten (also der rekusiv aufzählbaren Mengen natürlicher Zahlen) auf die Lösungsmengen der diophantischen Gleichungen übertragen. So können wir die Frage stellen: "Ist die vom Programm erzeugte Zahlenliste leer oder nicht leer?" Leider kann man diese Frage nicht immer beantworten, denn man kann ja nie wissen, ob ein Programm, das die Zahlenliste generieren soll, aber bisher noch keine einzige Zahl ausgegeben hat, in der nächsten Sekunde nicht doch die erste Zahl der Liste ausgeben wird. Wir wissen nur, dass wenn die Liste nicht leer ist, dann das Programm in endlich vielen Schritten die erste Zahl der Liste ausgeben wird. Solange das Programm aber weiterläuft, ohne dass es eine Zahl ausgegeben hat, solange wissen wir nicht, ob die Liste leer oder nicht leer ist. Die Unlösbarkeit von Turings Halteproblem beweist, dass es keinen Algorithmus geben kann, der für jedes Programm ermittelt, ob es jemals eine Zahl in die Liste schreibt (es könnte ja danach anhalten) oder nicht. Da jede solche Zahlenliste zugleich die Lösungsmenge einer diophantischen Gleichung ist, kann es auch keinen allgemeinen Algorithmus geben, der in jedem Fall ermitteln kann, ob diese Lösungsmenge leer ist oder nicht. Hilberts zehntes Problem ist daher unlösbar. Wir werden weiter unten diesen Punkt noch präziser darstellen.
Wie kann man sich nun die Konstruktion des oben genannten universellen Polynoms \(P\) vorstellen?
Man beginnt mit einer beliebigen rekursiv aufzählbaren Menge natürlicher Zahlen – nennen wir sie \(M\). Zu dieser Menge \(M\) gibt es dann einen Algorithmus (nennen wir ihn \(B_M\)), der die Liste aller Elemente dieser Menge Schritt für Schritt ausgeben kann. Diesen Algorithmus können wir beispielsweise als Turingprogramm aufstellen. Wir können nun die folgende berechenbare Funktion \(f_M\) definieren:
Wenn die Zahl \(x\) zur Menge \(M\) gehört, so muss es irgendein \(s\) geben, so dass \(f_M(x,s) = 1\) ist, denn \(x\) muss ja irgendwann durch den Algorithmus \( B_M \) ausgegeben werden.
Das Representation Theorem (siehe Kapitel 2.4) sagt nun, dass diese berechenbare Funktion \(f_M(x,s)\) in der Peano-Arithmetik (bzw. generell in einem hinreichend mächtigen formalen System) durch eine wohlgeformte Aussage \(A_M(x,s)\) dargestellt werden kann, wobei \(A_M(x,s)\) beweisbar ist, wenn \( f_M(x,s) = 1 \) ist, und ihr Gegenteil \(\neg A_M(x,s)\) beweisbar ist, wenn \( f_M(x,s) = 0 \) ist. Wenn nun \(x\) zur Menge \(M\) gehört, so muss es ein \(s\) geben, so dass die Aussage \(A_M(x,s)\) beweisbar ist. Wenn \(x\) dagegen nicht zur Menge gehört, so gibt es kein solches \(s\):
Damit haben wir die Zugehörigkeit zur Menge \(M\) in die Sprache der Peano-Arithmetik übersetzt. Der Ausdruck \(A_M(x,s)\) ist dabei ein sehr kompliziertes Konstrukt, das den Algorithmus \(B_M\) in die Sprache der Peano-Arithmetik überträgt.
Der Rest der Konstruktion besteht nun darin, die Aussage \( \exists s: A_M(x,s) \) so umzuwandeln, dass am Schluss eine Aussage der Form \begin{equation} \exists y_1 ... \exists y_m: P(x, n, y_1, ... , y_m) = 0 \end{equation} dasteht, wobei \(P\) ein Polynom mit ganzzahligen Koeffizienten ist. Diese Umwandlung ist nicht einfach, und der Teufel steckt im Detail!
Betrachten wir ein Beispiel dafür, welche Zwischenschritte in dieser Umwandlung stecken: Nehmen wir an, die Aussage \(A_M(x,s)\) enthält Teilstrings der Form \( A < B \) , wobei \(A\) und \(B\) bereits Polynome mit ganzzahligen Koeffizienten sind. Dann kann man diese Teilstrings umwandeln in Teilstrings der Form \( \exists y: A + y + 1 = B \). Dieser Teilstring hat bereits die gewünschte Form. Allerdings sind nicht alle Zwischenschritte so einfach. Eines der schwierigsten Probleme besteht z.B. darin, Teilstrings der Form \( \forall z \) loszuwerden.
So kompliziert der Beweis auch insgesamt ist, er liefert letztlich eine konkrete Vorschrift, wie ein Computerprogramm zur Erzeugung einer Zahlenliste in eine dazu gleichwertige diophantische Gleichung umgewandelt werden kann. Diese Vorschrift lässt sich programmieren, so dass die diophantische Gleichung jeweils explizit angegeben werden kann (sie kann allerdings recht lang und kompliziert werden). Gregory Chaitin hat genau dies für eine bestimmte LISP-Programmiersprache explizit durchgeführt.
Wir wollen uns als Beispiel eine ganz besondere Menge natürlicher Zahlen ansehen: die Primzahlen. Diese Menge ist sowohl rekursiv aufzählbar als auch rekursiv, d.h. man kann mit einem Computerprogramm die Menge der Primzahlen beliebig weit auflisten, und man kann bei jeder natürlichen Zahl immer entscheiden, ob sie eine Primzahl ist. Die Menge der Primzahlen ist insofern eine unproblematische Menge.
Man hat im Lauf der Geschichte lange versucht, eine Berechnungsformel für Primzahlen zu finden, also eine Funktion \(f(n)\), die die \(n\)-te Primzahl berechnet. Man weiß heute, dass es keine einfache Möglichkeit für eine solche Formel gibt. So kann \(f(n)\) kein Polynom mit ganzzahligen Koeffizienten sein.
Es muss aber eine diophantische Gleichung geben, so dass die entsprechende Lösungsmenge gleich der Menge aller Primzahlen ist. Tatsächlich gelang es im Jahr 1976, eine solche Gleichung zu finden (siehe J.P. Jones, Hideo Wada, Daihachiro Sato and Douglas Wiens: Diophantine representation of the set of prime numbers, Amer. Math. Monthly 83 (1976), 449-464. MR 54:2615. , PDF hier ).
Schauen wir uns dazu den folgenden komplizierten Ausdruck an:
Dieser Ausdruck ist ein Polynom 25-ten Grades in den 26 Variablen \( a \) bis \( z \), die natürliche Zahlen sind. Es ist ein wahrer Formelwust, für einen Menschen wie Sie und mich vollkommen unüberschaubar – zumindest auf den ersten Blick.
Dennoch haben Jones, Wada, Sato and Wiens in einem umfangreichen Beweis Folgendes gezeigt:
Wenn man die 26 Variablen der Reihe nach alle möglichen natürlichen Zahlen (inklusive Null) durchlaufen lässt, so durchläuft der Wert dieses Polynoms, sofern dieser Wert größer als Null ist, alle Primzahlen. Die Menge aller Primzahlen ist identisch mit der Menge der positiven Werte dieses Polynoms. Jeder positive Wert von \(f\) ist eine Primzahl, und umgekehrt kann man für jede Primzahl Werte der 26 Variablen \(a\) bis \(z\) innerhalb der natürlichen Zahlen (inklusive Null) finden, so dass der obige Ausdruck gerade diese Primzahl ergibt.
Um Primzahlen zu finden, muss man also positive Werte des Polynoms \(f(..)\) finden. Wenn man sich nun die Struktur von \(f\) näher ansieht, so erkennt man, dass \(f\) von der Form \begin{align} & f(a, b, c, ... , z) = \\ &= (k+2) \left\{ 1 - A_1^2 - A_2^2 - \, ... - A_{14}^2 \right\} \end{align} ist. Dabei ist beispielsweise \( A_1 = wz + h + j - q \) , also gleich der ersten eckigen Klammer, die quadriert wird. Man erkennt, dass das Polynom \(f\) nur dann einen positiven Wert annehmen kann, wenn alle vierzehn \(A_i\) gleich Null sind. Sind sie das nicht, so wird immer mindestens der Wert 1 abgezogen, d.h. die geschweifte Klammer \( \{ 1 - ...\} \) kann nicht größer als Null sein. Der Wert von \(f\) ist also in den meisten Fällen negativ. Positive Werte von \(f\) zu suchen ist also gleichbedeutend damit, das Gleichungssystem \begin{align} A_1 &= 0 \\ A_2 &= 0 \\ ... & \\ A_{14} &= 0 \end{align} für die 26 Variablen \(a\) bis \(z\) zu lösen.
Wenn man einen positiven Wert des Polynoms \(f\) gefunden hat, d.h. wenn alle vierzehn \(A_i\) gleich Null sind, so ist die geschweifte Klammer gleich Eins, und damit ist \begin{equation} f(a, b, c, ... , z) = (k+2) \end{equation} Wenn man also erst einmal das Gleichungssystem der vierzehn Gleichungen \( A_i = 0 \) gelöst hat und damit Werte für die 26 Variablen \(a\) bis \(z\) ermittelt hat ( \(k\) gehört auch zu diesen Variablen!), so ergibt jede mögliche Lösung für die Variable \(k\), wenn man sie um 2 erhöht, immer eine Primzahl, und jede Primzahl lässt sich als eine Lösung des Gleichungssystems auf diese Weise ermitteln.
Positive Werte des Polynoms \(f\) zu finden ist also identisch damit, die Gleichung \( f(a,b,c,...,z) = (k+2) \) in den natürlichen Zahlen zu lösen. Man kann den Term \( (k+2) \) auch auf die linke Seite der Gleichung bringen: \begin{equation} f(a, b, c, ... , z) - (k+2) = 0 \end{equation} Links steht insgesamt ein Polynom \( P(a,b,c,...,z) = f(a,b,c,...,z) - (k+2) \), und die Gleichung lautet \begin{equation} P(a,b,c,...,z) = 0 \end{equation} Diese Form entspricht genau der Gleichung \( P(x,n,y_1,..., y_m) = 0 \) , mit der wir diophantische Gleichungen und ihre Lösungsmenge \( D_n \) oben geschrieben haben. Der Term \( (k+2) \) entspricht dabei der Variable \(x\), und die anderen Variablen \(a\) bis \(z\) (ohne \(k\)) entsprechen den Variablen \( y_1,..., y_m \). Der Parameter \(n\) spielt hier keine Rolle. Die Lösungsmenge \( D_n \) ist die Menge aller Primzahlen. Da die Menge der Primzahlen rekursiv aufzählbar und zugleich rekursiv ist, muss es ein berechenbares Lösungsverfahren zur Lösung der Gleichung \( f(a,b,c,...,z) - (k+2) = 0 \) geben, mit dem sich im Prinzip alle Primzahlen ermitteln lassen. Es ist also tatsächlich möglich, die Primzahlen über eine diophantische Gleichung zu definieren und zu berechnen! Die großen Mathematiker der Geschichte wie Fermat und Euler wären über dieses Ergebnis sicher begeistert gewesen. Es zeigt sich allerdings, dass dieses Verfahren sehr aufwendig ist und sich deshalb nur wenig für die Suche nach Primzahlen eignet.
Das Beispiel der Primzahlen führte zu einer diophantischen Gleichung, für deren Lösungen es ein Rechenverfahren gibt, das alle Lösungen ermitteln kann. Es gibt jedoch auch diophantische Gleichungen, bei denen die Frage nach der Lösbarkeit nicht entscheidbar ist – wir hatten es oben bereits erwähnt und wollen uns nun im Detail ansehen, woran das liegt.
Wir haben oben gesehen, dass man zu jeder rekursiv aufzählbaren Menge natürlicher Zahlen eine diophantische Gleichung \( P(x, n, y_1, ..., y_m) = 0 \) finden kann, so dass die Lösungen für \(x\) genau dieser Menge entsprechen. Das Polynom \(P\) ist also ein universelles Polynom, das jeden Algorithmus repräsentieren kann, der eine endliche oder unendliche Liste natürlicher Zahlen ausgibt. Daher kann es sinnvoll sein, sich \( P(x, n, y_1, ..., y_m) \) so vorzustellen: \(n\) ist die Gödel-Nummer eines Programms zur Ausgabe einer Zahlenliste \(D_n\), die Menge der Lösungen \(x\) ist genau diese Zahlenliste \(D_n\), und die Hilfsvariablen \( y_1, ..., y_m \) sind interne Variablen des Programms, die nicht ausgegeben werden.
Da das Polynom universell ist, können wir es verwenden, um Gödels Unvollständigkeitssatz zu beweisen. Der Beweis ist vollkommen analog zu unseren Beweis der Unlösbarkeit von Turings Halteproblem aus Kapitel 2.3. Dazu schreiben wir noch einmal genau auf, was wir unter der Lösungsmenge \(D_n\) verstehen: \begin{equation} D_n = \left\{ x ; \; \exists y_1, ..., y_m : \, P(x, n, y_1, ..., y_m) = 0 \right\} \end{equation} In Worten: \(D_n\) ist die Menge aller natürlichen Zahlen \(x\), für die es Werte der Hilfsvariablen \( y_1, ..., y_m \) in den natürlichen Zahlen gibt, so dass \( P(x, n, y_1, ..., y_m) = 0 \) ist. Oder anders ausgedrückt: \(D_n\) ist die Zahlenliste, die das \(n\)-te Computerprogramm (das zur Gleichung \( P(x, n, y_1, ..., y_m) = 0 \) gehört) ausgibt.
Die Menge \(D_n\) entspricht dabei genau den berechenbaren (nicht unbedingt überall definierten) Funktionen \(f_n\) aus Kapitel 2.3. Dabei besteht die Menge Dn aus allen definierten Funktionswerten der Funktion \(f_n\). Man kann die Rechenvorschrift zur Berechnung der Funktionswerte leicht in eine Rechenvorschrift zur Ausgabe einer Liste aller Funktionswerte umwandeln. Dazu versucht man, die ersten \(s\) Funktionswerte \( f_n(k) \) mit \(k = 0\) bis \(s\) zu berechnen, wobei man das Programm für jeden Eingabewert \(k\) nur höchstens \(s\) Schritte lang laufen lässt. Alle Funktionswerte, die bis dahin berechnet wurden, kommen in die Liste. Diese Vorgehensweise wiederholt man dann immer wieder mit wachsendem \(s\). Auf diese Weise wird jeder Funktionswert, bei dem \(f_n\) definiert ist (d.h. das Programm hält an), irgendwann ausgegeben.
Wir können nun eine neue Menge (nennen wir sie \(V\) ) auf die folgende Weise konstruieren: Überprüfe bei jeder natürlichen Zahl \(n\), ob diese Zahl in der entsprechenden Lösungsmenge \(D_n\) enthalten ist (wir nehmen einmal probeweise an, dass das geht). Falls sie nicht enthalten ist, nimm sie in die neue Menge \(V\) auf.
\(V\) enthält also alle Zahlen \(n\), die nicht eine Lösung für die Variable \(x\) der \(n\)-ten Diophantischen Gleichung \(P(x,n,y_1,..., y_m) = 0 \) sind: \begin{equation} V = \left\{ n ; \; n \notin D_n \right\} \end{equation} Die Konstruktion dieser Menge entspricht dem Cantorschen Diagonalverfahren (ähnlich zur Konstruktion der Diagonalfunktion \(f_D\) in Kapitel 2.3).
Nun ist aufgrund ihrer Konstruktion die Menge \(V\) mit keiner der Mengen \( D_n \) identisch, denn wenn \(n\) ein Element von \( D_n \) ist, ist es kein Element von \(V\) und umgekehrt. \(V\) unterscheidet sich von jedem \( D_n \) zumindest bei der Zugehörigkeit der Zahl \(n\), die immer nur in genau einer der beiden Mengen vorhanden ist. Das aber bedeutet, dass die Menge \(V\) nicht rekursiv aufzählbar sein kann (d.h. nicht durch ein Computerprogramm aufgelistet werden kann), denn jede rekursiv aufzählbare Menge ist Lösungsmenge einer diophantischen Gleichung (d.h. die Liste aller Mengen \( D_n \) enthält jede rekursiv aufzählbare Menge natürlicher Zahlen). Es gibt also kein Computerprogramm, das die Elemente der Menge \(V\) auflisten kann.
Die Definition der Menge \(V\) kann also nicht zu einem solchen Computerprogramm genutzt werden. Demnach kann es also keinen allgemeinen Algorithmus geben, der in endlich vielen Schritten entscheiden kann, ob eine beliebige Zahl \(n\) zur Lösungsmenge \( D_n \) gehört. Die Aussage \( n \notin D_n \) ist also nicht für jedes \(n\) allgemein algorithmisch überprüfbar. Für jeden Algorithmus, der dies versucht, kann man natürliche Zahlen finden, bei denen er versagt.
Die Aussage \( n \notin D_n \) ist aber gleichbedeutend mit der Aussage "die Gleichung \(P(n, n, y_1, ..., y_m) = 0 \) besitzt keine Lösung in den Variablen \( y_1, ..., y_m \) ". Es gibt also keinen Algorithmus, der für jedes \(n\) herausfinden kann, ob die diophantische Gleichung \(P(n, n, y_1, ..., y_m) = 0 \) Lösungen besitzt oder nicht. Also kann es auch kein formales System geben, das diese Frage in allen Fällen beweisen oder wiederlegen kann, denn ansonsten könnten wir auf diese Weise einen entsprechenden Algorithmus programmieren. Dies ist eine weitere Variante von Gödels Unvollständigkeitssatz.
Wir sehen, dass unentscheidbare Aussagen keineswegs exotisch sein müssen. Gödels Aussage "Ich bin nicht beweisbar" aus Kapitel 2.5 ist nur ein extra konstruiertes Beispiel, aber keineswegs das Einzige. Sogar in klassischen Bereichen der Mathematik wie den diophantischen Gleichungen findet man unentscheidbare Aussagen. Es gibt Gleichungen in den natürlichen Zahlen, bei denen man aufgrund der mathematischen Axiome und den Regeln der Logik nicht entscheiden kann, ob sie Lösungen haben oder nicht. Man kann nicht beweisen, dass sie keine Lösungen haben, wird andererseits aber auch kein Gegenbeispiel finden. Interessanterweise kann man im Rahmen der üblichen Interpretation der Symbole in diophantischen Gleichungen in diesen Fällen sogar sagen, dass die Aussage "die Gleichung hat keine Lösungen" wahr ist, denn man kann kein Gegenbeispiel finden. Wahrheit bei unentscheidbaren Aussagen bedeutet dann, dass die Axiome es nicht zulassen, ein Gegenbeispiel zu konstruieren. Allerdings ist Wahrheit hier nicht identisch mit Beweisbarkeit, sondern nur mit Nicht-Widerlegbarkeit.
Literatur:
© Jörg Resag, www.joerg-resag.de
last modified on 04 March 2023