🛑 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⚓︎
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
, puisx = 0.3
- Ensuite
x = -0.7
,f1
s'arrête et renvoie-0.7
.
- Après quelques tours de boucle, on a
- Pour
f1(-5.2)
- Après chaque tour de boucle, on a
x < 0
f2
ne s'arrête pas.
- Après chaque tour de boucle, on a
- 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.
- Au test
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.
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")
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")
def f4(x):
return "boucle"
Que se passe-t-il lors des appels suivants ?
f4(+17.3)
f4(-5.2)
f4("boucle")
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
>>> 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
- Une fonction qui contient
while True
boucle-t-elle forcément à l'infini ? - 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
- Si la fonction rencontre un
return
avant la boucle, non. Sinon, tout est possible... - 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 :
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)
: renvoieTrue
sif
s'arrête avecx
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 :
def P(f):
if arret(f, f):
while True:
pass
else:
return 0
- Que produit
P(f4)
? - Que produit
P(f5)
? - 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
>>> 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)
etg(x)
s'évaluent en le même résultat (au sens où, par exemple,f(x) == g(x)
s'évalue enTrue
) ; - ou bien ni
f(x)
nig(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.
-
en référence à Idiocracy, un film d'anticipation, qui est devenu un documentaire avec le temps. ↩