All exercise sheets are in French. If you are looking for translations, please ask.
Vous pouvez trouver ici les TD du cours de calculabilité donné en première année à l'ENS Paris-Saclay.
TD1 [ PDF ] : Machines de Turing.
TD2 [ PDF ] : Machine de Turing à plusieurs rubans, langages récursivement énumérables, langages récursifs.
TD3 [ PDF ] : Réductions, (in)décidabilité.
TD4 [ PDF ] : Réductions, Théorème de Rice.
TD5 [ PDF ] : PCP, pavages, claviers.
Solutions pour le TD 5 :
- PCP : [ PDF ]
- Pavages : [ PDF ]
- Claviers : https://arxiv.org/abs/2102.10182 Preuve du théorème 117 et corollaire 118 pages 73-74
TD6 [ PDF ] : Fonctions récursives primitives.
TD7 [ PDF ] : Extraits du DM de 2022.
Pour celles et ceux qui veulent voir à quoi ressemble le code Latex de ces TD, vous pouvez trouver à titre d'exemple le source du TD3 ici.