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é.
- **É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
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
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
Thème complet
Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale
Ce thème dans une autre classe
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.