Calculabilité et décidabilité : fiche de révision Tle NSI
Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur
L'essentiel
Une fonction est calculable s'il existe un programme qui la calcule pour toute entrée, en terminant à chaque fois 1.
Un problème de décision est décidable s'il existe un programme Python qui calcule le prédicat associé 1.
Le problème de l'arrêt est indécidable : aucun programme ne peut dire, pour tout programme, s'il s'arrête ou boucle 4.
La calculabilité s'intéresse à l'existence d'un algorithme, pas à sa rapidité, qui relève de la complexité 4.
Calculable, décidable : les définitions
Le problème de l'arrêt
Calculabilité, langage et complexité
Méthode pour répondre au bac
Questions flash
4 questions · correction immédiate · ton score reste sur ton appareil.
Décidable signifie qu'il existe un programme calculant le prédicat associé 1. La rapidité relève de la complexité, pas de la décidabilité 4, et le langage n'a pas d'influence 2.
Faux : Turing a démontré en 1936 qu'aucun programme ne peut décider, pour tout programme, s'il s'arrête 3. Il est tentant de croire qu'on peut simplement exécuter le programme, mais si celui-ci boucle, on n'obtiendra jamais de réponse « non ».
La calculabilité ne regarde que l'existence d'un algorithme 4, et un problème décidable peut demander trop de temps en pratique 3. Le résultat est indépendant du langage 2, et l'indécidabilité est une impossibilité prouvée, pas un manque de résultat.
C'est la thèse de Church, aussi appelée thèse de Church-Turing 4. Le théorème de Rice porte sur les questions concernant le résultat des programmes 3, et l'arrêt est un exemple de problème indécidable.
Les questions qu'on se pose
Pourquoi ne pas simplement lancer le programme pour savoir s'il s'arrête ?
Si le programme s'arrête, tu le sauras. S'il boucle, tu n'auras jamais de moment où répondre « il ne s'arrêtera pas ». Or un programme de décision doit répondre en temps fini dans tous les cas 4.
Quelle différence entre calculabilité et complexité ?
La calculabilité demande s'il existe un algorithme qui résout le problème. La complexité étudie les ressources et le temps nécessaires 34.
Un problème indécidable n'a-t-il jamais de solution ?
Il n'existe pas de programme qui le résolve pour toutes les entrées 2. Pour certains cas particuliers, on peut pourtant répondre : l'impossibilité porte sur la méthode générale.