Dixième problème de Hilbert
Un article de Wikipédia, l'encyclopédie libre.
Le théorème de Youri Matiiassevitch, démontré en 1970 par Youri Matiiassevitch, implique que le dixième problème de Hilbert n'a pas de solution. Ce problème, qui proposait de trouver un algorithme général pour décider si un système d'équations diophantiennes (polynômes à coefficients entiers) a une solution en nombres entiers, a été posé par David Hilbert lors de sa conférence de 1900 au congrès international de mathématiques de Paris.
Un exemple de système d'équations diophantiennes est le suivant :
- 3x2y − 7y2z3 = 18
- − 7y2 + 8z2 = 0
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 :
- ( 3(x1 − x2)2(y1 − y2) − 7(y1 − y2)2(z1 − z2)3 − 18 )2 + ( −7(y1 − y2)2 + 8(z1 − z2)2)2 = 0.
Youri 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 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 récursivement énumérable si et seulement 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 est diophantien si par définition il existe un polynôme à coefficients entiers P tel que n appartient à S si et seulement si 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 Youri 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 y a des équations diophantiennes qui ne peuvent être résolues par aucun algorithme.
Le théorème de Youri 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.
[modifier] Références
- Youri Matiiassevitch Le dixième problème de Hilbert: Son indécidabilité, Masson, (1995), ISBN : 2225848351
[modifier] Voir aussi
| Problèmes de Hilbert | |||
| Premier problème - Deuxième problème - Troisième problème - Quatrième problème - Cinquième problème - Sixième problème - Septième problème - Huitième problème - Neuvième problème - Dixième problème - Onzième problème - Douzième problème - Treizième problème - Quatorzième problème - Quinzième problème - Seizième problème - Dix-septième problème - Dix-huitième problème - Dix-neuvième problème - Vingtième problème - Vingt-et-unième problème - Vingt-deuxième problème - Vingt-troisième problème | |||
