SAM8CCAG: Ressources

Section	Nom	Description
	Consignes pour l'oral de calculabilité

Cours	À LIRE : Polycopié de calculabilité
	Preuve de l'indécidabilité de PCP

TD - Calculabilité	Simulateur de machine de Turing GTM
	TD1. Machines de Turing
	TD2. MT++
	TD3. Simulations entre modèles
	TD4. Récursivité et réductions
	TD5. Réductions et Rice

TD - Complexité	TD6, Complexité en temps - Introduction
	TD7, Complexité en temps - P, NP et co-NP
	TD8, Complexité en temps - réductions et NP-complétude

Partiels et examens	Sujet CT 2018/2019
	Sujet CT 2021/2022

Ressources et bibliographie	RUBENS : une machine de Turing intégralement mécanique en Lego	RUBENS
	Vidéos de réalisations concrètes de machines de Turing	Vidéos de réalisations originales de machines de Turing
	Alan Turing : du calculable à l’indécidable, par Jean-Gabriel Ganascia	Alan Turing : du calculable à l’indécidable, par Jean-Gabriel Ganascia, sur Interstices.
	Des calculateurs universels, par Jean-Louis Giavitto	Des calculateurs universels, par Jean-Louis Giavitto, sur Interstices
	L'héritage d'Alan Turing	Journal du CNRS