OCaml (option informatique) · Chapitre 20 · Exercice de TD
Le castor affairé (busy beaver)
Calculabilité et décidabilité · niveau 3 (difficile)
É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.