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.

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.

À ne pas confondre en calculabilité

FonctionAppelTermine ?Pourquoi
f1 (while i != 10)f1(7)Ouii prend 7, 8, 9, 10
f1 (while i != 10)f1(12)Noni dépasse 10 sans jamais valoir 10
f2 (n + f2(n-2))f2(4)Ouiappels f2(4), f2(2), f2(0), résultat 6
f2 (n + f2(n-2))f2(5)Nonarguments 5, 3, 1, -1... sans jamais atteindre 0

Mode Bac : ce qui rapporte des points

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.

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.

  1. 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. »
  2. 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.
  3. É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.
  4. É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.
  5. 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.
  6. 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.

Comment réviser la calculabilité et la décidabilité ?

  1. 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.
  2. 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.
  3. 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.
  4. Refaire le sujet 2024: Il est court mais complet : cachez la solution et rédigez les parties A, B et C.
  5. 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