Langages formels, Calculabilité et Complexité

Carton

Utilisée dans les 6 développements suivants :

Algorithme CYK
Décidabilité de l'arithmétique de Presburger
Théorème de Cook
Théorème de Rice
Théorème de Savitch
NP-Complétude de HAM-PATH

Utilisée dans les 7 leçons suivantes :

909 (2017) Langages rationnels et automates finis. Exemples et applications.
910 (2016) Langages algébriques. Exemples et applications.
27 (2022) Décidabilité et indécidabilité. Exemples.
29 (2022) Langages rationnels et automates finis. Exemples et applications
912 (2021) Fonctions récursives primitives et non primitives. Exemples.
913 (2021) Machines de Turing. Applications.
25 (2022) Analyses lexicale et syntaxique. Applications.

Utilisée dans les 9 versions de développements suivants :

  • Développement :
  • Remarque :
    On prouve le théorème de Rice, et on rajoute à la fin un contre-exemple pour bien faire sentir ce que le théorème dit réellement : les propriétés doivent concerner le langage lui-même, pas la machine de Turing ni la manière dont elle exécute les calculs.
    Recasable avec 4* dans la leçon 913.
  • Référence :
  • Fichier :

Utilisée dans les 10 versions de leçons suivantes :