OCaml (option informatique) · Chapitre 20 · Application directe du cours
Décidable ou non ?
Calculabilité et décidabilité · niveau 1 (application)
Énoncé
Pour chacun, dire s'il est décidable : (a) « n est pair » ; (b) « le tableau t contient un 0 » ; (c) « le programme p s'arrête sur 0 ».
Corrigé
(a) Décidable : n mod 2 = 0, qui s'arrête toujours. (b) Décidable : un parcours du tableau (fini) s'arrête toujours. (c) Indécidable : c'est un cas particulier du problème de l'arrêt — décider l'arrêt sur l'entrée 0 pour tout p permettrait… de décider l'arrêt.