OCaml (option informatique) · Chapitre 20 · Exercice de TD
Décidable, semi-décidable, ou ni l'un ni l'autre ?
Calculabilité et décidabilité · niveau 3 (difficile)
Énoncé
Classer : (a) « p s'arrête sur x » ; (b) « p ne s'arrête pas sur x » ; (c) « la formule logique f est satisfiable » (chapitre 17).
Corrigé
(a) Semi-décidable non décidable : on simule, on confirme les oui (arrêt), jamais les non. (b) Non semi-décidable : c'est le complémentaire de (a) ; si (a) et (b) étaient toutes deux semi-décidables, l'arrêt serait décidable (lancer les deux semi-décideurs en parallèle) — impossible. (c) Décidable : il n'y a que valuations à essayer (chapitre 17), l'énumération s'arrête toujours (même si elle est exponentielle). Décidabilité et efficacité sont deux questions distinctes : un problème peut être décidable mais coûteux.
Exercices semblables
- Syracuse, problème ouvert mais pas indécidable corrigé
- Comprendre une réduction corrigé
- La diagonale corrigé
- Une propriété sémantique indécidable corrigé
- Le castor affairé (busy beaver) corrigé