Informatique · Terminale · 2 min de lecture
Prouver une terminaison sans prétendre résoudre tous les programmes
Tout programme est aussi une donnée, que peuvent lire ou produire d'autres programmes (interpréteur, compilateur, système d'exploitation, téléchargement) ; la calculabilité ne dépend pas du langage de programmation utilisé ; le problème de l'arrêt (décider, pour tout programme et toute entrée, si le programme s'arrête) est indécidable : aucun programme ne peut le résoudre dans tous les cas, ce que montre un raisonnement par l'absurde.
Chapitre du programme : Numérique et sciences informatiques (spécialité)
Bloc 1 sur 7 · Comprendre
Comprendre
La calculabilité étudie les problèmes qu'un algorithme peut résoudre. Le problème général de l'arrêt consiste à décider, pour tout programme et toute entrée, si l'exécution finira. Il est indécidable dans les modèles usuels de calcul : aucun algorithme total correct ne peut répondre pour tous les programmes.
Bloc 2 sur 7 · Approfondir
Approfondir
Cette impossibilité générale n'empêche pas de prouver la terminaison d'un programme particulier. Un variant de boucle prend des valeurs dans un ensemble bien fondé et diminue strictement à chaque tour où la boucle continue. Il faut également vérifier que chaque tour effectue bien l'opération prévue.
Bloc 3 sur 7 · Exemple
Exemple travaillé
Commencez avec n=11 et soustrayez3 tant que n>0. Les valeurs successives sont11,8,5,2 puis−1. La boucle réalise quatre tours et s'arrête. Le nombre de tours restant peut être mesuré par le plafond de max(n,0)/3 : il passe de4à3,2,1 puis0. Cette preuve vaut pour ce programme, pas pour tous les programmes.
Bloc 4 sur 7 · Visualiser
Visualiser le raisonnement
Placez les états de la boucle sur une chaîne orientée. Sous chaque état, notez le nombre de tours restants calculé. La descente d'un entier naturel rend visible qu'il est impossible de continuer indéfiniment avec cette règle.
Continuez sur votre lancée
Vous avez découvert l’essentiel et un exemple. Retrouvez la suite du cours et les points à retenir, puis passez à l’entraînement guidé dans votre compte.
- Les formules et les repères à retenir
- Les erreurs fréquentes expliquées
- Un exercice avec des aides et sa correction
L’accès gratuit comprend les cours et exercices de votre niveau choisi.
Sources
- Stanford Encyclopedia of Philosophy, computability : https://plato.stanford.edu/entries/computability/
- Alan Turing, On Computable Numbers : https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
Vous pensez avoir trouvé une erreur dans cette leçon ? Signalez-la par e-mail.