Spelling suggestions: "subject:"sixième"" "subject:"deuxième""
1 |
Le dixième problème de HilbertLemaître, Adrien January 2008 (has links) (PDF)
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.
|
Page generated in 1.973 seconds