Dixième problème de Hilbert

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le dixième problème de Hilbert fait partie de la liste des 23 problèmes posés par David Hilbert en 1900 à Paris, lors de sa conférence au congrès international des mathématiciens. Il énonce[1] :

X - De la possibilité de résoudre une équation de Diophante.

On donne une équation de Diophante à 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 nombre entiers rationnels.

En termes modernes, il demande de trouver une méthode algorithmique générale 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 qu'il n'existe pas de tel algorithme. Le théorème de Matiiassevitch établit que les ensembles diophantiens, 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érables, ce qui entraîne qu'un tel algorithme ne peut exister.

Description[modifier | modifier le code]

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é 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[2]. 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 théorème de Fermat-Wiles résout une famille d'équations diophantiennes à trois inconnues[3].

Article détaillé : Équation diophantienne.

Hilbert n'emploie pas le mot « 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 donner une définition mathématique, qui est le fruit de travaux des années 1930, et repose sur la thèse de Church, formulée en 1936[4].

Réponse au dixième problème de Hilbert[modifier | modifier le code]

Un exemple de système d'équations diophantiennes est le suivant : .

La question qui se pose s'énonce ainsi : existe-t-il des nombres entiers x, y et z qui satisfont simultanément les deux équations ? Cette question est équivalente à celle de savoir si une équation diophantienne unique à plusieurs variables admet une solution dans les entiers naturels. Par exemple, le système ci-dessus a une solution entière si et seulement si l'équation suivante a une solution dans les entiers naturels : .

Matiiassevitch a utilisé une astuce impliquant les nombres de Fibonacci afin d'exhiber une équation diophantienne dont les solutions se développent exponentiellement. Les premiers travaux sur ce sujet sont dus à Julia Robinson, Martin Davis et Hilary Putnam ; ils avaient démontré qu'il suffit de ce résultat pour qu'il n'existe aucun algorithme général décidant l'existence de solutions pour les équations diophantiennes.

Des travaux postérieurs ont montré que la question de l'existence de solutions d'une équation diophantienne est indécidable même si l'équation a seulement 9 variables naturelles (Matiyasevich, 1977) ou 11 variables entières (Zhi Wei Sun, 1992).

Le théorème de Matiiassevitch général[modifier | modifier le code]

Le théorème de Matiiassevitch lui-même est beaucoup plus fort que l'insolubilité du dixième problème. Il affirme que :

Un ensemble est récursivement énumérable si et seulement s’il est diophantien.

Un ensemble S de nombres entiers est dit récursivement énumérable s’il y a un algorithme qui se comporte comme suit : on donne comme entrée à l'algorithme un nombre entier n, si n appartient à S, alors l'algorithme s'arrête tôt ou tard ; sinon il s'exécute indéfiniment. Cela revient à dire qu'il existe un algorithme qui s'exécute indéfiniment et produit tous les membres de S. D'autre part, un ensemble S d'entiers est dit diophantien s'il existe un polynôme à coefficients entiers P tel que n appartient à S si et seulement s'il existe des entiers x1,…, xk tels que P(n,x1,…, xk) = 0.

Il n'est pas difficile de voir que chaque ensemble diophantien est récursivement énumérable. Pour cela considérons une équation diophantienne f(n, x1,…, xk) = 0 et imaginons un algorithme qui parcourt toutes les valeurs possibles pour n, x1,…, xk, dans l'ordre croissant de la somme de leurs valeurs absolues, et retourne n chaque fois que f(n, x1,…, xk) = 0. Évidemment cet algorithme s'exécutera sans fin et énumérera les n pour lesquels f(n, x1,…, xk) = 0 a une solution.

La conjonction du théorème de Matiiassevitch avec un résultat découvert dans les années 1930 implique qu'il n'y a pas de solution au dixième problème de Hilbert. Ce résultat découvert par plusieurs logiciens affirme qu'il existe des ensembles récursivement énumérables non récursifs. Dans ce contexte, un ensemble S de nombres entiers s'appelle « récursif » s'il y a un algorithme qui, étant donné un nombre entier n, renvoie une réponse oui ou non à la question n appartient-il à S ? Il s'ensuit qu'il existe une suite (indexée par n) d'équations diophantiennes (dont le degré et le nombre d'inconnues sont même bornés) pour laquelle aucun algorithme ne peut répondre correctement pour chaque n à la question la n-ième équation a-t-elle des solutions ?.

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 plus forte suivante du premier théorème d'incomplétude de Gödel :

Soit une axiomatisation quelconque de l'arithmétique. On peut construire une équation diophantienne qui n'a aucune solution, mais telle que ce fait ne puisse pas être démontré dans l'axiomatisation en question.

Notes et références[modifier | modifier le code]

  1. Congrès international des mathématiciens 1902, p. 87 (trad. de l'allemand par Léonce Laugel — [(de) texte original]).
  2. Matiyasevich 1996, p. 2
  3. Chaque exposant détermine une équation diophantienne, mais l'équation de Fermat, en tant qu'équation à 4 inconnues, ne l'est pas.
  4. Matiyasevich 1996, p. 5

Bibliographie[modifier | modifier le code]