Développement : Théorème de Rice

Détails/Enoncé :

Recasages pour l'année 2025 :

  • Pas de recasages pour cette année.

Versions :

  • Auteur :
  • 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 :

Références utilisées dans les versions de ce développement :

Langages formels, Calculabilité et Complexité, Carton (utilisée dans 19 versions au total)