Calculabilité - Problème de l’arrêt en Python #

Un programme en tant que donnée #

Terminaison #

On dit qu’une fonction termine si elle renvoie une valeur ou si elle lève une exception (par exemple ZeroDivisionError si une division par zéro est tentée).

Avec cette définition, seulement deux situations peuvent se présenter lorsqu’on appelle une fonction :

Elle termine,

Elle continue de calculer indéfiniment

Ainsi, la fonction ma_fonction (voir ci-dessous), termine pour un entier n inférieur ou égal à 10 (elle renvoie None) et ne termine pas pour n strictement plus grand que 10.

En outre, cette fonction termine pour une chaîne de caractères n (en levant l’exception TypeError à cause de l’opération +).

def ma_fonction(n):
  while n != 10 :
    n = n + 1

De l’utilité d’une fonction `arret` #

On pourrait penser qu’il serait utile d’avoir en Python une fonction arrêt :

qui termine sur toutes les entrées possibles,
telle que arret(f, x) renvoie True si le calcul de f(x) termine
et False sinon.

Une telle fonction, si elle était ajoutée au langage, permettrait d’éviter les boucles infinies en faisant un simple test.

Si on voulait programmer une telle fonction, il serait naturel que la fonction arret accède au code de la fonction f (ce qui est possible grâce au module dis), et analyse ce code, par quelque moyen compliqué, pour en déduire si oui ou non le calcul de f(x) va un jour terminer.

Le Problème de l’arrêt… #

La question :

“Est-il possible de programmer la fonction arret ?”

est connue sous le nom de problème de l’arrêt.

C’est impossible #

Nous allons montrer qu’une telle fonction ne peut pas exister.

Pour cela, nous allons employer un raisonnement par l’absurde.

Hypothèse #

Supposons que quelqu’un ait réussi à programmer cette fonction arret.

def arret(f, x) -> bool:
    """
    Prend une fonction et ses paramètres en entrée.
    * Termine toujours
    * Renvoie `True` si `f(x)` termine
    * Renvoie `False` si `f(x)` ne termine pas.
    """
    ...

La fonction `strange` #

Nous pouvons alors l’utiliser pour programmer la fonction strange suivante :

def strange(f, x):
  if arret(f, x):
    while True:
      pass

Cette fonction teste si le calcul de f(x) termine.

si f(x) termine, elle rentre dans une boucle infinie dans laquelle elle ne fait rien.
Sinon, elle ne fait rien et termine.

Autrement dit, strange(f, x) termine si et seulement si f(x) ne termine pas.

La fonction `paradox` #

La précédente fonction nous permet d’en définir une nouvelle, la fonction paradox.

def paradox(f):
  strange(f, f)

Par construction, le calcul de paradox(f) termine si et seulement si le calcul de f(f) ne termine pas. Appelons (1) cette propriété.

(1) le calcul de paradox(f) termine si et seulement si le calcul de f(f) ne termine pas

`paradox(paradox)` ? #

Maintenant, demandons-nous si le calcul de paradox(paradox) termine.

Pour cela, dans la propriété (1), remplaçons f par paradox.

La propriété devient :

Le calcul de paradox(paradox) termine si et seulement si le calcul de paradox(paradox) ne termine pas.

Cette dernière propriété est évidemment absurde (elle se contredit elle même).

Nous pouvons donc conclure notre raisonnement par l’absurde et affirmer qu’il est impossible de programmer la fonction arret.

Remarque #

Le problème de l’arrêt reste impossible même si on se limite à ce que les arguments de arrêt soient une fonction f des entiers dans les entiers et un entier x.

Pourquoi ? Simplement parce que n’importe quelle valeur de n’importe quel type sera représenté en machine par une suite d’octet, soit à peu près un entier naturel.

Complément #

La résolution du problème de l’arrêt par Alonzo Church et Alan Turing, en 1936 a eu de nombreuses conséquences en informatique et en mathématiques. La résolution de ce problème a conduit Alan Turing à créer les machines de Turing, modèle mathématiques à l’origine des ordinateurs modernes…

En particulier, il n’est pas possible d’écrire un assistant de programmation qui repère tous les problèmes qu’un code présente avant de l’avoir exécuté.

Il n’est pas non plus possible d’écrire un ramasse miette (garbage collector) qui soit parfait. Un ramasse miette cherche à libérer des zones de la mémoire après leur dernière utilisation dans un programme. Ces outils existent dans beaucoup de langages modernes (python, java, Golang etc.) mais ne sont jamais parfaits, en effet, l’existence d’un ramasse miette parfait est équivalente au problème de l’arrêt.

Vidéo #

Voici une vidéo de l’université de Rennes qui expose la preuve précédente.

Problème de l'arrêt en Python