Aller au contenu

🛑 Problème de l'arrêt⚓︎

Jouons un peu avec des fonctions et tordons-les un peu, pour voir.

Pour avoir un avant gout des études supérieures théoriques.

Des fonctions et des erreurs⚓︎

🐍 Script Python
def f1(x):
    while x > 0:
        x = x - 1
    return x

Que se passe-t-il lors des appels suivants ?

  • f1(+17.3)
  • f1(-5.2)
  • f1("boucle")
Réponse
  • Pour f1(+17.3)
    • Après quelques tours de boucle, on a x = 1.3, puis x = 0.3
    • Ensuite x = -0.7, f1 s'arrête et renvoie -0.7.
  • Pour f1(-5.2)
    • Après chaque tour de boucle, on a x < 0
    • f2 ne s'arrête pas.
  • Pour f1("boucle")
    • Au test x > 0 une erreur survient, en effet une string et un entier ne se comparent pas.
    • f2 s'arrête avec une erreur.

3 comportements

  • Une fonction peut terminer et renvoyer son résultat.
  • Une fonction peut entrer dans une boucle infinie.
  • Une fonction peut terminer suite à une erreur.

Un bon logiciel aurait pu prévoir les réponses aux trois questions précédentes, pour cette fonction f1 qui est simple.

🐍 Script Python
def f2(x):
    while x > 0:
        x = x + 1
    return x

Que se passe-t-il lors des appels suivants ?

  • f2(+17.3)
  • f2(-5.2)
  • f2("boucle")
🐍 Script Python
def f3(x):
    x = 1 / x
    while True:
        x = x + 1
    return x

Que se passe-t-il lors des appels suivants ?

  • f3(+17.3)
  • f3(-5.2)
  • f3("boucle")
🐍 Script Python
def f4(x):
    return "boucle"

Que se passe-t-il lors des appels suivants ?

  • f4(+17.3)
  • f4(-5.2)
  • f4("boucle")
🐍 Script Python
def f5(x):
    while True:
        pass

Que se passe-t-il lors des appels suivants ?

  • f5(+17.3)
  • f5(-5.2)
  • f5("boucle")

Fonction code_source⚓︎

Il est possible d'écrire une fonction code_source, et on aurait

🐍 Console Python
>>> print(code_source(f1))
    def f1(x):
        while x > 0:
            x = x - 1
        return x
>>> "while True" in code_source(f2)
False
>>> "while" in code_source(f3)
True

Questions

  1. Une fonction qui contient while True boucle-t-elle forcément à l'infini ?
  2. Pourrait-on envisager un programme qui lit le code source d'une fonction et dit, pour une entrée donnée, si elle s'arrête ou non ? Au moins qui réussirait à répondre sur des exemples très simples.
Réponses
  1. Si la fonction rencontre un return avant la boucle, non. Sinon, tout est possible...
  2. Pour des fonctions très simples, oui, on y arrive. Mais pour certaines fonctions, on n'y arrive pas encore, mais on y arrivera bientôt, la science progresse. Cependant, attention, il faut savoir une chose...

Une tentative de fonction d'arrêt⚓︎

On considère la fonction :

🐍 Script Python
def passur(f, x):
    if "while True" in code_source(f):
        return True
    else:
        return False

À quoi s'attendre, en fonction de x, avec les appels suivants ?

  • passur(f1, x)
  • passur(f2, x)
  • passur(f3, x)
  • passur(f4, x)
  • passur(passur, x)

Est-ce légal de passer une fonction en argument à elle-même ? OUI !

Existence d'une fonction d'arrêt ?⚓︎

On suppose qu'il existe une fonction Python qui peut déterminer (en temps fini) si une fonction f évaluée en x s'arrête ou non. En bref, une fonction un peu plus élaborée que passur 1 qui n'était pas crédible...

arret(f, x) : renvoie True si f s'arrête avec x en paramètre ; False sinon.

Exemples⚓︎

Par exemple, on a : arret(f1, +17.3) qui renvoie True.

Reprendre les questions précédentes sous cet angle.

Le drame⚓︎

On considère la fonction joueuse suivante :

🐍 Script Python
def P(f):
    if arret(f, f):
        while True:
            pass
    else:
        return 0
  1. Que produit P(f4) ?
  2. Que produit P(f5) ?
  3. Que produit P(P) ? Êtes-vous sûr ? Certain ? Mais ... c'est le drame !

Situations similaires

  • Si on considère \(A = \{X \text{ tel que } X \not\subset X\}\), l'ensemble de tous les ensembles qui ne se contiennent pas eux-mêmes.
  • Si on considère le paradoxe du barbier.
  • Si on considère \(\mathbb R\) dénombrable et l'argument diagonal de Cantor.

Remarque

Ce code Python est valide

🐍 Console Python
>>> A = [None, 1, [2, 3]]
>>> A.append(A)
>>> print(A)
[None, 1, [2, 3], [...]]
>>> print(A in A)
True

Ici, A n'est qu'un exemple, mais ce n'est pas un ensemble non plus...

Conclusion⚓︎

Aucune fonction arret(f, x) pouvant toujours déterminer l'arrêt de f en x en temps fini n'existe.

Problèmes indécidables : réduction⚓︎

Étant donné deux fonctions Python f et g et un objet x, on dit que f et g coïncident en x si :

  • ou bien les expressions f(x) et g(x) s'évaluent en le même résultat (au sens où, par exemple, f(x) == g(x) s'évalue en True) ;
  • ou bien ni f(x) ni g(x) ne produisent un résultat (ça boucle indéfiniment).

Question 1

Supposons qu'on vous donne une fonction Python cestpareil telle que cestpareil(f, g, x) renvoie True si f et g coïncident en x et False sinon.

À l'aide de cestpareil, définissez une fonction qui résout le problème de l'arrêt. Déduisez-en que le problème consistant à savoir si deux fonctions Python coïncident en une certaine valeur n'est pas décidable.

Question 2

On dit que f est totale si f(x) s'évalue toujours en un objet. Montrez qu'il n'y a pas de fonction Python qui décide si une fonction est totale.

Ces résultats se généralisent : toute propriété non triviale qui concerne la fonction (au sens mathématique) calculée par une machine de Turing (ou un programme Python) est indécidable. C'est le théorème de Rice.

Question 3

Fixons une fonction Python f. On dit que g implémente f si pour tout objet x, f et g coïncident en x. Montrez qu'il n'y a pas de fonction Python qui décide si une fonction g implémente f.

  • On pourra commencer en ayant fixé f comme étant la fonction constante égale à 0 : lambda x: 0.
  • On pourra ensuite considérer une fonction f totale.
  • On pourra enfin tenter le cas général.

  1. en référence à Idiocracy, un film d'anticipation, qui est devenu un documentaire avec le temps.