OCaml (option informatique) · Chapitre 20 · Application directe du cours
Le piège du « il suffit d'exécuter »
Calculabilité et décidabilité · niveau 1 (application)
Énoncé
Pourquoi exécuter p sur x et « regarder si ça s'arrête » ne donne-t-il pas un décideur de l'arrêt ?
Corrigé
Si p s'arrête, on le constate au bout d'un temps fini (réponse oui). Mais si p boucle, l'observation ne se termine jamais : on ne pourra jamais répondre non avec certitude — peut-être s'arrêtera-t-il à l'étape suivante ? On obtient un semi-décideur (correct sur les oui), pas un décideur. C'est précisément cette asymétrie qui rend l'arrêt non décidable.
Exercices semblables
- Une propriété sémantique indécidable corrigé
- Le castor affairé (busy beaver) corrigé
- Décidable, semi-décidable, ou ni l'un ni l'autre ? corrigé
- Décidable ou non ? corrigé
- Un décideur corrigé