Décidable, semi-décidable, ou ni l'un ni l'autre ?
Exercice · OCaml (option informatique), chapitre 20 — Calculabilité et décidabilité
É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.
Les autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.