mit 
ein Polynom
mit ganzzahligen Koeffizienten
zuzuordnen, sodaß die Diophantische Gleichung
Günter Schachner
86 25 051
13. 12. 1997
Am Zweiten Internationalen Mathematikerkongreß im August 1900 in Paris präsentierte D. Hilbert eine Liste von 23 wichtigen ungelösten Problemen. Ein Problem wurde weltweit nach seiner Position in Hilberts Liste benannt: das zehnte Hilbertsche Problem.
Hilbert fragte dabei nach einem Algorithmus, der für jede polynomiale Diophantische Gleichung mit ganzzahligen Koeffizienten entscheidet, ob diese eine Lösung besitzt. Vom Standpunkt der Berechenbarkeit ist diese Problemstellung gleichbedeutend damit, nach nicht-negativen ganzzahligen Lösungen zu fragen. Es könnte nun natürlich sein, daß ein derartiger Algorithmus gar nicht existiert. Um aber ein solches Ergebnis zu beweisen, müssen wir über alle möglichen Algorithmen argumentieren, weshalb wir eine klare mathematische Definition des Begriffes ,,Algorithmus`` benötigen.
In den Dreißiger Jahren beschäftigten sich u.a. die Mathematiker und Logiker A. Church, K. Gödel, S. Kleene, E. Post und A. Turing mit dem Problem der Berechenbarkeit. Deren zum Teil sehr unterschiedliche Ansätze bezüglich der ,,Durchführbarkeit einer Rechnung`` erwiesen sich letztlich alle als äquivalent. Ein Algorithmus sei in der Folge ein Programm für eine Turing-Maschine. Formal berechnet eine Turing-Maschine genau die partiell-rekursiven Funktionen, die nach der These von Church eine adäquate Formalisierung des intuitiven Berechenbarkeitsbegriffes darstellen.
Der erste ernsthafte Ansatz zu seiner Lösung wurde 1950 von M. Davis
unternommen. Seine Strategie beruhte darauf, jeder
rekursiv aufzählbaren Menge S
von n-Tupeln mit ein Polynom
mit ganzzahligen Koeffizienten
zuzuordnen, sodaß die Diophantische Gleichung
genau dann eine Lösung besitzt, wenn in S liegt.
Der Schlüssel zur Lösung fand sich
schließlich in einer von J. Robinson begonnenen Arbeit. Gemeinsam mit
M. Davis und H. Putnam konnte sie 1960 obigen Sachverhalt zeigen,
wenn man anstelle von Polynomen sogenannte exponentielle Polynome
zuläßt, d.h. Konstanten und Variablen dürfen nicht nur
miteinander addiert und multipliziert, sondern auch zur Potenz erhoben
werden. Zehn Jahre später konnte
J. Matijasevic unter Verwendung von Methoden der
algebraischen Zahlentheorie schließlich zeigen, daß die Relation
durch eine polynomiale Diophantische Gleichung beschrieben
werden kann, d.h. obiger Sachverhalt ist nicht nur für exponentielle,
sondern auch für gewöhnliche Polynome richtig.
Dieses Ergebnis beweist, daß es keinen Algorithmus der von Hilbert geforderten Art gibt. Dies ist salopp gesprochen eine Konsequenz der Tatsache, daß wir alles, was wir mit Turing-Maschinen machen können, auf polynomiale Diophantische Gleichungen übertragen können. Insbesondere macht sich dort also auch das Halteproblem bemerkbar.
J. P. Jones fand ein explizites Beispiel (18 Gleichungen vom
Maximalgrad 
in 33 Variablen), für das kein Algorithmus
der von Hilbert geforderten Art
existiert. Für polynomiale Diophantische Gleichungen vom Maximalgrad 2
konnte C. L. Siegel 1972 einen Algorithmus angeben,
während für allgemeine polynomiale Diophantische Gleichungen vom Grad 4
bekannt ist,
daß im allgemeinen kein derartiger Algorithmus existiert. Einzig der
Fall kubischer Diophantischer Gleichungen ist damit noch offen.
Beachten Sie aber, daß es für bestimmte Typen
polynomialer Diophantischer
Gleichungen sehr wohl Algorithmen der gewünschten Art geben kann, auch wenn
deren Grad größer als 3 ist.
Eine Konsequenz des obigen Ergebnisses ist außerdem, daß wir jede rekursiv aufzählbare Menge ganzer Zahlen durch eine polynomiale Diophantische Gleichung beschreiben können. 1977 fanden J. P. Jones, D. Sato, H. Wada und D. Wiens beispielsweise das Polynom
dessen positive Werte genau die Primzahlen sind. Der Grad und die Anzahl der Variablen dieses Polynoms können noch gesenkt werden, allerdings nicht unabhängig voneinander. Die Anzahl der Variablen muß in jedem Fall aber größer als 2 sein.
Das zehnte Hilbertsche Problem
This document was generated using the LaTeX2HTML translator Version 96.1-e (April 9, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 n-schachner10h.
The translation was initiated by Wolfgang Slany on Fri Jan 9 15:15:07 MET 1998