NSI (Spé) — Langages et programmation
Calculabilité, décidabilité et mise au point
Problèmes décidables et indécidables, problème de l'arrêt, tests, assertions, mise au point de programmes
Résumé synthétiqueFiche en 4 sectionsQuiz de 10 questionsGratuit, sans pub
Résumé
Un ordinateur peut-il tout résoudre, pourvu qu'on lui laisse assez de temps ? Étonnamment, non — et ce n'est pas une question de puissance. La calculabilité étudie ces limites. Un problème est décidable s'il existe un algorithme qui termine toujours et donne la bonne réponse oui/non (tester si un nombre est premier, par exemple). Mais certains problèmes sont indécidables : aucun algorithme ne peut les trancher pour tous les cas. Le plus célèbre est le problème de l'arrêt, démontré impossible par Alan Turing en 1936. Côté pratique, comme on ne peut pas tout prouver automatiquement, on met au point ses programmes : assertions, préconditions / postconditions, invariants et surtout un jeu de tests couvrant cas normaux, cas limites et cas d'erreur.
Un problème de décision est une question dont la réponse est oui ou non. Il est décidable s'il existe un algorithme qui répond correctement et s'arrête à coup sûr sur toutes les entrées. Sinon, il est indécidable : aucun algorithme ne marche dans tous les cas.
- Problème de décision : réponse oui/non. Ex. « Ce nombre est-il premier ? ».
- Décidable : il existe un algorithme qui termine toujours et donne la bonne réponse.
- Indécidable : aucun algorithme ne peut résoudre toutes les instances en temps fini.
- Machine de Turing (1936) : modèle abstrait d'ordinateur universel, étalon de ce qui est calculable.
- Thèse de Church-Turing : tout procédé de calcul « effectif » peut être simulé par une machine de Turing.
- Indécidable ≠ difficile : un problème dur (complexité énorme) reste calculable ; un indécidable est impossible à résoudre par algorithme.
Exemple
Décidable : « 91 est-il premier ? ». L'algorithme teste les diviseurs de 2 à $\sqrt{91}$, conclut « non » (91 = 7 × 13) et s'arrête. Il termine pour TOUT entier en entrée : le problème de la primalité est donc décidable.
Piège à éviter
Ne confonds pas « difficile à calculer » (complexité élevée, mais une réponse existe) et « indécidable » (impossible algorithmiquement, quelle que soit la puissance de la machine). Un superordinateur n'y change rien : la limite est théorique.
Pourrait-on écrire un programme magique H(P, e) qui, sans l'exécuter, dit si le programme P finira par s'arrêter sur l'entrée e ? Turing a prouvé que non : ce programme ne peut pas exister. C'est l'exemple fondateur d'indécidabilité.
L'hypothétique H(P, e) devrait répondre « s'arrête » ou « boucle » pour tout programme — un raisonnement par l'absurde montre qu'elle ne peut exister.
- Énoncé : existe-t-il H(P, e) qui décide si le programme P s'arrête sur l'entrée e ?
- Réponse : NON. Turing a prouvé en 1936 que le problème de l'arrêt est indécidable.
- Idée de la preuve (par l'absurde) : on suppose H existe, on bâtit un programme paradoxal qui s'arrête si H le dit bouclant, et boucle si H le dit s'arrêtant → contradiction.
- Conséquence : pas de détecteur universel de boucles infinies, ni d'antivirus parfait, ni de vérificateur de bugs total.
- Boucles parfois indéterminées : la conjecture de Syracuse ($3n+1$) ou un parcours de graphe sans marquage des sommets visités.
- Portée : une limite de principe de l'informatique, indépendante de la machine.
Exemple
Programme paradoxal : « si H dit que je m'arrête, alors je boucle ; sinon je m'arrête ». Quoi que réponde H sur ce programme, sa réponse est fausse. Donc H ne peut pas exister.
Piège à éviter
Le problème de l'arrêt est indécidable dans le cas général (pour TOUT programme). Pour un programme précis et simple, on peut souvent savoir s'il s'arrête : l'impossibilité concerne la méthode universelle, pas chaque cas particulier.
Puisqu'on ne peut pas tout prouver automatiquement, on vérifie en cours de route. L'instruction assert teste qu'une propriété attendue est bien vraie ; préconditions et postconditions précisent ce qu'une fonction exige et ce qu'elle garantit.
- assert condition, message : si la condition est fausse, lève une AssertionError ; sinon, ne fait rien.
- Précondition : ce qui doit être vrai AVANT l'appel. Ex. assert n >= 0, 'n doit être positif'.
- Postcondition : ce qui est garanti APRÈS l'exécution. Ex. assert resultat >= 0.
- Invariant de boucle : propriété vraie à chaque tour de boucle ; sert à prouver la correction.
- Exemple d'invariant : dans un tri par insertion, « les i premiers éléments sont triés » reste vrai après chaque itération.
- Documenter pré/postconditions guide l'appelant et facilite le débogage.
Exemple
def racine_entiere(n):
assert n >= 0, "n doit être positif" # précondition
r = 0
while (r + 1) * (r + 1) <= n:
r += 1
assert r * r <= n # postcondition
return r
assert n >= 0, "n doit être positif" # précondition
r = 0
while (r + 1) * (r + 1) <= n:
r += 1
assert r * r <= n # postcondition
return r
Piège à éviter
N'utilise jamais assert pour valider une entrée utilisateur : les assertions sont désactivées quand on lance Python avec l'option -O. Pour des contrôles qui doivent toujours s'appliquer, utilise if ... raise.
Tester, c'est confronter son programme à des cas connus pour traquer les bugs. Un bon jeu de tests ne se limite pas au cas « qui marche » : il vise surtout les cas limites, où se cachent la plupart des erreurs.
- Test unitaire : vérifier une fonction isolée sur des entrées dont on connaît la sortie attendue.
- Couvrir trois familles : cas normaux, cas limites (0, liste vide, valeur maximale) et cas d'erreur.
- Débogage : tracer avec print(), ou avancer pas à pas avec un débogueur et des points d'arrêt.
- doctest : les exemples écrits dans les docstrings deviennent des tests automatiques.
- unittest / pytest : cadres pour organiser de vrais tests avec des assertions dédiées.
- Régression : garder ses tests pour vérifier qu'une correction ne recasse rien plus tard.
Exemple
def factorielle(n):
r = 1
for k in range(2, n + 1):
r *= k
return r
# Jeu de tests
assert factorielle(0) == 1 # cas limite : 0! = 1
assert factorielle(1) == 1
assert factorielle(5) == 120 # cas normal
r = 1
for k in range(2, n + 1):
r *= k
return r
# Jeu de tests
assert factorielle(0) == 1 # cas limite : 0! = 1
assert factorielle(1) == 1
assert factorielle(5) == 120 # cas normal
Piège à éviter
Tester uniquement le cas « normal » (n = 5) et oublier les cas limites (n = 0, liste vide) est l'erreur la plus fréquente : c'est précisément là que se nichent les bugs.
Quiz - Calculabilité, décidabilité et mise au point
10 questions
S'entraîner
- Quiz : Calculabilité, décidabilité et mise au point10 questions corrigées sur ce chapitre
- Bac 2026 NSI – MétropoleSujet officiel
- Bac 2025 NSI – MétropoleSujet officiel
- Bac 2024 NSI – MétropoleSujet officiel
- Annales du bac de NSITous les sujets officiels, par année
- Coefficient de NSI au bacPoids de l'épreuve dans la note finale
Thème complet
Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale
Ce thème dans une autre classe
Articles utiles
Questions fréquentes
Les points clés à retenir sur Calculabilité, décidabilité et mise au point, extraits du quiz de révision.
Le problème de l'arrêt est :
Réponse :
Indécidable
Le problème de l'arrêt est indécidable : il n'existe aucun algorithme capable de déterminer, pour tout programme et toute entrée, si le programme s'arrête ou boucle indéfiniment.
Qui a démontré l'indécidabilité du problème de l'arrêt ?
Réponse :
Alan Turing
Alan Turing a démontré en 1936, par un raisonnement par l'absurde, qu'il est impossible d'écrire un programme universel qui détermine si un programme donné s'arrête.
Que fait l'instruction 'assert x > 0' en Python ?
Réponse :
Vérifie que x > 0, sinon lève AssertionError
assert x > 0 vérifie la condition x > 0. Si elle est fausse, Python lève une AssertionError et le programme s'arrête (sauf si les assertions sont désactivées).
Une précondition est :
Réponse :
Une condition qui doit être vraie avant l'exécution d'une fonction
Une précondition est une condition qui doit être satisfaite avant l'appel d'une fonction pour garantir son bon fonctionnement. Ex : le paramètre n doit être positif.