David Madore's WebLog: Une autre énigme de calculabilité

L'énigme

Le cruel Docteur No (connu pour ses méfaits précédemment racontés ici, là, là, là et encore là — et j'en ai peut-être oublié au passage) est à la recherche d'inspiration pour une nouvelle torture pour mathématiciens. Ayant construit un Ordinateur Infini[#], il s'apprête à choisir une question, pour chaque entier n, dont la réponse est soit oui, soit non, de manière à ce qu'il soit impossible de calculer algorithmiquement la réponse en fonction de n : ces pauvres mathématiciens, qui ne disposent que de vulgaires ordinateurs (i.e., machines de Turing) seront donc incapables de répondre à la question, et le Docteur No jubile de l'impossibilité devant laquelle il va les placer.

Mais voilà que son code de l'honneur de grand méchant se rappelle à lui : ses énigmes doivent avoir une solution ! Il doit toujours y avoir un moyen de s'en sortir. Demander de calculer une fonction non-calculable n'est pas du jeu.

Le mathématicien capturé aura donc le droit de faire calculer par l'Ordinateur Infini une indication pour chaque question, sous forme d'un entier naturel h(n), qui lui sera donnée avec la question. Bon, mais comme ça ce serait vraiment trop facile. Donc en fait le Docteur No va mettre deux limitations sur cette indication : d'abord, il n'y aura une indication choisie par le mathématicien que quand la réponse à la question est oui ; quand la réponse est non, le mathématicien se verra donnée une fausse indication, choisie par le Docteur No (et évidemment, aucune façon de savoir si on a affaire à une vraie ou fausse indication). Ensuite, l'indication sera donnée non pas comme l'entier h(n) mais comme un programme q (ne prenant pas d'entrée, et choisi par Docteur No en même temps que n) qui calcule h(n) : en cas de fausse indication (i.e., si la réponse attendue est non), le programme pourrait ne jamais terminer du tout, ou pourrait terminer et renvoyer n'importe quoi (ou même ne pas être un programme du tout, mais ça ce n'est pas intéressant parce que c'est trop facile à tester) ; en revanche, en cas de vraie indication (i.e., si la réponse attendue est oui), le programme fourni terminera en temps fini et renverra h(n) (mais sans aucune autre garantie que ça). Avec ces données n (la question) et q (le programme calculant — peut-être — l'indication), le mathématicien doit (algorithmiquement !) calculer la réponse attendue, sachant que l'énigme doit faire que ce ne soit pas possible sans q.

Comment le Docteur No va-t-il choisir son énigme pour que le problème soit faisable, et comment le mathématicien capturé va-t-il choisir les indications ?

[#] Ce peut calculer l'Ordinateur Infini n'est pas très pertinent ici. Disons par exemple qu'il peut calculer n'importe quoi dont on peut démontrer l'existence. Mais si on veut par exemple imaginer que c'est une machine hyperarithmétique, on peut.

Comme mon scénario est assez tarabiscoté (franchement, si vous trouvez une meilleure façon de raconter l'histoire, dites-le moi !), voici une version mathématiquement précise de ce que je demande de prouver :

Montrer qu'il existe une fonction d:ℕ→{0,1} non calculable (ce sont les réponses attendues, avec ‘0’ pour non et ‘1’ pour oui) et une fonction h:ℕ→ℕ (nécessairement non calculable ; ce sont les indications ; la valeur de h(n) n'aura d'importance que si d(n)=1 donc on peut se limiter définir h sur d⁻¹({1})) telles qu'il existe un algorithme p qui, donné un n∈ℕ et un q comme on va le dire, termine toujours en temps fini et calcule d(n). La garantie sur q est que si d(n)=1 alors q est un programme sans entrée[#2] qui termine en temps fini et renvoie h(n) (en revanche, si d(n)=0 alors il n'y a aucune sorte de garantie sur q, c'est une donnée finie arbitraire).

[#2] Pour qu'il n'y ait pas de confusion possible : q ne prend pas n en entrée : il (q) est donné en même temps que n, et la garantie est que si d(n)=1 alors pour ce n-là, le programme q (qui ne prend pas d'entrée du tout) termine et renvoie h(n).

Je ne sais pas si j'ai vraiment d'indication à donner, cette fois-ci : je vois mal comment en donner une sans donner directement la solution : je sais juste qu'on peut partir dans la mauvaise direction et avoir l'impression que cette énigme est complètement insoluble, ou bien se dire qu'en fait c'est juste idiot. Sans que ce soit une indication (et je ne me prononce pas sur le fait que ça aide au problème général), on peut éventuellement commencer par réfléchir à la version plus simple où q est directement la valeur de h(n) dans le cas où d(n)=1, au lieu d'être un programme qui la calcule.

Une fois de plus, j'écrirai la réponse dans quelques jours en éditant ce billet. En attendant, à défaut de trouver la solution, vous pouvez aussi proposer une façon plus claire que moi de présenter l'énigme ! (Vous pouvez aussi vous plaindre si les termes de l'énigme ne sont pas clairs.)

La réponse

[Section ajoutée 2024-01-03T14:30+01:00.]

Voici la solution que je propose (j'ai peur qu'elle soit complètement incompréhensible si on n'a pas un minimum d'habitude de la calculabilité, mais j'ai quand même fait des efforts minimaux pour rappeler quelques conventions du domaine).

Je vais choisir un codage de Gödel sur les programmes, c'est-à-dire que je représenter les programmes par des entiers naturels, et je vais appeler n-ième programme ou abusivement juste n le programme représenté par l'entier n dans ce codage (par exemple, imaginez que les programmes sont des chaînes binaires et l'entier est la lecture de la chaîne binaire comme un entier). Si je parle des N premiers programmes, ça désignera ceux dont le code de Gödel est ≤N.

La question n ↦ d(n) posée par le Docteur No sera le problème de l'arrêt : i.e., d(n)=1 (réponse oui) si l'exécution du n-ième programme termine, et d(n)=0 (réponse non) si le programme ne termine jamais. C'est un résultat fondamental (et fondateur) de la calculabilité que cette question n'est pas algorithmiquement décidable. Mais toute la difficulté de l'énigme est de trouver maintenant des indications h(n) dans le cas d(n)=1 qui la rendent décidable (sachant qu'on reçoit une fausse indication dans le cas d(n)=0).

Commençons par considérer le problème « facile » où l'indication est donnée directement dans le cas où d(n)=1, au lieu d'être un programme qui la calcule indirectement.

Dans cette situation « facile », il suffit de prendre pour h(n) le temps d'exécution b(n) du programme considéré (je veux dire du n-ième programme, celui dont la question demande s'il termine), ou d'ailleurs un majorant quelconque de ce temps d'exécution (le temps d'exécution étant compté en nombre d'étapes d'exécution sur une machine de Turing, disons).

En effet, avec une telle indication, on peut décider si d(n)=1 en lançant l'exécution du programme pour au plus le nombre d'étapes qu'on a reçu en indice : si le programme s'arrête dans le temps imparti, alors on sait qu'il s'est arrêté, donc on peut répondre oui ; si au contraire l'exécution ne s'est pas arrêtée dans le temps imparti, on peut répondre non, et on ne risque pas de se tromper, car pour se tromper il faudrait que la vraie réponse fût oui, mais dans ce cas on aura reçu la bonne indication, donc le vrai temps d'exécution (ou en tout cas un vrai majorant), et donc on aura correctement exécuté le programme jusqu'à son arrêt et constaté celui-ci. (Les fausses indications ne sont fournies que si la vraie réponse est non, et elles auront pour seul effet de faire simuler inutilement longtemps l'exécution du programme n considéré, mais sans affecter le résultat final, qui est que ça ne s'arrête pas dans le temps imparti.) Bref, cette indication résout le problème.

Bon, mais dans l'énigme « difficile » que j'ai posée, on ne reçoit pas directement l'indication mais un programme q qui lui-même la calcule, et ce programme pourrait lui-même ne jamais terminer. Comment s'en sortir ?

Si on cherche à utiliser q comme programme, je pense qu'il n'y a pas moyen de s'en sortir[#3] (même si je ne sais pas bien formaliser ça). L'astuce (que je tiens de Ânkov, cf. ce post sur MathOverflow) consiste à utiliser q non pas comme un programme (i.e., on ne va pas l'exécuter) mais lui-même comme une borne, comme dans le cas « facile ». Plus précisément :

[#3] Je me suis beaucoup arraché les cheveux là-dessus, en cherchant moyen d'utiliser q comme un programme, chercher à l'utiliser en bornant son temps d'exécution, ou lancer q et n en parallèle, ou toutes sortes de choses comme ça : à chaque fois ça ne marchait pas.

Soit b(n) le temps d'exécution du n-ième programme (supposé terminer, parce qu'on ne donne une vraie indication que lorsque la réponse est oui), comme dans le problème « facile ». Soit maintenant h(n) un nombre qui soit strictement plus grand que les valeurs renvoyées par ceux qui terminent parmi les b(n) premiers programmes (exécutés sans entrée). Autrement dit, on pose h(n) = B(b(n)) où b(n) est la borne qu'on veut communiquer sur le temps d'exécution du n-ième programme, et B(N) est le maximum plus un parmi les valeurs bien définies renvoyées par les N premiers programmes, i.e., parmi ceux qui terminent et renvoient un entier (cette fonction B est une sorte de fonction castor affairé, comme l'est, d'ailleurs, la fonction b[#4]).

[#4] On peut s'arranger pour prendre deux fois la même fonction, mais je n'ai pas l'impression que ça rende la solution plus claire.

Si on reçoit un programme q (que je vais identifier à son code de Gödel), il suffit de lancer le n-ième programme tourner pendant q étapes (c'est-à-dire pendant un nombre d'étapes égal au code de Gödel de q), et répondre oui si elle a terminé pendant ce temps imparti. En effet, si la réponse correcte attendue est non, de toute façon on va conster que le programme ne termine pas quel que soit le nombre d'étapes sur lequel on simule son exécution, donc on répondra correctement. Si a réponse correcte attendue est oui, et si b(n) est comme ci-dessus, le programme q qu'on reçoit est censé calculer h(n) = B(b(n)) ; mais par définition de B, cela signifie que q > b(n) (puisque les N := b(n) premiers programmes renvoient une valeur <B(N) s'ils terminent, c'est que q n'en fait pas partie, donc q > b(n)). Donc, comme dans le cas « facile », si on simule l'exécution du programme n pendant q étapes, on va constater la terminaison du programme, et on aura répondu correctement.

Ajout/suite (2024-02-11) : cette entrée ultérieure (et spécifiquement ce passage) révèle le rapport que l'énigme posée dans le présent billet a avec la formule ((¬¬D⇒D) ⇒ (D∨¬D)) ⇒ (¬¬D∨¬D) et ce qu'elle nous apprend sur elle.