OCaml (option informatique) · Chapitre 20 · Application directe du cours
Un décideur
Calculabilité et décidabilité · niveau 1 (application)
Énoncé
Écrire un décideur pour « tous les éléments de la liste l sont positifs » et justifier qu'il s'arrête toujours.
Corrigé
let rec tous_positifs l =
match l with
| [] -> true
| x :: reste -> x > 0 && tous_positifs resteLa récursion porte sur une liste strictement plus courte à chaque appel : elle atteint [] en un nombre fini d'étapes (variant : la longueur). La fonction s'arrête sur toute entrée et donne la bonne réponse : le problème est décidable.