Aller au contenu

Problème de l'arrêt (Bac 🎯)⚓︎

Licence Creative Commons
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.

programme

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

🔖 Synthèse de ce qu'il faut retenir pour le bac

On ne peut pas tout calculer : le problème de l'arrêt⚓︎

Le problème de l'arrêt est indécidable

Le problème de l'arrêt peut se formuler ainsi :

Énoncé du problème de l'arrêt

On considère la fonctionarret telle que pour tout couple d'arguments constitué d'un algorithme f et d'une entrée e, renvoie :

  • arret(f, e) renvoie True si l'algorithme f appliqué à e se termine
  • arret(f, e) renvoie False sinon

Existe-t-il un algorithme qui permet de calculer arret(f, e) pour tout couple d'arguments f et e. Autrement dit, la fonction arret est-elle calculable et plus précisément décidable puisqu'elle est à valeurs booléennes ?

Dans son article "On Computable Numbers, with an Application to the Entscheidungsproblem" publié en janvier 1937, Alan Turing a démontré que la fonction arret est indécidable. Il en a déduit que l'Entscheidungsproblem est indécidable.

Importance du résultat

Le fait que le problème de l'arrêt est indécidable fixe une limite dure et universelle au pouvoir des algorithmes : on ne peut pas tout calculer !

alt

Programme impossible qui teste si un programme s'arrête sur son entrée, source : Fschwarzentruber, Wikipedia CC BY-SA 4.0 Deed

Exercice 4

Source : le manuel NSI et le manuel de MP2I/MPI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen

Si on admet la thèse de Church-Turing et le fait que le langage Python soit Turing complet, il est équivalent de démontrer l'indécidabilité du problème de l'arrêt dans le langage Python plutôt qu'avec une machine de Turing.

La fonction d'arrêt est calculable si et seulement si elle peut représenter sous la forme d'une fonction Python (\(=\) un algorithme). La question de la décidabilité du problème de l'arrêt peut alors se formuler ainsi :

Énoncé du problème de l'arrêt en Python

Existe-t-il une fonction Python arret telle que pour tout couple d'arguments constitué d'une fonction Python f et d'une entrée e, arret(f, e) renvoie True si f(e) se termine et False sinon ?

La preuve de Turing est un raisonnement par l'absurde qui repose sur l'utilisation d'un argument diagonale. On suppose que la fonction arret existe et on considère la fonction paradoxe qui prend en entrée un entier n :

🐍 Script Python
def paradoxe(n):
    if arret(paradoxe, n):
        while True:
            pass
    else:
        return n

Par la suite on choisit 42 comme valeur du paramètre n.

question 1

Dans un premier cas on considère que paradoxe(42) se termine. Montrer qu'on aboutit à une contradiction.

Si paradoxe(42) se termine alors arret(paradoxe, 2) renvoie True et la première branche de l'instruction conditionnelle est exéxutée, ce qui conduit à une boucle infinie. Dans ce cas, la fonction ne se termine pas et on aboutit donc à une contradiction.

question 2

Dans un second cas on considère que paradoxe(42) ne se termine pas. Montrer qu'on aboutit aussi à une contradiction.

Si paradoxe(42) ne se termine pas alors arret(paradoxe, 2) renvoie False et la seconde branche de l'instruction conditionnelle est exéxutée, ce qui conduit à l'exécution d'un return et la fonction se termine. . De nouveau on aboutit à une contradiction.

question 3

Conclure sur la décidabilité du problème de l'arrêt.

Dans les deux cas possibles de terminaison ou non terminaison de paradoxe(42), on aboutit à une contradiction. Donc l'hypothèse de départ de l'existence de la fonction Python arret est fausse. C'est un exemple de raisonnement par l'absurde. On en déduit que la fonction Python arret n'existe pas et donc la fonction qui détermine si un algorithme quelconque s'arrête sur son entrée n'est pas calculable. Comme c'est une fonction à valeurs booléennes, on dit qu'elle n'est pas décidable.

Évidemment, la preuve peut se faire avec un autre entier que 42 !

alt

42 la réponse à la grande question sur la vie, l'Univers et le reste, source : Wikipedia

Exercice 5

Source : le manuel NSI et le manuel de MP2I/MPI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen

Question 1

Montrer qu'il n'existe pas de fonction Python prenant en paramètre une fonction Python f sans paramètre et renvoyant True si et seulement si l'exécution de f() s'arrête.

On suppose qu'il existe une fonction arret qui prend en paramètre une fonction Python f et renvoie True si et seulement si f() se termine. On considère la fonction :

🐍 Script Python
def paradoxe():
    if arret(paradoxe):
        while True:
            pass
    else:
        return n

Premier cas : paradoxe() se termine.

Dans ce cas arret(paradoxe) renvoie True, donc la première branche de l'instruction conditionnelle est exécutée, donc la boucle infinie s'exécute et paradoxe() ne se termine pas. On aboutit à une contradiction.

Second cas : paradoxe() ne se termine pas.

Dans ce cas arret(paradoxe) renvoie False, donc la second branche de l'instruction conditionnelle est exécutée, donc le return s'exécute et paradoxe() se termine. On aboutit de nouveau à une contradiction.

Dans les deux cas possibles, on aboutit à une contradiction, donc l'hypothèse de départ de l'existence de la fonction arret est fausse. C'est un exemple de raisonnement par l'absurde.

Exercice 6

Source : sujet initial de Fabien Perez partagé sur le Forum des enseignants de NSI puis modifié par Martin Fontaine (pseudo Websciences) et Jules Saget (pseudo Lemnis).

On donne la définition suivante utilisée dans cet exercice :

Deux fonctions f et g sont dites équivalentes sur l'entrée e si :

  • soit les exécutions de f(e) et de g(e) terminent et produisent le même résultat, c'est-à-dire f(e) = g(e) ;
  • soit les exécutions de f(e) et de g(e) ne se terminent pas.

On considère les fonctions f, g et h données ci-dessous.

🐍 Script Python
def f(n):
    if n == 0:
        return True
    elif n == 1:
        return False
    else:
        return f(n - 2)

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

def h(n):
    while True:
        x = 1
    return n%2 == 0

Question 1

Justifier que les fonctions f et g sont équivalentes sur l'entrée 3.

f(3)= f(3 - 2)= f(1) = False et g(3) = (n%2 == 0) = False. Par définition, f et g sont équivalentes sur l'entrée 3 car f(3) et g(3) se terminent et renvoient la même valeur.

Question 2

Montrer que les fonctions g et h ne sont équivalentes sur aucune entrée n.

Pour tout entier n :

  • l'exécution de h(n) conduit à une boucle infinie donc h(n) ne se termine pas
  • mais g(n)se termine et renvoie True si n est pair et False sinon.

Par définition g et h ne sont pas équivalentes car l'une se termine toujours et l'autre jamais.

Question 3

Donner un entier x tel que f et g ne sont pas équivalentes sur l'entrée x. Justifier.

f(-1)=f(-3)=f(-5)=f(-7) = ... on a une descente infinie qui ne converge jamais vers l'un des cas de base 0 ou 1. Donc f(-1) ne se termine pas, alors que g(-1)=((-1) % 2 == 0)=False donc g(-1) se termine et renvoie False.

Par définition, f et g ne sont donc pas équivalents sur l'entier -1.

Alonzo affirme avoir codé une fonction équivalent(p1, p2, x) qui prend en argument deux fonctions p1 et p2 et une entrée x et qui renvoie un booléen indiquant si p1 et p2 sont équivalentes sur l'entrée x.

Il affirme de plus que l'exécution de la fonction équivalent termine toujours.

Ada décide d'utiliser la fonction codée par Alan dans son programme :

🐍 Script Python
from code_alonzo import équivalent

def boucle_infinie(x):
    while True:
        print("∞")

def test(p, x):
    if équivalent(p, boucle_infinie, x):
        return False
    else:
        return True

Question 4

Justifier brièvement que, si la fonction d'Alan est correcte, l'exécution de test(p, x) termine toujours.

On suppose que la fonction d'Alan est correcte. Prenons deux valeurs de p et x et exécutons test(p, x). L'évaluation de équivalent(p, boucle_infinie, x) se termine car la fonction d'Alan est correcte, donc elle conduit à un return dans l'une des deux branches de l'instruction conditionnelle. Par conséquentl'exécution de test(p, x) se termine et ce quelles que soient les valeurs de p et x.

Question 5

Si la fonction d'Alonzo est correcte, que renvoie la fonction test(p, x) lorsque p s'arrête sur l'entrée x ?

Si la fonction d'Alonzo est correcte et si p s'arrête sur l'entrée x, alors équivalent(p, boucle_infinie, x) renvoie False puisque p(x) se termine mais pas boucle_infinie(x). Donc la seconde branche de l'instruction conditionnelle est exécutée et test(p, x) renvoie True.

Question 6

Même question que la précédente si p ne s'arrête pas sur l'entrée x.

Si la fonction d'Alonzo est correcte et si p ne s'arrête pas sur l'entrée x, alors équivalent(p, boucle_infinie, x) renvoie True puisque p(x) et boucle_infinie(x) ne se terminent pas. Donc la première branche de l'instruction conditionnelle est exécutée et test(p, x) renvoie False.

Question 7

En déduire ce que fait la fonction test.

La fonction test prend en argument une fonction Python p et son entrée x et renvoie True si p(x) se termine (cas de la question 5) et False si p(x) ne se termine pas (cas de la question 6). Par conséquent la fonction test décide le problème de l'arrêt. On aboutit à une contradiction car Alan Turing a démontré que le problème de l'arrêt est indécidable

Question 8

Que peut-on en conclure sur la fonction équivalent écrite par Alonzo ?

En supposant qu'il existe une 'fonction équivalente correcte, on aboutit à une contradiction avec l'indécidabilité du problème de l'arrêt. Par conséquent il n'existe pas de fonction équivalente correcte. C'est un exemple de raisonnement par l'absurde.

Une autre preuve de l'Entscheidungsproblem

À la même époque qu'Alan Turing, Alonzo Church démontre de façon indépendante qu'il ne peut exister de fonction calculable qui prend en arguments deux fonctions \(f\) et \(g\) et détermine leur équivalence : en renvoyant True si pour toute entrée e telle que f(e) se termine alors f(e) = g(e) et False sinon. À partir de ce premier problème indécidable, il démontre que l'Entscheidungsproblem est indécidable.