Le castor affairé (busy beaver)
Exercice · OCaml (option informatique), chapitre 20 — Calculabilité et décidabilité
Énoncé
On admet que la fonction castor n = « le plus grand nombre d'étapes qu'un programme de taille n qui s'arrête peut effectuer » n'est calculable par aucun algorithme. Relier ce fait à l'indécidabilité de l'arrêt.
Corrigé
Si l'on savait calculer castor n, on déciderait l'arrêt : pour savoir si un programme p de taille n s'arrête, il suffirait de le simuler castor n étapes ; s'il ne s'est pas arrêté dans ce délai maximal, c'est qu'il ne s'arrêtera jamais. Or l'arrêt est indécidable ; donc castor n'est pas calculable. Cette fonction croît plus vite que toute fonction calculable : un exemple concret de l'au-delà du calculable.
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.