TD n° 0 [ps][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 [ps][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 [ps][pdf]
Universalité au sens Turing des machines à compteur et deux exercices sur les machines de Turing.

TD n° 3 [ps][pdf]
Fonctions récursives primitives.

TD n° 4 [ps][pdf]
La fonction du "busy beaver" croît plus vite que toute fonction calculable.

TD n° 5 [ps][pdf]
Des exercices sur la récursivité tirés d'un partiel précédent.

TD n° 6 [ps][pdf]
Quelques exercices en vrac.

TD n° 7 [ps][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 [ps][pdf]
Le théorème de Rice-Shapiro permettant de montrer que certains ensembles ne sont pas récursivement énumérables.

TD n° 9 [ps][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 [ps][pdf]
Encore de la complexité de Kolmogorov, et une version élégante du théorème d'incomplétude de Gödel.