Voir la source de Dixième problème de Hilbert

Le '''dixième problème de Hilbert''' fait partie de la liste des 23 [[Problèmes de Hilbert|problèmes]] posés par [[David Hilbert]] en 1900 à Paris, lors de sa conférence au [[congrès international des mathématiciens]]. Il énonce<ref>{{harvsp|Congrès international des mathématiciens|1902|p=87|id=CIM1900}} (trad. de l'allemand par [[Léonce Laugel]] — {{lire sur Wikisource|lien=Seite:Hilbert_-_Mathematische_Probleme.pdf/25|langue=de|texte=texte original}}).</ref> :
{{énoncé| '''X. — De la possibilité de résoudre une équation diophantienne.'''
:On donne une équation diophantienne à un nombre quelconque d'inconnues et à coefficients entiers rationnels : ''On demande de trouver une méthode par laquelle, au moyen d'un nombre fini d'opérations, on pourra distinguer si l'équation est résoluble en nombres entiers rationnels.}}

En termes modernes, il demande de trouver un [[algorithme]] ''général'' permettant de décider, pour n'importe quelle [[équation diophantienne]] (c'est-à-dire équation polynomiale à coefficients entiers), si cette équation possède des solutions entières.

En 1970, [[Youri Matiiassevitch]] démontre<ref>{{Article|lang=ru|auteur= Ю. В. Матиясевич|titre=Диофантовость перечислимых множеств|revue=[[Doklady Akademii Nauk|Dokl. Akad. Nauk.]] [[URSS|SSR]]|vol=191|numéro=2|date=1970|p.=279-282|url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=35274&option_lang=rus}} ; traduction : {{Chapitre|lang=en|auteur=[[Youri Matiiassevitch#cite_note-1|Ju. V. Matijasevič]]|titre chapitre=Enumerable sets are diophantine|titre ouvrage=Mathematical Logic in the 20th Century|éditeur=[[Université nationale de Singapour|Singapore University]] Press/[[World Scientific]]|auteurs ouvrage=[[Gerald E. Sacks]]|date=2003|isbn=978-981-02-47362|doi=10.1142/9789812564894_0013|url={{Google Livres|vOLUCgAAQBAJ|page=269}}|page=269-273}}.</ref> qu'il n'existe pas de tel algorithme.
Le [[théorème de Matiiassevitch]] établit que les ensembles [[diophantien]]s, qui sont les ensembles de solutions entières positives ou nulles d'une équation diophantienne avec paramètres, sont exactement tous les ensembles [[récursivement énumérable]]s, ce qui entraîne qu'un tel algorithme ne peut exister.

== Prérequis ==

=== Description ===
Il s'agit du seul des 23 problèmes de Hilbert qui est ce que l'on appelle aujourd'hui un [[problème de décision]] : il existe une infinité [[Ensemble dénombrable|dénombrable]] d'équations diophantiennes, mais la solution du dixième problème demande de trouver une  méthode ''universelle'' qui permette de statuer sur la résolubilité de n'importe quelle [[équation diophantienne]]<ref>{{harvsp|Matiyasevich|1996|p=2}}.</ref>. Il existe de fait des méthodes très diverses et utilisant des techniques mathématiques très variées pour résoudre des équations diophantiennes spécifiques. Par exemple, le [[dernier théorème de Fermat|théorème de Fermat-Wiles]] résout une famille d'équations diophantiennes à trois inconnues<ref>Chaque exposant détermine une équation diophantienne, mais l'équation de Fermat, en tant qu'équation à 4 inconnues, ne l'est pas.</ref>.
{{article détaillé|Équation diophantienne}}

Hilbert n'emploie pas le mot « [[algorithmique|algorithme]] », mais il n'y a aucun doute que c'est cela qu'il entend. À son époque, il n'existe pas de définition précise de ce qu'est un algorithme, ce qui n'aurait pas été gênant si la solution du problème avait été positive. Pour pouvoir envisager une solution négative, il fallait en proposer une définition mathématique, qui est le fruit de travaux dans les années 1930, et repose sur la [[thèse de Church]], formulée en 1936<ref>{{harvsp|Matiyasevich|1996|p=5}}.</ref>.

=== Équation diophantienne ===
{{article détaillé | Équation diophantienne}}
Commençons par un exemple : considérons l'équation [[Polynôme|polynomiale]] (à deux inconnues) <math>x^2 - 2y^2= 0.</math> On sait depuis la [[Nombre irrationnel#Découverte des irrationnels|découverte des irrationnels]] en Grèce Antique qu'il n'existe pas de  [[nombre rationnel]]  <math>x/y</math> dont le carré vaut <math>2</math>. On dira alors que l'équation diophantienne associée au polynôme <math>D(x,y) = x^2 - 2y^2</math> ne possède aucune solution (on précise parfois « aucune solution [[Trivial (mathématiques)|non triviale]] », c’est-à-dire formée d’entiers strictement positifs). De manière générale, une [[équation diophantienne]] est une équation du type <math>D(x_1,\dots,x_k) = 0</math> où <math>D</math> est [[Polynôme en plusieurs indéterminées |un polynôme à <math>k</math> indéterminées]] à coefficients [[Entier relatif | entiers]], dont on cherche des solutions [[Entier relatif | entières]] (ou parfois seulement entières positives, voir ci-dessous).

Un exemple de familles d'équations diophantiennes dont on sait trouver des solutions, est la famille des équations du type <math>ax + by = c</math> d'inconnues <math>x, y</math>, où <math>a, b, c</math> sont des entiers; par exemple l'équation <math>99x + 56y = 1</math>. On peut bien sûr imaginer des exemples plus exotiques comme <math>4x^2 + 34zy - xy + (z-y-3x)^4 = 0</math> d'inconnues <math>x, y, z</math>.

[[David Hilbert |Hilbert]] pose donc la question dans son dixième [[Problèmes de Hilbert |problème]] de savoir si l'on peut écrire un algorithme <math>A</math>, prenant en entrée un [[polynôme]] <math>D(x_1,\dots,x_k)</math>, à coefficients [[Entier relatif|entiers]], et décidant si oui ou non l'équation <math>D(x_1,\dots,x_k) = 0</math> possède des solutions entières (en particulier on ne demande pas à l'algorithme <math>A</math> de donner ces solutions si elles existent).

Il est important de noter que la résolution de <math>D(x_1,\dots,x_k) = 0</math>  où <math>x_1,\dots,x_k</math> sont des [[Entier relatif | entiers quelconques]], revient à résoudre <math>D(y_1-z_1,\dots,y_k-z_k) = 0</math> où <math>y_1,z_1,\dots,y_k,z_k</math> sont des [[Entier naturel|entiers naturels]]. Ainsi, on peut donc ramener le dixième problème de Hilbert à un autre problème de décision, qui est de savoir si une équation diophantienne admet des solutions [[Entier naturel|entières positives]] (on parle de [[Réduction (complexité)|réduction]]).

=== Ensembles diophantiens ===
{{article détaillé | Diophantien}}
On ne va maintenant plus considérer une seule équation diophantienne <math>D(x_1,\dots,x_k) = 0</math> mais une famille d'équations diophantiennes du type <math>D(a_1,\dots,a_n,x_1,\dots,x_k) = 0</math>, où <math>a_1,\dots,a_n</math> sont des paramètres qui sont des entiers positifs.

Ceci peut donner l'impression que l'on complexifie le problème mais cette interprétation des équations diophantiennes va s'avérer très utile. En effet pour un polynôme <math>D(a_1,\dots,a_n,x_1,\dots,x_k)</math> à paramètres entiers <math>a_1,\dots,a_n</math>, on peut considérer l'ensemble <math>M = \{\,(a_1,\dots,a_n)\mid\exists x_1,\dots,x_k\in\N\ D(a_1,\dots,a_n,x_1,\dots,x_k)=0\,\}</math>, c'est-à-dire l'ensemble des <math>n</math>-uplets de paramètres <math>(a_1,\dots,a_n)</math> tels que l'équation <math>D(a_1,\dots,a_n,x_1,\dots,x_k) = 0</math> possède au moins une solution [[Entier naturel |entière positive]]. Réciproquement, on dit qu'un ensemble de <math>n</math>-uplets est [[diophantien]] s'il est de cette forme, et alors le polynôme <math>D(a_1,\dots,a_n,x_1,\dots,x_k)</math> est une ''représentation diophantienne'' de cet ensemble.

Par exemple l'ensemble des entiers naturels pairs est diophantien : en effet <math>D(a,x)=a-2x</math>  en est une représentation diophantienne. De même, le sous-ensemble de <math>\N^2</math> des couples d'entiers positifs premiers entre eux est diophantien puisque, par le [[Théorème de Bachet-Bézout|théorème de Bézout]], cet ensemble est représenté par le polynôme paramétré <math>D(a,b,x_1, x_2,y_1, y_2)  =  a(x_1 - x_2) + b(y_1 - y_2) -1</math> toujours avec <math>a,b,x_1,x_2,y_1,y_2</math> des entiers positifs.

=== Problèmes décidables ===
{{article détaillé | Décidabilité}}

Comme dit dans la description, le dixième problème de Hilbert est un problème [[Problème de décision|de décision]], c'est-à-dire qu'on se pose la question de l'existence d'un algorithme <math>A</math> qui, à chaque fois que l'on entre une équation diophantienne, renvoie « oui » ou « non » selon qu'elle possède ou non des solutions. S'il existe un tel algorithme, le problème de décision est dit décidable. On dira, de manière équivalente, que l'ensemble des instances positives d'un tel problème est alors ''récursif''.
=== Ensembles récursivement énumérables ===
{{article détaillé | Récursivement énumérable}}
[[Fichier:Récursivement énumérable.svg|vignette|Un ensemble récursivement énumérable peut être énuméré par un ordinateur.]]
Un sous-ensemble <math>S</math> de <math>\N^n</math>est dit [[ récursivement énumérable]] s’il existe un algorithme qui s'exécute indéfiniment et qui énumère exactement tous les membres de <math>S</math>.

<br />
{{énoncé| '''Proposition - tout ensemble diophantien est récursivement énumérable.'''}}

En effet, considérons une équation diophantienne <math>D(a_1,\dots,a_n,x_1,\dots,x_k) = 0</math> et imaginons un algorithme qui parcourt toutes les valeurs possibles des <math>(n + k)</math>-uplets <math>a_1,\dots,a_n,x_1,\dots,x_k</math> dans un ordre précis (par exemple un [[ ordre lexicographique]]), et affiche <math>a_1,\dots,a_n</math> chaque fois que <math>D(a_1,\dots,a_n,x_1,\dots,x_k) = 0</math>. Cet algorithme s'exécutera sans fin et énumérera exactement les <math>k</math>-uplets <math>a_1,\dots,a_n</math> pour lesquels <math>D(a_1,\dots,a_n,x_1,\dots,x_k) = 0</math> a une solution.  

{{énoncé| '''Proposition - Il existe des ensembles récursivement énumérables qui ne sont pas récursifs'''}}

Par exemple, le '''langage d'acceptation'''<ref>{{harvsp|Olivier Carton, Langages formels, calculabilité et complexité|2008|p=132,133|id=CIM1900}}.</ref>, c'est-à-dire l'ensemble des couples <math>\langle M, w \rangle</math> où <math>M</math> est une [[machine de Turing]] qui termine avec le mot <math>w</math> comme donnée initiale, est récursivement énumérable mais pas récursif. Ainsi, on peut trouver un ensemble récursivement énumérable <math>S</math> de <math>n</math>-uplets non [[Ensemble récursif |récursif]], c'est-à-dire tel que pour n'importe quel algorithme on puisse trouver un <math>n</math>-uplet pour lequel cet algorithme tourne indéfiniment sans jamais renvoyer de réponse. En vue des liens déjà établis entre ensembles diophantiens et ensembles récursivement énumérables, si l'ensemble <math>S</math> précédent était diophantien, on aurait notre réponse au dixième problème de Hilbert.

== Théorème de Matiiassevitch ==
{{Article détaillé|Théorème de Matiiassevitch|}}
Ces derniers énoncés ont incité [[Martin Davis]] à conjecturer que les ensembles récursivement énumérables sont exactement les ensembles diophantiens. Ceci donnerait en effet, grâce au dernier énoncé, une réponse négative au dixième problème de Hilbert. Le théorème de Matiiassevitch (1970) prouve la conjecture de [[Martin Davis | Davis]].

=== Énoncé ===

Le théorème de [[Youri Matiiassevitch | Matiiassevitch]], prouvant la conjecture de [[Martin Davis]], lui-même est beaucoup plus fort que l'insolubilité du dixième problème. Cet énoncé aussi appelé « Théorème DPRM » (pour [[Martin Davis]], [[Hilary Putnam]], [[Julia Robinson]] et [[Youri Matiiassevitch | Matiiassevitch]]) affirme que :

{{énoncé| '''Un ensemble est [[récursivement énumérable]] si et seulement s’il est diophantien.''' }}

Le fait que tout ensemble diophantien est récursivement énumérable a été expliqué ci-dessus dans la partie ensemble [[récursivement énumérable]], est évidemment le sens de l'équivalence qui a posé le moins de problèmes. C'est l'implication « être récursivement énumérable ⇒ être diophantien » qui a pris vingt ans à être prouvée.

=== Réponse au problème ===
Ce théorème répond bien au problème puisqu'on peut trouver un ensemble récursivement énumérable non récursif, et par le théorème précédent, cet ensemble est diophantien. On a donc un ensemble diophantien non récursif et la théorie de la [[ décidabilité]] nous dit donc que le problème de décision des équations diophantiennes a une réponse négative.
== Conséquences ==
=== Incomplétude de Gödel ===
Le théorème de Matiiassevitch a été depuis employé pour démontrer l'indécidabilité de nombreux problèmes liés à l'arithmétique. De même, on peut également dériver la forme suivante plus forte du premier théorème d'incomplétude de Gödel :{{énoncé| Soit une {{quoi|axiomatisation finie (ou récursive)}} de l'arithmétique. On peut construire une équation diophantienne qui n'a aucune solution, mais tel que ce fait ne puisse pas être démontré dans l'axiomatisation en question.{{refnec}} }}

=== Équation diophantienne universelle ===

Si <math>n\in\N</math>, on peut lister tous les ensembles récursivement énumérables de <math>n</math>-uplets de <math>\N^n</math>:<center><math>M_0,\dots,M_k,\dots</math></center>

Soit alors <math>U_n</math> l'ensemble des <math>(n+1)</math>-uplets tel que: <center><math>(a_1,\dots,a_n,k)\in U_n  \iff  (a_1,\dots,a_n) \in M_k</math></center>


Il n'est alors pas compliqué de prouver que <math>U_n</math> est récursivement énumérable, ainsi par le théorème de Matiiassevitch: 
<center><math>\exists D_n\ (a_1,\dots,a_n,a_{n+1})\in U_n \iff \exists (x_1,\dots, x_k)\  D_n(a_1,\dots,a_n,a_{n+1},x_1,\dots, x_k)=0</math> </center>

On a donc, de façon analogue à la [[Machine de Turing universelle]], pour tout <math>n\in\N</math>, l'existence d'un polynôme universel <math>D_n</math>, où l'universalité est à prendre de la façon suivante:
<center><math>\forall D\ \exists k_D\ \forall(a_1,\dots,a_n)\ [\exists  (x_1,\dots, x_k)\ [D(a_1,\dots,a_n,x_1,\dots, x_k) = 0 \iff D_n(a_1,\dots,a_n,k_D,x_1,\dots, x_k)=0]]</math></center>



Ainsi, pour un nombre de paramètres fixes, une équation diophantienne, de degré et nombre d'inconnues quelconques, peut se ramener à la résolution d'une équation diophantienne de degré et nombre d'inconnues fixes. 

== Notes et références ==
{{Références}}

== Bibliographie ==
* {{Ouvrage |langue=en |auteur1=Yuri Matiyasevich|url=http://logic.pdmi.ras.ru/~yumat/personaljournal/H10history/H10histe.pdf|titre=Hilbert's Tenth Problem: What can we do with Diophantine equations?|année=1996}} {{plume}}
* {{Ouvrage |langue=fr |auteur institutionnel=Congrès international des mathématiciens |titre=Compte rendu du deuxième Congrès international des mathematiciens tenu à Paris du 6 au 12 août 1900 |éditeur=Gauthier-Villars |lieu=Paris |année=1902 |pages totales=455 |lire en ligne=https://gallica.bnf.fr/ark:/12148/bpt6k994421/f94.item.zoom |id=CIM1900}} {{plume}}
* Youri Matiiassevitch, ''Le dixième problème de Hilbert: Son indécidabilité'', Masson, 1995 {{ISBN|978-2-22584835-3}}
* {{article|auteur1=J. P. Jones|auteur2=Y. V. Matijasevič|année=1991|titre=Proof of Recursive Unsolvability of Hilbert's Tenth Problem|périodique=The American Mathematical Monthly|volume=98|numéro=8|pages=689-709|doi=10.1080/00029890.1991.11995778}}
* {{lien web|url=http://logic.pdmi.ras.ru/Hilbert10/index.html|titre=Welcome to Hilbert's Tenth Problem page!|site=Institut de mathématiques Steklov|auteur=Maxim Vsemirnov (sous la supervision de [[Yuri Matiyasevich]])}}


{{Palette|Problèmes de Hilbert}}

{{Portail|logique|mathématiques}}

[[Catégorie:Problème de Hilbert]]
[[Catégorie:Informatique théorique]]
[[Catégorie:Logique mathématique]]
[[Catégorie:Calculabilité]]
[[Catégorie:Conjecture réfutée]]