Section Nom Description
Cours Fichier À LIRE : Polycopié de calculabilité
Fichier Preuve de l'indécidabilité de PCP
Fichier 21 janvier. CM1 - Administrivia + Introduction
Fichier 23 janvier. CM2 - thèse de Church-Turing
Fichier 28 janvier. CM3 - la machine universelle
Fichier 4 février. CM4 - problèmes indécidables
Fichier 11 février. CM5 - indécidabilité (suite)
Fichier À LIRE : Périfel, chapitre 2 partie 1
Fichier 27 février. CM6 - reboot complexité
Fichier 4 mars. CM7 - complexité en temps
Fichier À LIRE : Périfel, chapitre 2 partie 2
Fichier 18 mars. CM8 - complexité en temps non déterministe
Fichier À LIRE : Périfel, chapitre 3
Fichier 25 mars. CM9 - théorème de Cook-Levin
TD - Calculabilité URL Simulateur de machine de Turing GTM
Fichier TD1. Machines de Turing
Fichier TD2. MT++
Fichier TD3. Simulations entre modèles
Fichier TD4. Récursivité et réductions
Fichier TD5. Réductions et Rice
TD - Complexité Fichier TD6 - complexité en temps - introduction
Fichier TD 7 - complexité en temps - P, NP et co-NP
Fichier TD 8 - complexité en temps - réductions et NP-complétude
Partiels et examens Fichier Sujet CT 2018/2019
Fichier Sujet CT 2021/2022
Ressources et bibliographie URL RUBENS : une machine de Turing intégralement mécanique en Lego

RUBENS
Page Vidéos de réalisations concrètes de machines de Turing

Vidéos de réalisations originales de machines de Turing
URL Alan Turing : du calculable à l’indécidable, par Jean-Gabriel Ganascia

Alan Turing : du calculable à l’indécidable, par Jean-Gabriel Ganascia, sur Interstices.
URL Des calculateurs universels, par Jean-Louis Giavitto

Des calculateurs universels, par Jean-Louis Giavitto, sur Interstices
URL L'héritage d'Alan Turing

Journal du CNRS