Numérique et sciences informatiques (spécialité) · TerminaleBac

Calculabilité et décidabilité : cours 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 s'arrête pour toute entrée et renvoie la bonne valeur ; un problème de décision est décidable si le prédicat associé est calculable.¹
Le résultat ne dépend pas du langage choisi : tous les modèles de calcul connus ont les mêmes possibilités (thèse de Church).²⁴
Le problème de l'arrêt est indécidable : aucun programme ne peut dire, pour tout programme et toute entrée, si l'exécution s'arrête (Turing, 1936).³
Décidable ne veut pas dire rapide : la calculabilité ne s'occupe que de l'existence d'un algorithme, la complexité étudie son coût.⁴³
Pour un exercice : écrire un programme qui termine toujours prouve la décidabilité ; une preuve par l'absurde de type « programme paradoxal » prouve l'indécidabilité.

Pourquoi se demander ce qu'un programme peut calculer

Depuis le début de l'année, tu écris des programmes qui résolvent des problèmes : trier une liste, chercher un mot, calculer une moyenne. À chaque fois, tu as fini par trouver un algorithme. Une question se pose alors, plus profonde : existe-t-il toujours un programme qui résout un problème donné ? Ou bien y a-t-il des problèmes parfaitement bien posés pour lesquels aucun programme, même écrit par le meilleur informaticien, ne marchera jamais ?

C'est exactement l'objet de la théorie de la calculabilité : elle cherche à identifier les limites de ce qu'un algorithme est capable de calculer.⁴ Ce cours te donne le vocabulaire (fonction calculable, problème décidable), te montre comment démontrer qu'un problème est décidable, puis traite le grand résultat du programme : le problème de l'arrêt.

Le plan du cours :

ce qu'est une fonction calculable ;
ce qu'est un problème de décision et quand on le dit décidable ;
pourquoi le langage choisi n'a aucune importance ;
le problème de l'arrêt, avec sa démonstration ;
ses conséquences pour les outils qui analysent des programmes ;
les erreurs à éviter le jour du bac.

Fonction calculable : une définition précise

Prenons une fonction $f$ qui, à une entrée $x$ , associe une sortie $f(x)$ . Quand tu l'implémentes en Python, tu écris une fonction qui prend $x$ en paramètre et renvoie $f(x)$ . Mais on peut décrire mathématiquement une fonction sans savoir si un tel programme existe. D'où la définition suivante.

ExempleUne fonction calculable

Soit $f(n) = n^2 + 1$ pour un entier $n \geq 0$ . Le programme suivant la calcule :

def f(n):
    return n * n + 1

Il ne contient aucune boucle : il s'arrête forcément, quelle que soit la valeur de n. La fonction $f$ est donc calculable.

ExempleUne fonction calculable avec une boucle

Soit $g(n)$ la somme des entiers de $1$ à $n$ .

def g(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

La boucle for effectue exactement n tours : le programme s'arrête pour tout entier n. La fonction $g$ est calculable. Remarque que la méthode utilisée (boucle ou formule) n'a aucune importance : il suffit qu'un programme convienne.

Problème de décision et décidabilité

Beaucoup de questions informatiques n'attendent qu'une réponse par oui ou par non : « ce nombre est-il premier ? », « cette liste est-elle triée ? », « ce mot figure-t-il dans le texte ? ». On les appelle des problèmes de décision. À chacun on associe un prédicat : une fonction qui renvoie True quand la réponse est oui et False quand elle est non.

ExempleDécider si un nombre est pair

Le problème « l'entier $n$ est-il pair ? » est décidable :

def est_pair(n):
    return n % 2 == 0

Le programme s'arrête pour tout entier et donne la bonne réponse.

ExempleDécider si un nombre est premier

Le problème « l'entier $n \geq 2$ est-il premier ? » est décidable. Il suffit de tester les diviseurs possibles :

def est_premier(n):
    for d in range(2, n):
        if n % d == 0:
            return False
    return True

La boucle contient au plus $n-2$ tours, donc le programme s'arrête. Il n'est pas très rapide, mais il est correct et se termine : le problème est décidable. Ce cas illustre le point central du chapitre : la lenteur n'enlève rien à la décidabilité.⁴

Pourquoi le langage choisi n'a pas d'importance

La définition parle d'un programme Python. Une objection vient aussitôt : et si un problème était décidable en Python mais pas en C, en Java ou en OCaml ? La réponse est non. Les résultats de la calculabilité ne dépendent pas du langage choisi.² Ils ne dépendent pas non plus de la puissance de ton ordinateur : la théorie raisonne sur un ordinateur idéalisé, comme la machine de Turing, dont on a démontré qu'elle possède les mêmes possibilités que tous les ordinateurs existants.⁴

Plusieurs définitions formelles du calcul ont été proposées dans les années 1930.² Bien avant, au XIXe siècle, le métier à tisser de Jacquard fut le premier système mécanique programmable par cartes perforées.⁴ Entre 1842 et 1843, Ada Lovelace ajoute des notes à un article sur la machine analytique de Babbage ; l'une d'elles décrit un algorithme de calcul des nombres de Bernoulli, considéré comme le premier véritable programme informatique.⁴ Le visuel ci-dessous situe quelques repères qui préparent le résultat central du cours.

Notes d'Ada Lovelace (1842 – 1843)

1842
1891Cantor découvre l'argument diagonal
1931Gödel publie ses théorèmes d'incomplétude
1936Turing démontre l'indécidabilité de l'arrêt
1938Kleene et Turing : équivalence des modèles de calcul
1938

Repères historiques autour de la calculabilité · Dates tirées des sources du cours.

Le problème de l'arrêt

Existe-t-il des problèmes de décision indécidables ? Oui, et le plus célèbre concerne les programmes eux-mêmes. Voici la situation : tu écris un programme qui boucle sans fin sur certaines entrées ; l'exécution ne s'arrête jamais. Ne serait-il pas formidable de disposer d'un outil universel qui, avant de lancer n'importe quel programme, annonce s'il s'arrêtera ou non ?

Supposons, pour raisonner, qu'on dispose d'une fonction arrete(prog, donnee) qui renvoie True si le programme prog (donné sous forme de texte) s'arrête sur l'entrée donnee, et False s'il tourne indéfiniment. On exige comme pour toute fonction calculable que arrete se termine toujours. Le théorème affirme qu'elle ne peut pas exister.

Démonstration · Preuve par l'absurde

Supposons qu'une fonction arrete(prog, donnee) existe : elle se termine toujours et répond correctement. Fabriquons à partir d'elle un nouveau programme.

def paradoxe(prog):
    if arrete(prog, prog):
        while True:      # boucle sans fin
            pass
    else:
        return 0

Il faut comprendre que le texte d'un programme est une donnée comme une autre : on peut donc donner prog à prog comme entrée. Cet usage d'un objet appliqué à sa propre description relève de l'argument diagonal, découvert par Cantor en 1891 et très utilisé en calculabilité.⁴

Appelons maintenant paradoxe sur son propre texte : paradoxe(paradoxe).

Cas 1 : arrete(paradoxe, paradoxe) renvoie True. Alors paradoxe entre dans la boucle infinie et ne s'arrête pas. Mais arrete avait affirmé qu'il s'arrêtait : contradiction.
Cas 2 : arrete(paradoxe, paradoxe) renvoie False. Alors paradoxe renvoie 0 et s'arrête. Mais arrete avait affirmé qu'il ne s'arrêtait pas : contradiction.

Les deux cas sont impossibles. L'hypothèse de départ est donc fausse : aucune fonction arrete correcte et toujours terminante n'existe. Le problème de l'arrêt est indécidable.

SupposerUne fonction arrete existe et répond toujours juste.
Construireparadoxe boucle si arrete dit oui, s'arrête sinon.
AppliquerOn exécute paradoxe(paradoxe) : deux cas à examiner.
ConclureChaque cas se contredit : arrete n'existe pas.

Preuve de l'indécidabilité de l'arrêt

Conséquences : ce qu'aucun outil ne pourra faire

Le problème de l'arrêt n'est pas une curiosité de logiciens. Il explique pourquoi certains outils idéaux n'existeront jamais. On ne peut pas concevoir un programme capable de tester n'importe quel programme d'un langage suffisamment puissant pour conclure, dans tous les cas, s'il s'arrêtera en temps fini ou bouclera.³

Les compilateurs, analyseurs et débogueurs existent et sont utiles. Ils ne contredisent pas le théorème : ils traitent des cas particuliers, acceptent de répondre « je ne sais pas » ou limitent le type de programmes étudiés. Ce qui est impossible, c'est un outil qui donne toujours la bonne réponse, pour tous les programmes.

Le problème de l'arrêt n'est pas le seul exemple. On connaît de nombreuses fonctions incalculables, dont le « castor affairé » : une fonction bien définie, qui possède une valeur pour chaque entier, mais qu'on ne peut pas calculer pour les entiers suffisamment grands.⁴ Du côté de la logique, Gödel a publié en 1931 ses théorèmes d'incomplétude. Le premier dit que, dans toute théorie axiomatique de l'arithmétique qui ne se contredit pas, certains énoncés vrais restent hors de portée d'une démonstration au sein de cette théorie.⁴ Pour l'établir, il a lui aussi employé un argument diagonal.⁴ Les mathématiques et l'informatique rencontrent donc des limites de même nature.

Décidable en théorie, impossible en pratique : calculabilité et complexité

Un problème peut être décidable en théorie sans que la décision soit réalisable en pratique : le calcul exigerait une durée supérieure à l'âge de l'univers, ou une mémoire dépassant le nombre d'atomes qu'il contient.³ Étudier les problèmes de décision en tenant compte des ressources et du temps de calcul est l'objet de la théorie de la complexité des algorithmes.³

Pour ne pas mélanger les deux notions, retiens ce tableau :

Calculabilité et complexité
Notion	Question posée	Exemple
Calculabilité	Existe-t-il un algorithme qui résout le problème ?	Le problème de l'arrêt n'en a pas
Complexité	Quel temps et quelles ressources faut-il ?	Tester tous les codes à 100 chiffres

Calculabilité et complexité

Méthodes et pièges pour le bac

Exercices corrigés

Exercice 1 Décidable ou non ? Justifier

★☆☆Environ 10 min

Pour chacun des problèmes suivants, indique s'il est décidable et justifie avec un programme ou avec un théorème du cours.

« La chaîne de caractères s est-elle un palindrome ? »
« Le programme P s'arrête-t-il sur l'entrée x ? » (pour tout programme P et toute entrée x)
« L'entier n est-il divisible par 7 ? »

Indice 1

Pour un problème décidable, cherche un programme dont la boucle est bornée.

Indice 2

Pour la question 2, repense au théorème de Turing.

Voir la correction pas à pas

Question 1 : on écrit def palindrome(s): return s == s[::-1]. Le programme s'arrête pour toute chaîne finie et renvoie la bonne réponse : le problème est décidable.
Question 2 : c'est exactement le problème de l'arrêt. Aucun programme ne peut répondre correctement pour tous les programmes et toutes les entrées : le problème est indécidable.
Question 3 : on écrit def div7(n): return n % 7 == 0. Il n'y a pas de boucle, le programme s'arrête toujours : le problème est décidable.

Deux problèmes sur trois sont décidables, avec un programme évident. Le problème de l'arrêt est le cas typique d'indécidabilité ; il ne faut pas le confondre avec la possibilité d'étudier un programme précis.

Exercice 2 Compter les tours d'une boucle

★☆☆Environ 8 min

On considère le programme suivant :

def f():
    i = 1
    tours = 0
    while i < 100:
        i = i * 2
        tours = tours + 1
    return tours

Combien de tours la boucle effectue-t-elle ?
Peut-on en déduire que ce programme s'arrête ? Justifie.

Indice 1

Écris les valeurs successives de i : 1, 2, 4, ...

Indice 2

i double à chaque tour : il finira par dépasser 99.

Voir la correction pas à pas

Valeurs de i au début de chaque tour : 1, 2, 4, 8, 16, 32, 64. Pour ces 7 valeurs, i < 100 est vrai, donc 7 tours.
Après le septième tour, i vaut 128. La condition 128 < 100 est fausse : la boucle s'arrête.
Le programme s'arrête car i double à chaque tour et dépasse donc 100 en un nombre fini de tours. La fonction qui renvoie ce nombre de tours est donc calculable.
Réponse : 7 tours.

Pour prouver qu'une boucle while se termine, on identifie une quantité qui évolue dans un sens et finit par rendre la condition fausse. C'est la justification attendue pour dire qu'un programme s'arrête.

Exercice 3 Tester la primalité avec peu de divisions

★★☆Environ 12 min

Pour décider si un entier $n \geq 2$ est premier, on teste seulement les diviseurs $d$ tels que $2 \leq d \leq \lfloor\sqrt{n}\rfloor$ .

Écris la fonction Python correspondante.
Pour $n = 97$ , combien de diviseurs candidats faut-il tester au maximum ?
Ce problème est-il décidable ? Pourquoi ?

Indice 1

Pour $97$ , calcule d'abord la partie entière de $\sqrt{97}$ .

Indice 2

Compte les entiers de $2$ à cette valeur incluse.

Voir la correction pas à pas

Fonction : def est_premier(n): d = 2, puis while d * d <= n: avec if n % d == 0: return False et d += 1 ; on termine par return True.
Pour $n = 97$ : $\sqrt{97} \approx 9{,}85$ , donc la partie entière vaut $9$ .
Les diviseurs candidats sont $2, 3, 4, 5, 6, 7, 8, 9$ : il y en a $9 - 2 + 1 = 8$ au maximum.
Le problème est décidable : la boucle s'arrête toujours, car $d$ augmente de $1$ à chaque tour et $d \times d$ finit par dépasser $n$ ; le programme renvoie la bonne réponse.

Ce programme est plus rapide que l'essai de tous les entiers jusqu'à $n-1$ , mais la décidabilité était déjà acquise avec la version lente. La rapidité relève de la complexité, pas de la calculabilité.

Exercice 4 Que se passe-t-il avec un « détecteur de boucles » ?

★★★Environ 15 min

Un collègue prétend avoir écrit arrete(prog, donnee) qui répond toujours True ou False correctement. Pour le mettre à l'épreuve, tu écris :

def test(prog):
    if arrete(prog, prog):
        while True:
            pass
    return 1

Que renvoie arrete(test, test) si test(test) s'arrête ?
Même question si test(test) boucle indéfiniment.
Que conclus-tu sur le collègue ?

Indice 1

Applique test à son propre texte et regarde ce que fait la condition if.

Indice 2

Traite les deux cas séparément et cherche chaque fois une contradiction.

Voir la correction pas à pas

Cas où test(test) s'arrête : alors arrete(test, test) doit renvoyer True. Mais dans ce cas le if est vrai et test(test) entre dans la boucle infinie, donc ne s'arrête pas : contradiction.
Cas où test(test) boucle indéfiniment : alors arrete(test, test) doit renvoyer False. Mais alors le if est faux, le programme renvoie 1 et s'arrête : contradiction.
Les deux cas sont absurdes. Aucune fonction arrete qui répond toujours juste ne peut exister : le collègue se trompe, ou sa fonction ne se termine pas toujours.

C'est la preuve de Turing sous une autre forme : appliquer un programme à sa propre description et inverser la réponse annoncée. Elle montre que le problème de l'arrêt est indécidable.

Les questions qu'on se pose

Comment savoir si un problème est décidable à l'examen ?

Cherche d'abord un programme qui répond toujours : boucles bornées, parcours d'une structure finie, calcul direct. Si tu en trouves un et que tu justifies sa terminaison, le problème est décidable. Si la question concerne le comportement de programmes quelconques (arrêt, résultat), pense au problème de l'arrêt et au théorème de Rice : ces questions sont en général indécidables.³

Quelle différence entre calculable et décidable ?

« Calculable » s'applique à une fonction, « décidable » à un problème de décision. Les deux notions sont liées : un problème de décision est décidable exactement quand le prédicat associé est calculable.¹

Si on ne trouve pas d'algorithme, le problème est-il indécidable ?

Non. Ne pas avoir trouvé d'algorithme prouve seulement qu'on n'a pas encore réussi. L'indécidabilité se démontre, par exemple avec une preuve par l'absurde comme celle de Turing pour le problème de l'arrêt.³²

Un langage plus puissant peut-il décider plus de problèmes ?

Non, pour les langages de programmation usuels : les résultats de la calculabilité ne dépendent pas du langage choisi, et tous les modèles de calcul connus sont équivalents.² Un programme dans un langage peut être traduit dans un autre.

Les compilateurs et débogueurs ne contredisent-ils pas le problème de l'arrêt ?

Non. Ils analysent des cas particuliers ou acceptent de ne pas conclure. Le théorème interdit seulement un outil parfait qui répondrait correctement pour tout programme d'un langage puissant.³

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.

Signaler une erreur sur cette page

Calculabilité et décidabilité : cours de Terminale NSI

L'essentiel

Pourquoi se demander ce qu'un programme peut calculer

Fonction calculable : une définition précise

Problème de décision et décidabilité

Pourquoi le langage choisi n'a pas d'importance

Le problème de l'arrêt

Conséquences : ce qu'aucun outil ne pourra faire

Décidable en théorie, impossible en pratique : calculabilité et complexité

Méthodes et pièges pour le bac

Exercices corrigés

Exercice 1 Décidable ou non ? Justifier

Exercice 2 Compter les tours d'une boucle

Exercice 3 Tester la primalité avec peu de divisions

Exercice 4 Que se passe-t-il avec un « détecteur de boucles » ?

Quiz

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur