Modèles de calculs –­machines de Turing

L3 Informatique, U. Grenoble Alpes

Pour l’autre partie du cours Modèles de calculs, qui traite de lambda-calcul, visiter la page dédiée.

Cours

Le plan indiqué est prévisionnel et susceptible de modifications.

  1. Introduction : présentation du cours ; machines de Turing
  2. Variantes des machines de Turing : taille de l'alphabet, nombre de ruban, forme du ruban, non-déterminisme
  3. Thèse de Church-Turing : reconnaître, décider, calculer ; machine RAM et langage while ; tous les modèles (raisonnables) sont équivalents
  4. Incalculabilité : incalculabilité par dénombrement ; machine universelle ; problème de l'arrêt
  5. Incalculabilité (suite) : théorème de Rice, langages non (co-)reconnaissables
  6. Autres problèmes incalculables : pavage du plan, problème de correspondance de Post
  7. Fonctions primitives récursives : langage loop et fonction d'Ackermann-Péter
  8. Bilan du cours

Sujets de TD et examens

Quelques lectures, vidéos et liens intéressants

Machines de Turing

Thèse de Church-Turing

Indécidabilité

Bibliographie indicative

Ces références sont présentes pour celles et ceux qui le souhaitent, mais il n’y a aucune obligation à les consulter. Elles peuvent soit vous permettre d’avoir une autre présentation des sujets traités en cours, soit d’aller plus loin car elles abordent des sujets non traités.

Dernière modification : 13 janvier 2025