Décidable ou non ?
Exercice · OCaml (option informatique), chapitre 20 — Calculabilité et décidabilité
É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.
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.