Exercice calculabilite bac

Exercice 1⚓︎

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 2⚓︎

Sujet de bac Asie jour 1 session 2025

Décidabilité, algorithmique et programmation Python

En Python, on peut utiliser le triple guillemet pour écrire une chaîne de caractères sur plusieurs lignes. Par exemple, on peut définir une variable programme1 qui contient la chaîne de caractères correspondant à un petit programme Python de la manière suivante :

programme1 = """
x = 10
y = 10
while x > 0:
    x = x - 1
    y = y + 1
"""

De même, on peut définir la variable programme2 :

programme2 = """
def boucle_infinie():
    while True:
        pass # Ne rien faire
boucle_infinie()
"""

1. On suppose que l'on exécute le programme contenu dans la variable programme1. Donner les valeurs de x et de y après exécution de ce programme.

Réponse

x vaut 0 et y vaut 20.

2. Expliquer pourquoi tout programme Python peut être vu comme une chaîne de caractères.

Réponse

Un fichier Python est un fichier texte, on peut donc le percevoir comme une chaine de caractères.

En Python, la fonction exec permet d'exécuter le programme correspondant à une chaîne de caractères passée en paramètre.

>>> exec("r = 42")
>>> r
42
>>> exec(programme1)
>>> x + y
20
>>> exec(programme2)
[ne termine pas]

On considère les quatre variables programme3, programme4, programme5 et programme6 suivantes :

programme3 = """
x = 10
while x != 0:
    x = x - 2
"""

programme4 = """
x = 10
while x > 0:
    x = x + 2
"""

programme5 = """
x = 10
while x < 0:
    x = x + 4
"""

programme6 = """
x = 10
while x != 0:
    x = x - 4
"""

3. On exécute les variables programme3, programme4, programme5 et programme6 avec la fonction exec. Déterminer lesquelles terminent et lesquelles ne terminent pas.

Réponse

Les programmes 3 et 5 terminent.

Les programmes 4 et 6 ne terminent pas.

On cherche à écrire une fonction arret telle que arret(programme) renvoie True si exec(programme) termine et False si exec(programme) ne termine pas. Cette fonction arret doit donc s'arrêter dans tous les cas.

4. Indiquer ce que réalise le programme suivant et s'il permet de répondre au problème posé ci-dessus.

def arret_essai1(programme):
    exec(programme)
    return True

Réponse

Ce programme ne répond pas au problème car si le programme ne s'arrête pas (à la ligne 2), le programme ne renverra jamais False.

On suppose disposer d'une fonction recherche(mot, texte) qui renvoie True si une chaîne de caractères mot est présente dans une chaîne de caractères texte et False sinon.

5. Expliquer succinctement le principe de l'algorithme de Boyer-Moore qui permet d'implémenter cette fonction recherche.

Réponse

L'algorithme de Boyer-Moore est un algorithme de recherche de texte qui utilise un dictionnaire pour faire des décalages intelligents et ainsi accélérer la recherche.

Une idée est d'écrire une fonction qui décrète qu'un programme s'arrête s'il ne contient pas de while et ne s'arrête pas s'il en contient un.

6. Écrire une fonction arret_essai2(programme) qui renvoie True si la chaîne de caractères "while" n'est pas utilisée dans la chaîne de caractères programme et False sinon.

Réponse

    def arret_essai2(programme):
        return not recherche('while', programme)

7. Montrer qu'il est possible que :

arret_essai2(programme) renvoie True alors que le programme ne s'arrête pas ;
arret_essai2(programme) renvoie False alors que le programme s'arrête.

Indication : il n'y a pas que les boucles while qui peuvent poser des problèmes de non terminaison.

Réponse

Avec le programme suivant :

def programme():
    programme()

arret_essai2(programme) renverra True alors que le programme ne s'arrête pas.

Avec le programme suivant :

def programme():
    n = 3
    while n > 0:
        print(n)
        n -= 1

arret_essai2(programme) renverra False alors que le programme s'arrête.

Nos tentatives pour écrire une telle fonction arret sont restées vaines. Nous allons montrer qu'il est en réalité impossible d'écrire une telle fonction. On va supposer qu'une telle fonction arret existe. On va montrer que cette supposition aboutit à un paradoxe ce qui prouvera que la supposition est fausse.

8. Écrire une fonction terminaison_inverse telle que l'appel terminaison_inverse(programme) termine si la chaîne de caractères programme représente un programme qui ne termine pas et ne termine pas si la chaîne de caractères programme représente un programme qui termine. On pourra utiliser la fonction boucle_infinie de programme2 ainsi bien sûr que la fonction arret dont on a supposé l'existence.

Réponse

def terminaison_inverse(programme):
    if arret(programme) == True:
        boucle_infinie()
    else:
        print('stop')

On considère "terminaison_inverse(programme_paradoxal)" qui n'est rien d'autre qu'une chaîne de caractères, et on définit une variable que l'on appelle programme_paradoxal à laquelle on affecte cette chaîne de caractères :

programme_paradoxal = "terminaison_inverse(programme_paradoxal)"

9. Étudier si le programme paradoxal termine ou non, c'est-à-dire si exec(programme_paradoxal) termine ou non.

Réponse

Si programme_paradoxal termine, alors terminaison_inverse(programme_paradoxal) ne termine pas.

Si programme_paradoxal ne termine pas, alors terminaison_inverse(programme_paradoxal) termine.

10. Indiquer ce que l'on peut conclure sur la fonction arret.

Réponse

La question 9. a abouti à une contradiction. Celle-ci est due à la non-existence de la fonction arret.

11. Expliquer si l'impossibilité d'écrire une telle fonction arret est due aux limitations du langage Python.

Réponse

Cette impossibilité n'est pas due aux limitations du langage Python. Elle est générale, et a été démontrée en 1936 par Alan Turing sous le nom Théorème de l'arrêt.

Crédits⚓︎

Gilles Lassus

Exercice calculabilite bac

Exercice 1⚓︎

Partie A : boucle while⚓︎

Partie B : fonction récursive⚓︎

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

Crédits⚓︎

Exercice 2⚓︎

Crédits⚓︎

Partie A : boucle `while`⚓︎