Numérique et sciences informatiques (spécialité) · TerminaleBac
Calculabilité et décidabilité : quiz de Terminale 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 se termine pour toute entrée x et renvoie f(x) 1.
- Un problème de décision est décidable si le prédicat associé est calculable par un programme Python ; il est indécidable sinon 12.
- Le problème de l'arrêt est indécidable : Turing l'a démontré en 1936 3.
- La calculabilité s'intéresse à l'existence d'un algorithme, pas à son efficacité, qui relève de la complexité 4.
Avant de commencer
Ce quiz couvre le chapitre sur la calculabilité et la décidabilité du programme de Terminale NSI. Tu y trouveras des questions sur les définitions (fonction calculable, problème décidable), sur le problème de l'arrêt, sur le lien avec la complexité, et sur quelques repères historiques des années 1930. Lis chaque question jusqu'au bout, choisis ta réponse, puis lis l'explication même quand tu as bon : elle signale l'erreur tentante, celle que l'on retrouve souvent dans les copies.
Quiz
15 questions · correction immédiate · ton score reste sur ton appareil.
-
Une fonction est calculable quand un programme se termine pour toute entrée x et renvoie f(x) 1. L'idée de la durée (« moins d'une seconde ») est tentante, mais la calculabilité ne mesure aucune rapidité : seule compte l'existence du programme 4. Connaître une formule ne suffit pas non plus, car il faut un programme qui termine sur toutes les entrées.
-
C'est la définition donnée dans le cours : un problème de décision est décidable si un programme Python permet de calculer le prédicat associé 1. Il est équivalent de dire que le problème est décidable ou que le prédicat est calculable 1. La réponse « Faux » viendrait d'une confusion avec « résoudre rapidement », qui n'est pas la question.
-
C'est Alan Turing qui a établi, en 1936, que le problème de l'arrêt est indécidable 3. Gödel est tentant car il est lié à la même époque : il a publié en 1931 ses théorèmes d'incomplétude, un résultat d'une autre nature 4. Cantor a découvert l'argument diagonal en 1891, et Lovelace est une pionnière de la programmation du XIXe siècle 4.
-
Aucun programme universel ne peut, pour un programme quelconque fourni en entrée, répondre en temps fini « il s'arrête » ou « il ne s'arrête pas » 4. L'exécution « assez longtemps » est une fausse piste : si le programme tourne encore, tu ne sais pas s'il va s'arrêter plus tard ou boucler pour toujours. Le résultat vaut pour tout langage suffisamment puissant, dont ceux utilisés en pratique 3.
-
C'est faux. La calculabilité ne s'occupe pas de l'efficacité, objet de la théorie de la complexité ; elle étudie seulement l'existence ou la non-existence d'un algorithme qui résout un problème 4. Le piège est de croire qu'un problème « trop long à calculer » est indécidable : ce sont deux notions différentes.
-
Un ensemble peut être décidable en théorie alors que la décision exigerait une durée démesurée (supérieure à l'âge de l'univers) ou des ressources démesurées 3. C'est la théorie de la complexité qui étudie ces limites pratiques 3. Les autres réponses sont fausses : si le prédicat n'était pas calculable, le problème serait indécidable, et non seulement impraticable. Quant au choix du langage, il n'influe pas sur le résultat 2.
-
Un problème est décidable s'il existe un programme qui calcule la fonction associée, et il est indécidable sinon 2. Le complémentaire d'un ensemble décidable est décidable 3. Les résultats de la calculabilité ne dépendent pas du langage choisi 2. L'affirmation sur l'arrêt est fausse : le résultat de Turing s'étend aux langages suffisamment puissants, comme ceux utilisés en pratique 3.
-
Selon le théorème de Rice, une question sur les programmes qui ne porte que sur le résultat du calcul (terminaison, valeur renvoyée…) est soit indécidable, soit triviale 3. Une question triviale reçoit toujours la même réponse, « oui » ou « non », pour n'importe quel programme 3. La puissance de la machine n'y change rien : on parle d'impossibilité de principe.
-
La thèse de Church affirme une correspondance exacte entre les fonctions calculables au sens formel et celles qu'un être humain ou une machine peut effectivement calculer dans la réalité physique 4. Dire que « toutes les fonctions sont calculables » est faux : le problème de l'arrêt fournit un contre-exemple 4. De même, la machine de Turing est démontrée équivalente en possibilités à tous les ordinateurs existants, ce qui contredit la dernière proposition 4.
-
En 1931, Gödel établit que, dans toute théorie axiomatique cohérente de l'arithmétique, certains énoncés vrais restent indémontrables 4. Il s'appuie sur un codage et sur un argument diagonal que la calculabilité emploie beaucoup, notamment pour le problème de l'arrêt 4. La proposition « tout est démontrable » dit exactement le contraire du résultat.
-
En 1938, Kleene et Turing prouvent que trois modèles de calcul, le lambda-calcul de Church, les fonctions récursives générales et les machines de Turing, ont le même pouvoir 4. Cette équivalence appuie la thèse de Church : peu importe le modèle formel choisi, on calcule les mêmes fonctions 4. Les propositions qui classent un modèle au-dessus d'un autre contredisent ce résultat.
-
Entre 1842 et 1843, Ada Lovelace a traduit un article sur la machine analytique de Babbage et y a ajouté des notes ; la dernière contient un algorithme de calcul des nombres de Bernoulli, considéré comme le premier véritable programme informatique 4. Le métier à tisser à cartes perforées est l'œuvre de Joseph Marie Jacquard, au XIXe siècle aussi, ce qui rend la dernière réponse tentante mais fausse 4. Le problème de l'arrêt est un résultat de Turing 3.
-
C'est vrai : cette fonction possède bien une valeur pour tout entier, et pourtant aucun programme ne parvient à la déterminer dès que l'entier devient assez grand 4. Cela montre qu'une fonction peut exister mathématiquement sans être calculable : « être définie » et « être calculable » sont deux choses distinctes 4.
-
Un problème est indécidable s'il n'existe aucun programme calculant la fonction associée 2. Pour l'établir, on peut le prouver directement ou le relier à un résultat connu 2. Ne pas avoir trouvé de programme prouve seulement qu'on n'a pas trouvé. Enfin, « tout problème est décidable » est faux, puisque le problème de l'arrêt est indécidable 3.
Les questions qu'on se pose
Quelle différence entre un problème indécidable et un problème très long à résoudre ?
Un problème indécidable n'a aucun programme qui le résout pour toutes les entrées 2. Un problème peut être décidable en théorie mais demander trop de temps ou de ressources en pratique ; c'est la théorie de la complexité qui étudie ce cas 3. La calculabilité, elle, ne s'occupe que de l'existence d'un algorithme 4.
Que dois-je savoir sur le problème de l'arrêt pour le Bac ?
Retiens son énoncé : aucun programme ne sait dire, pour tout programme reçu en entrée, s'il s'arrête ou non 4. Retiens aussi l'auteur et la date : Alan Turing, 1936 3. Sache en donner la conséquence pratique : on ne peut pas tester automatiquement la terminaison de tous les programmes d'un langage suffisamment puissant 3.
Sources
Programme visé : Calculabilité et décidabilité · Éduscol (Ministère de l'Éducation nationale)
- Calculabilité et décidabilité, Éduscol (Ministère de l'Éducation nationale). Consulté le 7 novembre 2026.
- Calculabilité (Cours M1 MEEF NSI), Université Grenoble Alpes. Consulté le 7 novembre 2026.
- Décidabilité, Wikipédia. Consulté le 7 novembre 2026.
- Théorie de la calculabilité, Wikipédia. Consulté le 7 novembre 2026.
Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.