Programme comme donnée, calculabilité et décidabilité (Bac NSI)
Mis à jour le · AprenAI
Ce thème tombe rarement, mais il pèse lourd : dans les annales digitalisées, un seul sujet, l'exercice 1 de Métropole France 2 remplacement 2024, lui est consacré, et il vaut 6 points. Il demande de dire si des appels de fonction terminent, puis de démontrer par l'absurde qu'aucun programme ne peut décider à coup sûr si un autre programme termine : c'est le problème de l'arrêt.
- 2 sujets officiels
- 0,4 % des sujets
- 2024-2025 années
Qu'est-ce que la décidabilité et le problème de l'arrêt ?
Un programme est une suite de caractères : on peut donc le stocker dans une chaîne, le passer en argument à une autre fonction, l'analyser ou l'exécuter. C'est ce que signifie « programme comme donnée ». Un interpréteur Python, un compilateur ou un antivirus manipulent des programmes comme des données.
On dit qu'un appel f(x) termine lorsque son évaluation renvoie une valeur au bout d'un nombre fini d'étapes, et qu'il ne termine pas s'il peut effectuer des instructions à l'infini. Deux sources de non-terminaison apparaissent au programme : une boucle while dont la condition ne devient jamais fausse, et une fonction récursive dont les appels n'atteignent jamais le cas de base. Dans le sujet 2024, f1 contient while i != 10 : i = i + 1. L'appel f1(7) termine (i vaut 7, 8, 9, 10) et f1(-2) aussi, mais f1(12) ne termine pas, car i croît sans jamais valoir 10. L'ensemble des entiers pour lesquels f1(n) termine est n ≤ 10. Pour f2(n), qui renvoie n + f2(n-2) avec le cas de base n == 0, f2(4) termine et renvoie 6, tandis que f2(5) ne termine pas : les arguments 5, 3, 1, -1... sautent le cas de base. Seuls les entiers naturels pairs conviennent.
Un problème est décidable s'il existe un algorithme qui répond toujours, par oui ou non, en un nombre fini d'étapes. Le problème de l'arrêt demande : peut-on écrire une fonction arret(code_f, x) qui renvoie True si f(x) termine et False sinon ? La réponse est non. La preuve est par l'absurde. On suppose arret écrite et on définit paradoxe(x) : si arret(x, x) alors infini(42) sinon return 0. On étudie paradoxe(code_paradoxe). Si arret renvoie True, le programme exécute infini(42) et ne termine pas, ce qui contredit la réponse True. Si arret renvoie False, il exécute return 0 et termine, ce qui contredit False. Dans les deux cas arret se trompe : une telle fonction ne peut pas exister. Le problème de l'arrêt est donc indécidable.
Conséquence pratique : il n'existe pas de programme parfait qui détecterait tous les bugs de boucle infinie dans tous les programmes. On peut le faire pour des cas particuliers (une boucle avec un variant), pas en général.
- Terminaison: Propriété d'un appel de fonction qui s'arrête après un nombre fini d'étapes.
- Variant de boucle: Quantité entière positive qui décroît strictement à chaque tour de boucle et prouve ainsi que la boucle s'arrête.
- Cas de base: Cas d'une fonction récursive qui ne fait plus d'appel récursif et renvoie directement un résultat.
- Problème décidable: Problème pour lequel il existe un algorithme qui termine toujours et donne la bonne réponse oui ou non.
- Problème de l'arrêt: Question de savoir si un programme donné, sur une entrée donnée, termine : elle est indécidable.
- Raisonnement par l'absurde: On suppose le contraire de ce qu'on veut prouver et on en déduit une contradiction.
À ne pas confondre en calculabilité
- Terminer ≠ Renvoyer le bon résultat: Terminer veut dire s'arrêter en un nombre fini d'étapes ; un programme peut terminer et se tromper, ou ne jamais terminer.
- Décidable ≠ Calculable: Une fonction est calculable si un algorithme la calcule ; un problème de décision est décidable si un algorithme répond toujours oui ou non. Le problème de l'arrêt n'est pas décidable.
- Boucle infinie ≠ Récursion infinie: La première vient d'un while dont la condition reste vraie ; la seconde, d'appels récursifs sans cas de base atteint, qui finit en erreur de profondeur maximale de récursion.
- Cas particulier ≠ Cas général: On sait prouver la terminaison d'un programme précis avec un variant ; on ne peut pas écrire un algorithme qui le fait pour tous les programmes.
| Fonction | Appel | Termine ? | Pourquoi |
|---|---|---|---|
| f1 (while i != 10) | f1(7) | Oui | i prend 7, 8, 9, 10 |
| f1 (while i != 10) | f1(12) | Non | i dépasse 10 sans jamais valoir 10 |
| f2 (n + f2(n-2)) | f2(4) | Oui | appels f2(4), f2(2), f2(0), résultat 6 |
| f2 (n + f2(n-2)) | f2(5) | Non | arguments 5, 3, 1, -1... sans jamais atteindre 0 |
Mode Bac : ce qui rapporte des points
- Valeurs successives: Listez-les explicitement : 7, 8, 9, 10 pour f1(7) ; 12, 13, 14, 15, 16 pour les cinq premières valeurs de f1(12).
- Condition de terminaison: f1(n) termine pour n ≤ 10 ; f2(n) termine pour les entiers naturels pairs.
- Phrase clé du problème de l'arrêt: Il n'existe pas de fonction arret qui réponde correctement pour tous les programmes : le problème de l'arrêt est indécidable.
- Structure de la preuve: Raisonnement par l'absurde ; étude de paradoxe(code_paradoxe) ; deux cas (True, False) ; contradiction dans les deux cas.
- Fonction qui ne termine jamais: def infini(n): return infini(n), sans cas de base.
Comment le Bac NSI interroge-t-il sur la décidabilité ?
Un seul sujet digitalisé : Métropole France 2 remplacement, 2024, exercice 1, 6 points. C'est un exercice entier, construit en trois parties qui montent en difficulté, comme le font souvent les sujets de NSI. Les questions de début sont très accessibles, ce qui permet de sécuriser des points même sans maîtriser la preuve finale.
- Partie A : boucle while (1): Valeurs successives de i, terminaison de f1(7), f1(-2), f1(12), puis condition générale sur n. Il s'agit d'exécuter le code à la main.
- Partie B : fonction récursive (1): Terminaison de f2(4) et f2(5), ensemble des entiers pour lesquels f2 termine, écriture d'une fonction infini qui ne termine jamais.
- Partie C : problème de l'arrêt (1): On suppose une fonction arret et on étudie paradoxe(code_paradoxe) : ligne exécutée, terminaison dans chaque cas, puis conclusion de la contradiction.
- Exercice 1 · Métropole 2 remplacement 2024 · Partie A : boucle while
- Exercice 1 · Métropole 2 remplacement 2024 · Partie B : fonction récursive
- Exercice 1 · Métropole 2 remplacement 2024 · Partie C : problème de l'arrêt
Entraîne-toi : Programme comme donnée, calculabilité et décidabilité (2 sujets officiels)
Tous les sujets de NSI sur « Programme comme donnée, calculabilité et décidabilité » (2024-2025), avec le corrigé.
Comment démontrer que le problème de l'arrêt est indécidable ?
Exemple : Métropole France 2 remplacement, 2024, exercice 1, partie C. On suppose que arret(code_f, x) existe et on utilise paradoxe(x) : si arret(x, x), alors infini(42), sinon return 0.
- Poser l'hypothèse: Écrire clairement : « Supposons qu'il existe une fonction arret telle que arret(code_f, x) renvoie True si f(x) termine et False sinon. »
- Lire la fonction paradoxe: Elle appelle arret(x, x) : le programme est donné à lui-même comme argument. Si le test est vrai, elle appelle infini(42), qui ne termine jamais ; sinon elle renvoie 0.
- Étudier le premier cas: Si arret(code_paradoxe, code_paradoxe) renvoie True, l'appel paradoxe(code_paradoxe) exécute la ligne infini(42) : il ne termine pas. Or True disait qu'il termine : contradiction.
- Étudier le second cas: Si arret renvoie False, le programme exécute return 0 et termine. Or False disait qu'il ne termine pas : contradiction.
- Conclure: Dans les deux cas arret donne une réponse fausse : l'hypothèse est absurde. Aucune fonction arret ne peut exister, le problème de l'arrêt est indécidable.
- Cas des parties A et B: Écrivez les valeurs prises par la variable à chaque appel. Pour f2(5) : 5, 3, 1, -1... n reste impair, donc n == 0 n'est jamais vrai.
Quelles erreurs éviter sur la décidabilité ?
Le corrigé de ce sujet est une réponse type sans barème détaillé : il attend des réponses exactes aux questions fermées (oui/non, valeur) et une justification propre à la fin.
- Répondre « oui » trop vite: f1(12) ne termine pas, même si l'on pense que « i va finir par valoir 10 » : i part de 12 et ne fait qu'augmenter.
- Oublier les cas impairs: Pour f2, la réponse « tous les entiers naturels » est fausse : les impairs ne terminent pas. La bonne réponse est les entiers naturels pairs.
- Ne traiter qu'un seul cas de la preuve: Il faut examiner True puis False. Avec un seul cas, la contradiction n'est pas démontrée.
- Mélanger la ligne exécutée et la valeur renvoyée: Si le test est vrai, la ligne exécutée est infini(42) ; sinon c'est return 0 : indiquez la ligne demandée.
- Écrire infini avec un cas d'arrêt: La fonction infini doit ne terminer pour aucun n : pas de if qui renvoie une valeur.
- Confondre « difficile » et « indécidable »: Indécidable ne veut pas dire que personne n'a trouvé l'algorithme : on prouve qu'aucun algorithme ne peut exister.
Comment réviser la calculabilité et la décidabilité ?
- Savoir tracer une boucle et une récursion: Entraînez-vous à écrire les valeurs successives d'une variable, puis la suite des arguments d'une fonction récursive.
- Retenir la notion de variant: Un entier positif qui décroît strictement à chaque tour : c'est l'argument de terminaison attendu dans ce thème et dans les exercices de recherche dichotomique.
- Apprendre la preuve par cœur: Hypothèse, paradoxe, deux cas, contradiction. Elle tient en cinq lignes et peut être rejouée sur n'importe quelle variante.
- Refaire le sujet 2024: Il est court mais complet : cachez la solution et rédigez les parties A, B et C.
- Pratiquer sur AprenAI: Faites l'exercice officiel de ce thème et corrigez-vous avec la solution rédigée.
Qu'est-ce que le problème de l'arrêt ?
C'est la question de savoir si l'on peut écrire un programme qui, pour n'importe quel programme et n'importe quelle entrée, dit si l'exécution termine. La réponse est non : le problème est indécidable.
Comment prouver qu'une fonction récursive termine ?
Il faut montrer que l'argument décroît à chaque appel et finit par atteindre le cas de base. Pour f2(n) = n + f2(n-2), cela marche pour les entiers pairs mais pas pour les impairs.
Qu'est-ce qu'un problème décidable ?
Un problème pour lequel un algorithme répond toujours par oui ou non en un nombre fini d'étapes. Savoir si un entier est pair est décidable ; savoir si un programme quelconque termine ne l'est pas.
Combien de sujets du Bac NSI portent sur la décidabilité ?
Dans les annales digitalisées, un seul : l'exercice 1 de Métropole France 2 remplacement, 2024, noté sur 6 points.
Pourquoi un programme peut-il être une donnée ?
Parce qu'un code source est un texte : on peut le stocker dans une chaîne de caractères, le passer en argument et l'analyser avec un autre programme, comme le fait arret(code_f, x).
Plus sur l'épreuve de NSI
- Piles, files, listes et dictionnaires · 66 sujets
- Programmation orientée objet · 46 sujets
- Arbres et arbres binaires de recherche · 50 sujets
- Graphes : modélisation et parcours · 27 sujets
- Bases de données et SQL · 83 sujets
- Binaire, entiers et opérateurs booléens · 16 sujets
- Architectures matérielles et systèmes d'exploitation · 32 sujets
- Réseaux : adressage IP et sous-réseaux · 39 sujets
- Protocoles de routage : RIP et OSPF · 51 sujets
- Sécurisation des communications : chiffrement et HTTPS · 9 sujets
- Récursivité · 24 sujets
- Modularité, API et paradigmes de programmation · 6 sujets
- Mise au point des programmes : bugs, assertions et tests · 13 sujets
- Diviser pour régner · 8 sujets
- Programmation dynamique · 7 sujets
- Recherche textuelle et algorithme de Boyer-Moore · 3 sujets
- Coût des algorithmes, tris et recherche · 23 sujets