Vous pouvez trouver ici les TD du cours de calculabilité donné en première année à l'ENS Paris-Saclay.

TD1 : Machines de Turing.

• Corrigé.

TD2 : Machine de Turing à plusieurs rubans, langages récursivement énumérables, langages récursifs.

• Corrigé.

TD3 : Réductions, (in)décidabilité.

• Corrigé.

TD4 : Réductions, Théorème de Rice.

• Corrigé.

TD5 : PCP, pavages, claviers.

• Corrigé.
• Solution PCP.
• Solution pavage.

TD6 : Fonctions récursives primitives.

• Corrigé.

TD7 : Révisions.

Vous pouvez trouver les sources de ces feuilles ici.