Das zehnte Problem von Hilbert ist auf der Liste der Probleme von Hilbert von 1900 zehnt. Seine Behauptung ist wie folgt:

Eine Diophantine Gleichung ist eine Gleichung der Form

:

wo p ein Polynom mit Koeffizienten der ganzen Zahl ist. Man hat viele Jahre für das Problem gebraucht, mit einer negativen Antwort gelöst zu werden. Heute ist es bekannt, dass kein solcher Algorithmus im allgemeinen Fall besteht. Dieses Ergebnis ist die vereinigte Arbeit von Martin Davis, Yuri Matiyasevich, Hilary Putnam und Julia Robinson.

Formulierung

Die Wörter "Prozess" und "begrenzte Zahl von Operationen" sind genommen worden, um zu bedeuten, dass Hilbert um einen Algorithmus bat. Der Begriff "vernünftige ganze Zahl" bezieht sich einfach auf die ganzen Zahlen, positiv, negativ oder Null: 0, ±1, ±2.... So bat Hilbert um einen allgemeinen Algorithmus, um zu entscheiden, ob eine gegebene polynomische Gleichung von Diophantine mit Koeffizienten der ganzen Zahl eine Lösung in ganzen Zahlen hat. Wie man jetzt bekannt, ist die Antwort auf das Problem verneinend: Kein solcher allgemeiner Algorithmus kann bestehen. Obwohl es unwahrscheinlich ist, dass sich Hilbert solch einer Möglichkeit vor dem Weitergehen vorgestellt hatte, die Probleme zu verzeichnen, hat er sich wirklich vorherwissend geäußert:

oder in einem falschen Sinn, und sind aus diesem Grund nicht erfolgreich. Das Problem entsteht dann: Die Unmöglichkeit der Lösung laut der gegebenen Hypothesen oder im Sinn zu zeigen, hat nachgesonnen."

Die Arbeit am Problem ist in Bezug auf Lösungen in natürlichen Zahlen aber nicht willkürlichen ganzen Zahlen gewesen. Aber es ist leicht zu sehen, dass ein Algorithmus in jedem Fall verwendet werden konnte, um ein für den anderen vorzuherrschen. Wenn man einen Algorithmus besessen hat, um Lösbarkeit in natürlichen Zahlen zu bestimmen, konnte sie verwendet werden, um ob eine Gleichung in unknowns, zu bestimmen

:

hat eine Lösung der ganzen Zahl durch die Verwendung des angenommenen Algorithmus auf die 2 Gleichungen

:

Umgekehrt konnte ein Algorithmus, um für die Lösbarkeit in willkürlichen ganzen Zahlen zu prüfen, verwendet werden, um eine gegebene Gleichung für die Lösbarkeit in natürlichen Zahlen durch die Verwendung zu prüfen, der Algorithmus zur bei der gegebenen Gleichung erhaltenen Gleichung durch das Ersetzen von jedem angenommen hat, der durch die Summe der Quadrate von vier neuen unknowns unbekannt ist. Das arbeitet wegen des quadratischen Lehrsatzes von Lagrange, des Inhalts, dass jede natürliche Zahl als die Summe von vier Quadraten geschrieben werden kann.

Sätze von Diophantine

Sätze von natürlichen Zahlen, Paare von natürlichen Zahlen (oder sogar N-Tupel von natürlichen Zahlen), die Definitionen von Diophantine haben, werden Sätze von Diophantine genannt.

Definitionen von Diophantine können durch gleichzeitige Gleichungssysteme sowie durch individuelle Gleichungen weil das System zur Verfügung gestellt werden

:ist

zur einzelnen Gleichung gleichwertig

:

Rekursiv enumerable Satz kann als ein charakterisiert werden, für den dort ein Algorithmus besteht, der schließlich hinken wird, wenn ein Mitglied des Satzes, wie eingegeben, zur Verfügung gestellt wird, aber unbestimmt weitermachen kann, wenn der Eingang ein nicht Mitglied ist. Es war die Entwicklung der Berechenbarkeitstheorie (auch bekannt als recursion Theorie), der eine genaue Erklärung des intutitive Begriffs der algorithmischen Berechenbarkeit zur Verfügung gestellt hat, so den Begriff von rekursiven enumerability vollkommen streng machend. Es ist offensichtlich, dass Sätze von Diophantine rekursiv enumerable sind. Das ist, weil man alle möglichen Tupel von Werten des unknowns in einer Folge und dann für einen gegebenen Wert des Parameters einordnen, diese Tupel prüfen kann, um nacheinander zu sehen, ob sie Lösungen der entsprechenden Gleichung sind. Die Unlösbarkeit des zehnten Problems von Hilbert ist eine Folge der überraschenden Tatsache dass der

gegenteilig ist wahr:

Dieses Ergebnis ist als der Lehrsatz von Matiyasevich verschiedenartig bekannt (weil er den entscheidenden Schritt zur Verfügung gestellt hat, der den Beweis vollendet hat), und der MRDP Lehrsatz (für Yuri Matiyasevich, Julia Robinson, Martin Davis und Hilary Putnam). Weil dort rekursiv enumerable Satz besteht, der nicht berechenbar ist, ist die Unlösbarkeit des zehnten Problems von Hilbert eine unmittelbare Folge. Tatsächlich kann mehr gesagt werden: Es gibt ein Polynom

:

mit solchen Koeffizienten der ganzen Zahl dass der Satz von Werten für der die Gleichung

:

hat Lösungen in natürlichen Zahlen ist nicht berechenbar. Also, nicht nur gibt es keinen allgemeinen Algorithmus, für Gleichungen von Diophantine für die Lösbarkeit sogar für diese Parameter-Familie von Gleichungen zu prüfen, es gibt keinen Algorithmus.

Geschichte

Anwendungen

Der Matiyasevich/MRDP Lehrsatz verbindet zwei Begriffe - ein aus der Berechenbarkeitstheorie, anderem von der Zahlentheorie - und hat einige überraschende Folgen. Vielleicht ist das überraschendeste die Existenz einer universalen Gleichung von Diophantine:

:There besteht ein solches Polynom, dass, in Anbetracht jedes Diophantine untergeht, gibt es eine solche Zahl dass

::

Wie man

sehen kann, ist das einfach wahr, weil es universale Maschinen von Turing gibt, die dazu fähig sind, jeden Algorithmus durchzuführen. Diese Implikation von J.R. hatte es unwahrscheinlich scheinen lassen.

Hilary Putnam hat darauf hingewiesen, dass für jeden Satz von Diophantine von positiven ganzen Zahlen es ein Polynom gibt

:

solch, der aus genau den positiven Zahlen unter den Werten besteht, die durch als angenommen sind

die Variablen

:

erstrecken Sie sich über alle natürlichen Zahlen. Das kann wie folgt gesehen werden: Wenn

:

stellt eine Definition von Diophantine dessen zur Verfügung, dann genügt sie, um zu setzen

:

Also, zum Beispiel gibt es ein Polynom, für das der positive Teil seiner Reihe genau die Primzahlen ist. (Andererseits kann kein Polynom nur Hauptwerte übernehmen.)

Andere Anwendungen betreffen, was Logiker als Vorschläge, manchmal auch genannt Vorschläge des Typs Goldbach kennzeichnen. Diese sind der Goldbach-Vermutung im Angeben ähnlich, dass alle natürlichen Zahlen ein bestimmtes Eigentum besitzen, das algorithmisch checkable für jede besondere Zahl ist. Der Matiyasevich/MRDP Lehrsatz deutet an, dass jeder solcher Vorschlag zu einer Behauptung gleichwertig ist, die behauptet, dass eine besondere Gleichung von Diophantine keine Lösungen in natürlichen Zahlen hat. Mehrere wichtige und berühmte Probleme sind dieser Form: insbesondere der Letzte Lehrsatz von Fermat, die Hypothese von Riemann und der Vier Farbenlehrsatz. Außerdem kann die Behauptung, dass besondere formelle Systeme wie Peano-Arithmetik oder ZFC entsprechen, als Sätze ausgedrückt werden. Die Idee ist, Kurt Gödel im Codieren von Beweisen durch natürliche Zahlen auf solche Art und Weise zu folgen, dass das Eigentum, die Zahl zu sein, die einen Beweis vertritt, algorithmisch checkable ist.

Sätze haben das spezielle Eigentum dass, wenn sie falsch sind, dass Tatsache in einigen der üblichen formellen Systeme nachweisbar sein wird. Das ist, weil sich die Unehrlichkeit auf die Existenz eines Gegenbeispiels beläuft, das durch die einfache Arithmetik nachgeprüft werden kann. So, wenn ein Satz solch ist, dass weder es noch seine Ablehnung in einem dieser Systeme nachweisbar sind, dass Satz wahr sein muss.

Eine besonders bemerkenswerte Form des Unvollständigkeitslehrsatzes von Gödel ist auch eine Folge des Matiyasevich/MRDP Lehrsatzes:

Lassen Sie

:

stellen Sie eine Definition von Diophantine eines nichtberechenbaren Satzes zur Verfügung. Lassen Sie, ein Algorithmus dass Produktionen eine Folge von solchen natürlichen Zahlen dass die entsprechende Gleichung zu sein

:

hat keine Lösungen in natürlichen Zahlen. Dann gibt es eine Zahl, die nicht Produktion durch während tatsächlich die Gleichung ist

:

hat keine Lösungen in natürlichen Zahlen.

Um zu sehen, dass der Lehrsatz wahr ist, genügt er, um dass zu bemerken, wenn es keine solche Zahl gab, konnte man Mitgliedschaft einer Zahl in diesem nichtberechenbaren Satz algorithmisch prüfen, indem man gleichzeitig den Algorithmus geführt hat, um zu sehen, ob Produktion ist, während man auch alle möglich - Tupel von natürlichen Zahlen überprüft, eine Lösung der Gleichung suchend

:

Wir können einen Algorithmus mit einigen der üblichen formellen Systeme wie Peano-Arithmetik oder ZFC vereinigen, indem wir es systematisch Folgen der Axiome und dann Produktion eine Zahl wann auch immer ein Satz der Form erzeugen

lassen:

wird erzeugt. Dann sagt der Lehrsatz uns, dass entweder eine falsche Angabe dieser Form bewiesen wird oder eine wahre, bleibt unerwiesen im fraglichen System.

Weitere Ergebnisse

Wir können vom Grad eines Satzes von Diophantine als seiend kleinster Grad eines Polynoms in einer Gleichung sprechen, die diesen Satz definiert. Ähnlich können wir die Dimension solch eines Satzes kleinste Zahl von unknowns in einer Definieren-Gleichung nennen. Wegen der Existenz einer universalen Gleichung von Diophantine ist es klar, dass es absolute obere Grenzen zu beiden dieser Mengen gibt, und es viel Interesse an der Bestimmung dieser Grenzen gegeben hat.

Bereits in den 1920er Jahren hat Thoralf Skolem gezeigt, dass jede Gleichung von Diophantine zu einem des Grads 4 oder weniger gleichwertig ist. Sein Trick sollte neuen unknowns durch Gleichungen einführen, die sie gleich dem Quadrat eines unbekannten oder dem Produkt von zwei unknowns setzen. Die Wiederholung dieses Prozesses läuft auf ein System der zweiten Grad-Gleichungen hinaus; dann wird eine Gleichung des Grads 4 durch das Summieren der Quadrate erhalten. So ist jeder Diophantine untergegangen, ist trivial des Grads 4 oder weniger. Es ist nicht bekannt, ob dieses Ergebnis bestmöglich ist.

Julia Robinson und Yuri Matiyasevich haben gezeigt, dass jeder Satz von Diophantine Dimension hat, die nicht größer ist als 13. Später hat Matiyasevich ihre Methoden geschärft zu zeigen, dass 9 unknowns genügen. Obwohl es gut sein kann, dass dieses Ergebnis nicht das bestmögliche ist, hat es keinen weiteren Fortschritt gegeben. Also, insbesondere es gibt keinen Algorithmus, für Gleichungen von Diophantine mit 9 oder weniger unknowns für die Lösbarkeit in natürlichen Zahlen zu prüfen. Für den Fall von vernünftigen Lösungen der ganzen Zahl (weil hatte Hilbert es ursprünglich aufgestellt), zeigt der 4 Quadrattrick, dass es keinen Algorithmus für Gleichungen ohne mehr als 36 unknowns gibt. Aber Zhi Wei Sun hat gezeigt, dass das Problem für ganze Zahlen sogar für Gleichungen ohne mehr als 11 unknowns unlösbar ist.

Martin Davis hat algorithmische Fragen studiert, die die Zahl von Lösungen einer Gleichung von Diophantine einschließen. Das zehnte Problem von Hilbert fragt, ob diese Zahl 0 ist. Lassen Sie

und lassen Sie, eine richtige nichtleere Teilmenge dessen zu sein. Davis hat bewiesen, dass es keinen Algorithmus gibt, um eine gegebene Gleichung von Diophantine zu prüfen, um zu bestimmen, ob die Zahl seiner Lösungen ein Mitglied des Satzes ist. So gibt es keinen Algorithmus, um ob die Zahl von Lösungen einer Gleichung von Diophantine zu bestimmen

ist

begrenzt, ein vollkommenes Quadrat, eine Blüte usw. seltsam.

Erweiterungen des zehnten Problems von Hilbert

Obwohl Hilbert das Problem für die vernünftigen ganzen Zahlen aufgeworfen hat, kann es genauso gut um viele Ringe gebeten werden (insbesondere um jeden Ring, dessen Elemente listable sind). Offensichtliche Beispiele sind die Ringe von ganzen Zahlen von Feldern der algebraischen Zahl sowie den rationalen Zahlen. Ein Algorithmus wie bat er könnte erweitert worden sein, um diese anderen Gebiete zu bedecken. Zum Beispiel, die Gleichung

:

wo ein Polynom des Grads ist, ist in nichtnegativen rationalen Zahlen wenn und nur wenn lösbar

:ist

in natürlichen Zahlen lösbar. (Wenn man einen Algorithmus besessen hat, um Lösbarkeit in nichtnegativen rationalen Zahlen zu bestimmen, konnte sie leicht verwendet werden, um Lösbarkeit im rationals zu bestimmen.) Jedoch hatte das Wissen, dass es keinen solchen Algorithmus wie Hilbert gibt, gewünscht sagt nichts über diese anderen Gebiete.

Es hat viel Arbeit am zehnten Problem von Hilbert für die Ringe von ganzen Zahlen von Feldern der algebraischen Zahl gegeben. Sich auf der früheren Arbeit von Jan Denef und Leonard Lipschitz und Verwenden-Klassenfeldtheorie stützend, sind Harold N. Shapiro und Alexandra Shlapentokh im Stande gewesen sich zu erweisen:

Shlapentokh und Thanases Pheidas (unabhängig von einander) haben dasselbe Ergebnis für Felder der algebraischen Zahl erhalten, die genau zugeben, dass ein Paar des Komplexes embeddings konjugiert.

Das Problem für den Ring von ganzen Zahlen von Feldern der algebraischen Zahl außer denjenigen, die durch die Ergebnisse oben bedeckt sind, bleibt offen. Ebenfalls, trotz viel Interesses, bleibt das Problem für Gleichungen über den rationals offen. Barry Mazur hat vermutet, dass für jede Vielfalt über den rationals der topologische Verschluss über den reals des Satzes von Lösungen nur begrenzt viele Bestandteile hat. Diese Vermutung deutet an, dass die ganzen Zahlen nicht Diophantine über den rationals und so sind, wenn diese Vermutung wahr ist, würde eine negative Antwort auf das Zehnte Problem von Hilbert eine verschiedene Annäherung verlangen als das, das für andere Ringe verwendet ist.

Zeichen

• Yuri V. Matiyasevich, das Zehnte Problem von Hilbert, MIT Presse, Cambridge, Massachusetts, 1993.
• Martin Davis, Yuri Matiyasevich und Julia Robinson, "das Zehnte Problem von Hilbert: Diophantine Gleichungen: Positive Aspekte einer Negativen Lösung," Verhandlungen von Symposien in der Reinen Mathematik, vol.28 (1976), Seiten 323-378; nachgedruckt in Den Gesammelten Arbeiten von Julia Robinson, Solomon Feferman, Redakteur, pp.269-378, amerikanische Mathematische Gesellschaft 1996.
• Martin Davis, "das Zehnte Problem von Hilbert, ist" Amerikaner Mathematisch Monatlich, vol.80 (1973), Seiten 233-269 Unlösbar; nachgedruckt als ein Anhang in Martin Davis, Berechenbarkeit und Unlösbarkeit, Nachdruck von Dover 1982.
• Martin Davis und Reuben Hersh, "das 10. Problem von Hilbert", Wissenschaftlicher Amerikaner, vol. 229 (1973), Seiten 84-91.
• Jan Denef, Leonard Lipschitz, Thanases Pheidas, Jan van Geel, Redakteure, "das Zehnte Problem von Hilbert: Werkstatt an der Genter Universität, Belgien, am 2-5 November 1999." Zeitgenössische Mathematik vol. 270 (2000), amerikanische Mathematische Gesellschaft.

Außenverbindungen

• Das zehnte Problem von Hilbert: eine Geschichte der mathematischen Entdeckung
• Die zehnte Problem-Seite von Hilbert!
• Zhi Wei Sun: Auf dem zehnten Problem von Hilbert und zusammenhängenden Themen