Lipsum.dev

Sur un résultat d'impossibilité en informatique

31 mai 2025 — Informatique théorique, Calculabilité

Considérons le problème algorithmique suivant :

On représente un nombre réel par un programme en Python qui énumère les chiffres de sa représentation décimale. C’est-à-dire qu’on encode un nombre réel $x$ par une fonction de signature f(n: int) -> int telle que :

f(0) est la partie entière de $x$
f(1) est la première décimale de $x$
f(2) est la seconde décimale de $x$
etc.

Exemple 1 : Si pi est une fonction représentant le nombre $\pi \approx 3.14$ alors on aura pi(0) = 3, pi(1) = 1, pi(2) = 4, etc.

Exemple 2 : Le programme suivant représente le nombre $42.42424242...$ :

def fortytwoforever(n: int) -> int:
   if n == 0:
       return 42
   elif n % 2:
       return 4
   else:
       return 2

Problème

Pouvez-vous écrire une fonction add qui prend en arguments deux programmes f et g, représentant des réels $x$ et $y$ , et renvoie un programme représentant la somme $x + y$ ?

Formulé en Python, à l’aide du typage, il s’agit de compléter la fonction suivante :

from typing import Callable
# Our "real numbers" are functions from int to int.
Real = Callable[[int], int]
# The problem is to implement this function.
def add(f: Real, g: Real) -> Real:
   pass

Quelques remarques :

J’ai choisi Python qui est un langage classique, mais tout ceci se transpose dans n’importe quel langage de programmation standard.
Cette façon de représenter les nombres réels n’est pas bijective puisqu’il existe différents programmes qui représenteront le même réel, et surtout il existe des nombres réels qui ne seront représentés par aucun programme. Ceci sera sans importance pour la suite.
Sauf mention contraire, le mot fonction désignera ici une fonction implémentable informatiquement (e.g. en Python) et non pas une fonction mathématique — la distinction est importante car il existe des fonctions (mathématiques) que l’on ne peut pas implémenter informatiquement, comme nous le verrons.

Solution

J’ai posé cet exact problème à deux agents conversationnels : voici la réponse de ChatGPT et voici celle du Chat de Mistral.

Dans les deux cas, il s’agit de réponses erronées.

À l’impossible nul n’est tenu.

Vous l’aurez certainement deviné en lisant le titre de cet article, il est en fait impossible d’écrire un programme add qui fasse ce qui est demandé ici. Le fait que des IA qui ont pourtant ingurgité des livres d’informatique théorique entiers n’aient pas détecté ceci nous montre de sérieuses limitations dans leurs capacités de raisonnement…

La première partie de cet article sera dédiée à la démonstration de ce résultat d’impossibilité, qui ne requiert pas de connaissances particulièrement avancées.

Puis, dans une seconde partie, nous nous intéresserons à une extension de ce problème dans laquelle on autorise la fonction d’addition à accéder aux codes sources des programmes f et g (au lieu de simplement pouvoir les exécuter).

Cette seconde partie (indépendante de la première), nous amènera à visiter différents résultats plus ou moins avancés de calculabilité, un domaine de l’informatique théorique qui s’intéresse à ce que les ordinateurs peuvent faire — sans considération de temps de calcul ou de ressources mémoires nécessaires.

Pourquoi c’est impossible ?

La réponse courte est la suivante : il est impossible d’implémenter un algorithme d’addition, car cet algorithme devrait décider en un nombre fini d’étapes de la valeur du premier chiffre de l’addition, alors que celui-ci peut dépendre d’un nombre infini de chiffres des nombres additionnés.

Je vous propose ici de détailler cette explication via un raisonnement par l’absurde, en supposant que l’on dispose d’un programme add(f: Real, g: Real) -> Real.

Considérons des fonctions f: Real et g: Real, représentant respectivement les nombres $\frac{1}{3} = 0.333…$ et $\frac{2}{3} = 0.666…$ (elles sont toutes deux implémentables facilement).

Que vaut add(f, g)(0) ?

C’est la partie entière de $\frac{1}{3} + \frac{2}{3} = 1$ donc on s’attend à avoir add(f, g)(0) == 1 (*).

Le calcul de add(f, g)(0) termine en temps fini et ne peut donc inspecter qu’un nombre fini des chiffres renvoyés par $f$ : il existe un majorant $n_{max}$ aux arguments $n$ tels que $f(n)$ est appelé au cours de cette exécution.

On pourrait implémenter une fonction f_modified correspondant au nombre $0.\underbrace{33…3}_{n_{max}\text{ fois}}22…$ dont les $n_{max}$ premières décimales sont identiques à celles de $f$ mais dont les suivantes sont des $2$ au lieu de $3$ .

On s’attendrait alors à ce que add(f_modified, g) corresponde au nombre $0.\underbrace{99…9}_{n_{max}\text{ fois}}88…$

Pourtant, on aura nécessairement add(f_modified, g)(0) == 1 puisque l’algorithme d’addition va voir exactement les mêmes valeurs que lors du calcul de add(f, g)(0) : les chiffres qui diffèrent ne sont pas lus.

Le résultat de l’addition des réels représentés par f_modified et g sera donc forcément erroné.

(*) En fait, on peut aussi avoir add(f, g)(0) == 0 d’après le développement impropre $1 = 0.999…$

On peut dans ce cas adapter le raisonnement ci-dessus en définissant un programme f_modified représentant un nombre de la forme $0.33…344…$ , ce qui conduit à un autre calcul erroné.

Cqfd.

Ce qui suit introduit une extension du problème initial, qui nécessite pour son traitement des résultats d’informatique théorique plus sophistiqués. C’est une invitation, facultative, à explorer différents résultats de calculabilité qui se manifestent de façon intéressante dans ce problème de représentation des réels.

💡 Sur une variante du problème

Pourrait-on réussir à additionner deux nombres réels, toujours représentés par des fonctions f: Real et g: Real, en donnant maintenant à la fonction add(f: str, g: str) -> Real l’accès aux codes sources de f et g (au lieu simplement de pouvoir interroger f et g) ?

Cette variante du problème initiale est plus permissive, puisqu’elle élargit la classe des fonctions candidates : une fonction qui a accès aux codes sources peut simuler l’exécution de f et g, mais pouvoir exécuter f et g ne donne pas accès à leurs codes sources.

Il se trouve que, là encore, la réponse est négative. Pour le montrer, nous aurons cette fois besoin de considérations d’informatique théorique plus poussées, que je vais développer dans l’interlude théorique ci-dessous.

∗ ∗ ∗

Le problème de l’arrêt

Il est bien connu des développeurs que, dans un langage comme Python, on peut construire des programmes qui ne terminent pas.

Une question très classique de l’informatique théorique est celle du problème de l’arrêt, qu’on peut présenter ainsi :

Peut-on implémenter une fonction halt(source: str) -> bool prenant en entrée le code source: str d’une fonction (sans argument) et renvoyant un booléen indiquant si le programme correspondant s’arrête en temps fini ?

La réponse est non et il existe différentes façons de le montrer. Par exemple, raisonnons par l’absurde en supposant que l’on dispose d’une telle fonction halt(source: str) -> bool.

On peut alors écrire un programme p (comme paradoxe) comme suit :

def p():
    s = """def p():
    s = {!r}
    if halt(s.format(s)):
        while True:
            pass
    else:
        return"""
    if halt(s.format(s)):
        while True:
            pass
    else:
        return

Tel que construit ci-dessus, le programme p invoque la fonction halt sur son propre code source (auquel on lui a donné accès de façon astucieuse !) de façon à faire le contraire de ce que halt indique qu’il fait : si halt dit que p termine en temps fini, alors p part dans une boucle infinie, et vice-versa.

L’hypothèse de départ est donc erronée : il ne peut pas exister de telle fonction halt(source: str) -> bool résolvant le problème de l’arrêt.

Le « problème de séparation »

Le problème de séparation (dénomination propre à cet article) est le suivant :

Peut-on implémenter une fonction sep(source: str) -> bool qui reçoit le code source: str d’une fonction sans argument et se comporte de la façon suivante :

Si le programme (décrit par source) termine en temps fini et retourne 0, sep(source) retourne True.
Si le programme termine en temps fini et retourne une autre valeur que 0, sep(source) renvoie False.
Sinon (le programme décrit par source ne termine pas), sep(source) renvoie True ou False arbitrairement mais de façon déterministe : la même source donne toujours le même retour.

Je vous laisse vous convaincre que le problème de séparation est insoluble, à l’aide de la fonction paradoxale suivante :

def p():
    s = """def p():
    s = {!r}
    if sep(s.format(s)):
        return 1
    else:
        return 0"""
    if sep(s.format(s)):
        return 1
    else:
        return 0

Il s’agit d’un raisonnement par l’absurde très similaire à la preuve du théorème de l’arrêt qui précède, et je reviendrai sur cette similarité et la structure de ces preuves un peu plus loin.

∗ ∗ ∗

Revenons à notre problème de savoir si on peut implémenter la fonction add(f: str, g: str) -> Real prenant en arguments les codes sources.

Nous allons d’abord montrer une première impossibilité (◇) : il est impossible d’implémenter une telle fonction d’addition qui ne donne jamais de développement impropre.

Pour prouver ce résultat, on peut montrer que si un telle fonction d’addition existait, on pourrait l’utiliser pour résoudre le problème de l’arrêt. On encode à cette fin le problème de l’arrêt dans la représentation d’un réel, de la façon suivante :

Soit une fonction h(source: str) -> Real qui prend en entrée la source d’une fonction (sans argument) et renvoie une fonction h(source) qui fait ceci :

h(source)(0) renvoie toujours 0.
Pour n > 0, h(source)(n) exécute le programme représenté par source pendant n étapes élémentaires et se comporte ainsi :
- Si au cours de ces n étapes, le programme termine, h(source)(n) renvoie 0.
- Sinon (l’exécution n’est pas terminée après n étapes), h(source)(n) renvoie 3.

Remarque : Ce qu’on appelle « étape élémentaire » dépendra des détails du langage utilisé. Il pourrait par exemple s’agir d’une instruction machine.

Ainsi définie, si source correspond à un programme qui s’arrête, h(source) représentera un réel de la forme $0.33…300…$

Au contraire, si source correspond à un programme qui ne termine jamais, h(source) représentera le réel $\frac{1}{3} = 0.333…$

On notera toujours g: Real une fonction représentant $\frac{2}{3} = 0.666…$

Je vous laisse vous convaincre que, sous l’hypothèse que add ne renvoie jamais de développement impropre, la fonction lambda source: add(h(source), g)(0) == 0 qui renvoie le premier chiffre du développement décimal de la somme des réels représentés par h(source) et g résout le problème de l’arrêt, ce qui est impossible.

Cqfd (◇).

On peut cependant démontrer une deuxième impossibilité (♤), plus forte : il est impossible d’implémenter une telle fonction d’addition, même en l’autorisant à renvoyer arbitrairement (mais de façon déterministe) des développements impropres.

Pour démontrer cette seconde version, on va encoder le « problème de séparation » dans un programme k(source: str) -> Real ainsi défini :

k(source)(0) renvoie toujours 0.
Pour n > 0, k(source)(n) exécute le programme représenté par source pendant n étapes élémentaires et se comporte ainsi :
- Si au cours de ces n étapes, le programme termine
  - Si la valeur de retour est 0, k(source)(n) renvoie 2.
  - Si la valeur de retour est différente de 0, k(source)(n) renvoie 4.
- Sinon, k(source)(n) renvoie 3.

Ainsi, selon les cas, k(source) pourra représenter un réel de la forme 0.333… (programme qui ne termine pas), 0.33…322… (programme qui termine et retourne 0) ou 0.33…344… (programme qui termine et retourne une valeur différente de 0).

Je vous laisse vous convaincre que lambda source: add(k(source), g)(0) == 0 résout le problème de séparation, ce qui est impossible.

Cqfd (♤).

∗ ∗ ∗

Avant de conclure, je souhaiterais ajouter deux petites remarques techniques.

La première, c’est que pour démontrer les résultats d’impossibilité du problème de l’arrêt et du problème de séparation, j’ai utilisé le schéma de preuve suivant :

Supposer qu’un programme (e.g. halt, sep) qui résout le problème existe.
Construire une fonction paradoxale p qui a accès à son propre code source et appelle la fonction précédente avec celui-ci.
Utiliser dans p le résultat de cet appel pour faire précisément le contraire de ce qu’il indique (paradoxe).

L’astuce qui permet en 2. à un programme d’accéder à son propre code source peut se formaliser théoriquement à travers le théorème de récursion de Kleene.

Je ne rentrerai pas dans les détails, qui nécessitent un formalisme plus abstrait que les fonctions Python utilisées ici. Il me semble néanmoins important de le souligner, car on peut obtenir le résultat d’impossibilité (♤) directement à l’aide du théorème de récursion.

C’est le sujet de cette réponse de J.D. Hamkins qui donne également des indications historiques sur la représentation des réels calculables utilisée ici et les alternatives qui permettent de calculer l’addition.

La seconde remarque, c’est que je n’ai pas montré que le problème de l’arrêt ne pouvait être résolu à partir du problème de séparation.

En fait, cette question est assez subtile : on veut comparer entre eux deux problèmes pour lesquels on sait qu’il n’existe pas de solution algorithmique.

On peut montrer (ce n’est pas bien difficile) qu’une fonction halt — qui n’existe pas en tant que programme, mais qu’on peut définir en tant que fonction mathématique, on parle alors d’oracle — qui résout le problème de l’arrêt, permet aussi de résoudre le problème de séparation.

En revanche, la réciproque est bien plus subtile : il existe des oracles pour le problème de séparation qui permettent de résoudre le problème de l’arrêt, mais il en existe aussi qui ne le permettent pas — rappelons que les oracles pour le problème de séparation peuvent différer dans ce qu’ils renvoient pour un programme qui ne termine pas.

Un point clef dans la démonstration de ce dernier résultat est le théorème de la base basse, qui permet d’affirmer l’existence d’un ensemble auquel correspond un oracle qui résout la séparation mais ne permet pas de résoudre l’arrêt. Il s’agit là d’un résultat mathématique (cet ensemble est par nature non calculable) assez technique.

Pour une présentation très approfondie de la calculabilité et en particulier des théorèmes mentionnés ici, vous pouvez lire le livre de Monin et Patey, qui est une référence en français.

Pour d’autres ressources, vous pouvez également parcourir ce fil de discussion qui recouvre en grande partie les explications détaillées ici.

Maths et applications, avec les mains et avec du code 💻
Suivre sur Twitter

← Satisfaisabilité, frustration et transitions de phase