Le dixième problème de Hilbert

Lemaître, Adrien (2008). « Le dixième problème de Hilbert » Mémoire. Montréal (Québec, Canada), Université du Québec à Montréal, Maîtrise en informatique.

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (5MB)

Résumé

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.

Type:	Mémoire accepté
Informations complémentaires:	Le mémoire a été numérisé tel que transmis par l'auteur.
Directeur de thèse:	Marcotte, Odile
Mots-clés ou Sujets:	Dixième problème de Hilbert
Unité d'appartenance:	Faculté des sciences > Département d'informatique
Déposé par:	RB Service des bibliothèques
Date de dépôt:	11 sept. 2008
Dernière modification:	01 nov. 2014 02:05
Adresse URL :	http://archipel.uqam.ca/id/eprint/942

Modifier les métadonnées (propriétaire du document)

Statistiques