http://www.lirmm.fr/~poupet/
e-mail: victor.poupet [at] lirmm.fr

Enseignement : Décidabilité (2e semestre 2004-2005)

Cours de Jacques Mazoyer en L3 à l'ENS Lyon.
Les TD ont été écrits avec Vincent Nesme, également chargé de TD.

Crystal and Ice - inner-space

Travaux dirigés

TD n°0 [pdf]

Travail préliminaire sur les codages de N : bijections ou injections de N dans lui-même ou de N^k dans N^p.

TD n°1 [pdf]

Initiation aux machines de Turing : exemples, accélération linéaire, réduction de l'alphabet et de l'espace de travail, etc.

TD n°2 [pdf]

Universalité au sens Turing des machines à compteur et deux exercices sur les machines de Turing.

TD n°3 [pdf]

Fonctions récursives primitives.

TD n°4 [pdf]

La fonction du busy beaver croît plus vite que toute fonction calculable.

TD n°5 [pdf]

Des exercices sur la récursivité tirés d'un partiel précédent.

TD n°6 [pdf]

Quelques exercices en vrac.

TD n°7 [pdf]

Encore des exercices divers sur les thèmes de la récursivité (on montre l'indécidabilité du problème de correspondance de Post à la fin).

TD n°8 [pdf]

Le théorème de Rice-Shapiro permettant de montrer que certains ensembles ne sont pas récursivement énumérables.

TD n°9 [pdf]

Complexité de Kolmogorov : définition rapide dans le TD, premières propriétés et applications (théorème d'incomplétude de Chaitin-Kolmogorov).

TD n°10 [pdf]

Encore de la complexité de Kolmogorov, et une version élégante du théorème d'incomplétude de Gödel.

Partiel

Partiel de l'année 2004-2005 [pdf]

L'énoncé du partiel comporte 5 exercices (de taille et difficulté variable). On y utilise la plupart des thèmes liés à la récursivité : numérotation des fonctions calculables, théorème s-m-n, théorème du point fixe de Kleene, théorème de Rice, indécidabilité du problème de l'arrêt, etc.

Valid XHTML 1.0 Transitional Valid CSS! Valid Konami!