Exercice calculabilite bac

D'après le sujet de bac du 12 septembre 2024, Métropole, J2, Exercice 1 (24-NSIJ2ME3)

Cet exercice porte sur l’exécution d’un programme Python et sur la décidabilité.

Dans cet exercice, on dira qu’un appel f(x), où f est une fonction Python prenant un argument et x est une valeur, termine lorsque l’évaluation de f(x) renvoie toujours une valeur au bout d’un nombre fini d’étapes. À l'opposé, un tel appel ne termine pas s'il est possible qu'il effectue des instructions à l'infini.

Partie A : boucle `while`⚓︎

Commençons par un premier exemple, avec une fonction prenant un entier en argument et utilisant une boucle while.

def f1(n):
    i = n
    while i != 10:
        i = i + 1
    return i

1. Sur votre copie, donner les valeurs successives de la variable i lors de l'exécution de f1(7) et indiquer si f1(7) termine.

Réponse

i = 7 : initialisation
i = 8, puis le test i != 10 est vrai
i = 9, puis le test i != 10 est vrai
i = 10, puis le test i != 10 est faux
La fonction renvoie 10.

f1(7) termine donc et renvoie 10.

2. Indiquer si l'appel f1(-2) se termine. Si oui, indiquer la valeur renvoyée.

Réponse

i = -2 : initialisation
i = -1, puis le test i != 10 est vrai
i = 0, puis le test i != 10 est vrai
i = 1, puis le test i != 10 est vrai
i = 2, puis le test i != 10 est vrai
...
i = 9, puis le test i != 10 est vrai
i = 10, puis le test i != 10 est faux
La fonction renvoie 10.

f1(-2) termine donc et renvoie 10.

3. Sur votre copie, donner les 5 premières valeurs prises par la variable i lors de l'exécution f1(12), et indiquer si l'appel f1(12) va terminer ou non.

Réponse

i = 12 : initialisation
i = 13, puis le test i != 10 est vrai
i = 14, puis le test i != 10 est vrai
i = 15, puis le test i != 10 est vrai
i = 16, puis le test i != 10 est vrai

f1(12) ne termine donc pas car la condition i != 10 est toujours vraie. On ne sort pas de la boucle while

4. Préciser pour quels entiers n l'appel f1(n) se termine.

Réponse

Pour n <= 10, l'appel f1(n) se termine.
Pour n > 10, l'appel f1(n) ne se termine pas.

Partie B : fonction récursive⚓︎

Prenons maintenant un deuxième exemple, avec une fonction récursive (prenant, elle aussi, un entier en argument).

def f2(n):
    if n == 0:
        return 0
    else:
        return n + f2(n - 2)

5. L'appel f2(4) termine-t-il ? Si oui, indiquer la valeur renvoyée par f2(4) ; sinon, justifier brièvement.

Réponse

f2(4) essaie de calculer 4 + f2(2), donc il y a un appel à f2(2).
f2(2) essaie de calculer 2 + f2(0), donc il y a un appel à f2(0).
f2(0) renvoie immédiatement 0.
f2(2) renvoie alors 2 + 0, donc 2.
f2(4) renvoie alors 4 + 2, donc 6.

f2(4) termine et renvoie 6.

6. L'appel f2(5) termine-t-il ? Si oui, indiquer la valeur renvoyée par f2(5) ; sinon, justifier brièvement.

Réponse

f2(5) essaie de calculer 5 + f2(3), donc il y a un appel à f2(3).
f2(3) essaie de calculer 3 + f2(1), donc il y a un appel à f2(1).
f2(1) essaie de calculer 1 + f2(-1), donc il y a un appel à f2(-1).
f2(-1) essaie de calculer -1 + f2(-3), donc il y a un appel à f2(-3). La condition d'arret if n == 0: n'est jamais atteinte car n ne prend que des valeurs impaires.
f2(5) ne termine pas donc pas.

Remarque

Si on exécute ce code, au bout de 1000 appels récursifs (valeur par défaut) un mécanisme de Python stoppe le programme.
Il s'affiche alors : RecursionError: maximum recursion depth exceeded

7. Déterminer l'ensemble des entiers naturels n pour lesquels l'appel f2(n) termine.

Réponse

L'appel f2(n) termine pour tous les entiers pairs et positifs.

8. Écrire une fonction Python infini, récursive, telle que l'appel infini(n) ne termine pour aucun entier n.

Réponse

def infini(n):
    """n est un entier naturel donc positif ou nul."""
    if n == -1:  # Cette condition ne sera jamais réalisée
        return 0
    else:
        return infini(n + 1)

Une autre réponse possible :

def infini(n):
    return infini(n)

Partie C : le problème de l'arrêt⚓︎

On se demande maintenant s'il est possible d'écrire une fonction arret qui prend en arguments une chaine de caractères code_f contenant le code d'une fonction f et un argument x de f, et tel que arret(code_f, x) renvoie True si l'appel f(x) va terminer et False sinon.

Dans la suite de cet exercice, on suppose disposer d'une fonction arret et on implémente la fonction suivante, utilisant cette fonction arret, ainsi que la fonction infini de la question précédente dont l'appel infini(n) ne termine jamais, quelle que soit la valeur de n.

def paradoxe(x):
    if arret(x, x):
        infini(42)
    else:
        return 0

De même, on suppose disposer d'une variable code_paradoxe contenant le code de la fonction paradoxe sous la forme d'une chaine de caractères, et on s'intéresse à l'appel paradoxe(code_paradoxe).

Cet appel de fonction commence par effectuer le test arret(code_paradoxe, code_paradoxe) dans le if de la ligne 2.

9. Dans le cas où arret(code_paradoxe, code_paradoxe) renvoie True, préciser la prochaine instruction à être exécutée. Dans ce cas, expliquer si l'appel paradoxe(code_paradoxe) termine.

Réponse

Si arret(code_paradoxe, code_paradoxe) renvoie True, alors la prochaine instruction sera infini(42) qui ne termine pas. Cela prouve que l'appel paradoxe(code_paradoxe) ne termine pas.

10. Dans le cas où arret(code_paradoxe, code_paradoxe) renvoie False, préciser la prochaine instruction à être exécutée. Dans ce cas, expliquer si l'appel paradoxe(code_paradoxe) termine.

Réponse

Si arret(code_paradoxe, code_paradoxe) renvoie False, alors la prochaine instruction sera return 0 qui termine. Cela prouve que l'appel paradoxe(code_paradoxe) termine.

11. En déduire qu'une telle fonction arret ne peut exister.

Réponse

Supposons que la fonction arret existe.
arret(code_paradoxe, code_paradoxe) peut renvoyer soit True, soit False.

Supposons que arret(code_paradoxe, code_paradoxe) renvoie True. D'après la question 9. l'appel paradoxe(code_paradoxe) ne termine pas. Donc ce n'est pas possible car il faudrait que arret(code_paradoxe, code_paradoxe) renvoie False, ce qui est en contradiction avec notre hypothèse.
Supposons que arret(code_paradoxe, code_paradoxe) renvoie False. D'après la question 10. l'appel paradoxe(code_paradoxe) termine. Donc ce n'est pas possible car il faudrait que arret(code_paradoxe, code_paradoxe) renvoie True, ce qui est en contradiction avec notre hypothèse.

On a démontré que si la fonction arret existait, ce n'était pas possible. Ceci montre "par l'absurde" que la fonction arret ne peut pas exister.

Crédits⚓︎

La plus grande partie de cet exercice est retranscrite et corrigée par Franck Chambon sous licence cc-by-nc-sa.

Modifications : Mireille Coilhac.

Exercice calculabilite bac

Partie A : boucle while⚓︎

Partie B : fonction récursive⚓︎

Partie C : le problème de l'arrêt⚓︎

Crédits⚓︎

Partie A : boucle `while`⚓︎