eines der 23 Hilbertschen Probleme.

Es stellt die Frage nach einem Algorithmus zur Lösung von diophantischen Gleichungssystemen. Man kann dies als ein Entscheidungsproblem verstehen: Gegeben ist eine endliche Menge von Polynom-Gleichungen, gefragt ist, ob es eine Lö-sung dieser Gleichungen über den ganzen Zahlen gibt (und wenn ja, ist eine solche Lösung anzugeben). Eine erste einfache Reduktion des Problems besteht darin, festzustellen, daß es genügt, eine einzelne Polynomgleichung der Form \(P(\overrightarrow{x})=0\) zu betrachten.

Eine Menge A, die sich folgendermaßen über ein geeignetes Polynom P mit ganzzahligen Koeffizienten ausdrücken läßt \begin{eqnarray}x\in A\iff \exists \overrightarrow{y}\in {{\mathbb{Z}}}^{k}:P(x,\overrightarrow{y})=0\end{eqnarray}

heißt diophantisch. (Man vergleiche mit der Definition der arithmetischen Hierarchie, insbesondere mit den rekursivaufzählbaren Mengen \({\Sigma}_{1}^{0}\)).

Nach wichtigen Vorarbeiten von M. Davis, H. Putnam und J. Robinson in den 50er Jahren gelang Y. Matiyasevich 1970 der Beweis des Satzes, daß jede rekursiv aufzählbare Menge diophantisch ist. Die wichtigste Folgerung aus diesem Satz ist, daß eine allgemeine Lösung des zehnten Hilbertschen Problems unmöglich ist, da das betreffende Entscheidungsproblem unentscheidbar ist (Entscheidbarkeit, Berechnungstheorie).

Eine weitere interessante Folgerung ist, daß es zu jeder rekursiv aufzählbaren Menge A von natürlichen Zahlen (z. B. der Menge aller Primzahlen) ein Polynom \(P(\overrightarrow{x})\) gibt mit Koeffizienten aus Z, so daß A genau die Menge der nichtnegativen Werte ist, die \(P(\overrightarrow{x})\) für x ∈ ℤ^k annimmt.