OCaml (option informatique) · Chapitre 20 · Exercice de TD
Syracuse, problème ouvert mais pas indécidable
Calculabilité et décidabilité · niveau 2
Énoncé
La fonction syracuse (chapitre 4) s'arrête-t-elle pour tout n ? En quoi diffère cette question de l'indécidabilité de l'arrêt ?
Corrigé
Pour Syracuse, on ignore si la boucle s'arrête pour tout n (conjecture ouverte), faute d'un variant connu — mais c'est une question sur un programme précis. L'indécidabilité de l'arrêt est plus forte : elle affirme qu'aucun algorithme ne peut répondre pour tous les programmes. On peut très bien prouver la terminaison de tel programme donné (par un variant) ; ce qu'on ne peut pas, c'est un procédé général valable pour tous.
Exercices semblables
- Semi-décider l'arrêt corrigé
- Comprendre une réduction corrigé
- La diagonale corrigé
- Une propriété sémantique indécidable corrigé
- Le castor affairé (busy beaver) corrigé