L'objet de ce travail est d'exposer la démonstration de l'indécidabilité du dixième problème de Hilbert fournie par Matiiassevitch dans son livre Le dixième problème de Hilbert. Son indécidabilité paru en 1995. Le problème consiste à fournir une méthode permettant de déterminer l'existence d'une solution en nombres entiers relatifs d'une équation
polynomiale à coefficients entiers quelconque, dite équation diophantienne. Après un exposé des notions préliminaires, on réduit le problème aux entiers naturels. On s'attache ensuite à clarifier les mécanismes fournis par Matiiassevitch (1995) qui permettent de déterminer le caractère "diophantien" de l'exponentiation dans les entiers naturels. Ceci constitue la difficulté centrale de la démonstration. Sa résolution fut le fait de Matiiassevitch (1970). Ce fait établi, on s'attache à commenter et expliciter la nouvelle preuve fournie par Matiiassevitch (1995) qui utilise des méthodes de codage s'appuyant sur l'exponentiation. On voit comment leur utilisation judicieuse permet de coder les machines de Turing à l'aide d'équations diophantiennes. Ceci mène à l'équivalence entre les ensembles semi-décidables et les ensembles codés par les équations diophantiennes. Enfin, on étudie la preuve de l'indécidabilité par l'utilisation d'une méthode diagonale portant sur les équations diophantiennes. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Décidabilité, Dixième problème de Hilbert, Équations diophantiennes, Machine de Turing, Matiiassevitch.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMUQ.942 |
| Date | January 2008 |
| Creators | Lemaître, Adrien |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Detected Language | French |
| Type | Mémoire accepté, PeerReviewed |
| Format | application/pdf |
| Relation | http://www.archipel.uqam.ca/942/ |
Page generated in 0.0021 seconds