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 Nk dans Np.
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.