OCaml (option informatique) · Chapitre 20 · Exercice de TD
Comprendre une réduction
Calculabilité et décidabilité · niveau 2
Énoncé
On veut montrer que « le programme p s'arrête sur toutes les entrées » est indécidable. Esquisser la réduction depuis l'arrêt.
Corrigé
Supposons un décideur arrete_partout. Pour décider si un programme q s'arrête sur une entrée y, construisons le programme r qui, sur n'importe quelle entrée, exécute q sur y (en ignorant son argument). Alors r s'arrête sur toutes les entrées si et seulement si q s'arrête sur y. Si arrete_partout r existait, on déciderait l'arrêt de q sur y — impossible. Donc « s'arrêter partout » est indécidable.
Exercices semblables
- Semi-décider l'arrêt corrigé
- Syracuse, problème ouvert mais pas indécidable corrigé
- La diagonale corrigé
- Une propriété sémantique indécidable corrigé
- Le castor affairé (busy beaver) corrigé