David Madore's WebLog: Une tentative pour vulgariser les bases de la calculabilité

(Plan :)

• Qu'est-ce qu'un algorithme ?
• La calculabilité n'est pas l'étude des ordinateurs
• Entrées, sorties, programme et extension
• Sans préoccupations de ressources !
• La « thèse » de Church-Turing
• « Données finies » et codage de Gödel
• Programmes qui ne terminent jamais
• Les programmes sont eux-mêmes des données finies
• Un programme « universel »
• Exécution en temps limité
• L'astuce de Quine pour l'auto-référence
• Récursivité et non terminaison
• L'indécidabilité du problème de l'arrêt

☞ Qu'est-ce qu'un algorithme ?

Bref, de quoi s'agit-il ?

La théorie de la calculabilité, c'est l'étude mathématique de ce que peut, en théorie, faire un ordinateur ou un programme informatique, ou plus exactement, de ce que peut faire un algorithme en l'absence de toute considération d'efficacité.

Avant toute chose, il faut donc que j'explique un peu ce qu'est un algorithme.

Si je dois tenter une définition d'algorithme ce sera quelque chose comme ceci : un plan précis d'exécution d'étapes simples et mécaniques de calcul ou de traitement de données, pouvant être réalisé sans aucune réflexion pour aboutir à un résultat bien défini, et qui est donc, en particulier, réalisable par un ordinateur (ou, en principe, par un humain suffisamment patient).

Première difficulté de la vulgarisation, ici, que mon ami David Monniaux a souvent montrée du doigt : à cause de la manière dont beaucoup de journalistes ont utilisé le mot, de manière volontiers péjorative, comme une boîte noire dont on ne comprend pas pas le fonctionnement, et/ou dont le résultat n'est pas bien spécifié, le grand public a en tête une notion de ce qu'est un algorithme possiblement très différente de son sens technique. La définition que je propose de plan précis d'exécution d'étapes simples et mécaniques de calcul ou de traitement de données, pouvant être réalisé sans aucune réflexion pour aboutir à un résultat bien défini, et qui est donc, en particulier, réalisable par un ordinateur (ou, en principe, par un humain suffisamment patient) est peut-être trop longue pour être vraiment parlante (cf. ce fil Bluesky pour une discussion).

D'autres gens proposent de dire des choses plus courtes pour définir algorithme, par exemple une recette de cuisine ou ensemble d'étapes permettant de réaliser une action : c'est peut-être plus clair mais néanmoins exagérément vague pour essayer d'en parler ensuite de façon précise. (Le problème avec recette de cuisine ou plan pour réaliser une action c'est que ① ça ne limite pas le domaine au traitement de l'information, or je ne dirais pas que, disons, un plan pour faire un coup d'état est un algorithme, et ② une recette de cuisine, normalement, n'implique pas de boucles — même si ça peut impliquer d'attendre que quelque chose se produise —, encore moins de récursion[#2].) Donc c'est un peu réducteur. Un algorithme au sens utilisé ici est constitué d'étapes extrêmement simples et très précisément définies, mais au final on peut être amené à faire des choses immensément compliquées avec, parce qu'on peut les combiner de façon très complexe.

[#2] On ne va jamais être amené à se demander est-ce que cette recette de cuisine termine ? alors que c'est, justement, une des questions cruciales qu'on peut être amené à se poser (et à ne pas savoir répondre) pour un algorithme.

☞ La calculabilité n'est pas l'étude des ordinateurs

Néanmoins, il me semble important de souligner qu'un algorithme n'est pas forcément quelque chose qui va être exécuté par un ordinateur. Il s'agit juste d'exécuter mécaniquement des étapes très simples, sans jamais se tromper, en suivant les instructions fournies (celles qui constituent l'algorithme). En principe, donc, n'importe quel algorithme peut être suivi par un humain comme il peut l'être par un ordinateur (et tout ce que peut faire un ordinateur peut aussi être fait par un humain) : il s'agira « juste » de disposer d'une patience infinie, d'un temps illimité, et d'une quantité illimitée de papier, et d'une capacité incroyable à ne jamais se tromper, chose pour laquelle les ordinateurs sont extrêmement bons et les humains extrêmement mauvais, mais je veux vraiment souligner que les ordinateurs ne peuvent rien faire qui ne soit pas, en principe, aussi faisable par un humain dans ces conditions (patience infinie, etc.).

Ce que je dis là n'est pas purement théorique : il y a vraiment des algorithmes utilisables par des humains, et d'ailleurs utilisés par des humains[#3]. J'espère qu'on apprend encore à l'école à poser une multiplication : c'est bien un algorithme qui est enseigné, et on devrait être convaincu qu'il permet, en principe, à un humain assez motivé, sans calculatrice, de savoir combien vaut 96 889 010 407 × 94 143 178 827, même si ça va être long et fastidieux (et si on pose la question à l'ordinateur, il va utiliser un algorithme qui n'est pas substantiellement différent, au moins pour des nombres de cette taille, de celui qu'on a appris à l'école).

[#3] Ou du moins, qui l'ont été : le nombre de situations où des humains calculent des multiplications de grands nombres à la main doit maintenant être minuscule ; mais historiquement, il y avait des gens dont c'était le métier. Par exemple, quand Urbain Le Verrier (connu pour sa découverte de la planète Neptune) prend la tête de l'Observatoire de Paris en 1853, puis l'amiral Mouchez en 1887, les tâches ingrates de calcul numérique sont déléguées à des « calculatrices » (ce sont essentiellement des femmes, mal rémunérées et très peu considérées). Toutes les tables de logarithmes publiées avant le 20e siècle ont aussi, bien sûr, été calculées par des humains appliquant des algorithmes longs et fastidieux (qui prennent maintenant une fraction de seconde à un ordinateur). Dans la nouvelle The Feeling of Power (1957) (disponible en ligne ici), Asimov imagine un monde dans lequel plus personne ne sait faire de calculs autrement que sur un ordinateur, et quelqu'un redécouvre qu'on peut les faire à la main.

La calculabilité n'a donc pas vraiment à voir avec les ordinateurs, ou comme le dit un adage (attribué sans doute à tort à E. W. Dijkstra), l'informatique n'est pas plus l'étude des ordinateurs que l'astronomie n'est l'étude des télescopes.

☞ Entrées, sorties, programme et extension

Un algorithme, donc, prend quelque chose en entrée (on peut aussi parler des arguments passés à l'algorithme), par exemple deux nombres à multiplier, et renvoie un certain résultat en sortie, par exemple le résultat de la multiplication. (Les entrées et les sorties seront toutes des « données finies », terme sur lequel je vais revenir ci-dessous.) Ce qu'on a fait, c'est calculer une certaine fonction au sens mathématique.

La différence entre la fonction mathématique et l'algorithme qui la calcule, c'est qu'il peut y avoir toutes sortes de façons de calculer la même fonction (par exemple, différentes façons de poser une multiplication, qui aboutissent au même résultat) : la fonction, c'est l'opération abstraite qui associe un résultat à des arguments, alors que l'algorithme, c'est le plan d'exécution par lequel on est arrivé à ce résultat. Il y a des fonctions mathématiques qui sont plus ou moins difficiles à calculer par un algorithme, et certaines qui sont même impossibles à calculer algorithmiquement (elles sont non-calculables), mais qui n'en ont pas moins un sens mathématique.

On peut aussi utiliser les termes d'extension et d'intention (ou intension ? cf. ce billet au sujet de ce mot) : l'extension, c'est la fonction mathématique qu'on calcule, tandis que l'intenſion (quelle que soit la manière dont on l'écrit), c'est l'algorithme, c'est-à-dire la manière dont on calcule cette fonction.

Autre difficulté : est-ce qu'algorithme est synonyme de programme ? En calculabilité, les deux mots sont utilisés de façon essentiellement interchangeables. Mais il y a au moins des différences d'usage, au moins dans le contexte de l'informatique plus large[#4]. Le terme d'algorithme est plus abstrait et fait souvent référence au plan de fonctionnement débarrassé de ses détails relatifs à l'usage, par exemple, d'un langage de programmation particulier (on parle d'implémentation pour l'écriture concrète d'un algorithme dans un système informatique particulier), mais la limite entre l'algorithme et son implémentation est un peu floue. On parle plus volontiers d'algorithme, par exemple, quand on ne s'intéresse qu'à la partie proprement calculatoire ; alors qu'un programme peut faire intervenir une interface utilisateur, des lectures et écritures sur écran, clavier ou disque, ce genre de choses. En outre, on peut considérer (ou pas…) qu'un algorithme doit répondre à un problème bien posé[#5] alors qu'un programme est simplement une suite d'instruction données à un ordinateur. (Et évidemment, programme sous-entend un contexte informatique alors qu'un algorithme est, comme je le souligne ci-dessus, théoriquement applicable par un humain.) Convenons, néanmoins, d'ignorer ces subtilités et que, dans ce qui suit, puisque je veux parler de calculabilité, et même si ce n'est pas vraiment l'usage habituel, programme signifie la même chose qu'algorithme, et que j'utiliserai ci-dessous ces termes de façon essentiellement interchangeable[#6].

[#4] J'aurais du mal à dire, par exemple, qu'un navigateur comme Firefox est un algorithme. C'est un programme. Ce programme utilise toutes sortes d'algorithmes à différents endroits (par exemple, pour organiser les marque-page il y a certainement des algorithmes de tri), mais il n'est pas un algorithme dans l'usage normal du mot (ne serait-ce que parce qu'il n'arrête pas d'avoir des nouvelles versions, alors qu'un algorithme est quelque chose de plus abstrait). A contrario, la manière dont on fait une multiplication à l'école primaire est un algorithme, je ne qualifierais pas ça de programme (ne serait-ce que parce qu'il n'y a pas d'ordinateur en vue).

[#5] Ce que je veux dire, c'est que, selon cette distinction terminologique (avec laquelle je ne suis pas forcément d'accord), un algorithme doit avoir une spécification : il prend en entrée certaines données et produit un certain résultat qui doit répondre à un certain problème mathématiquement bien défini (la spécification de l'algorithme) ; et on est censé prouver mathématiquement que l'algorithme correspond bien à sa spécification. Dans ce sens, ChatGPT n'est pas un algorithme (même s'il y a des algorithmes utilisés pour, par exemple, calculer ses paramètres à partir d'un corpus d'entraînement, ou pour produire la sortie à partir de ses poids), parce qu'on ne peut pas dire qu'il réponde à une quelconque spécification. En quelque sorte, cette distinction terminologique cherche à refléter la distinction entre les méthodes formelles/rigoureuses et heuristiques en informatique, en réservant le terme d'algorithme pour les premières.

[#6] Dans la mesure où je fais une différence (et elle ne sera pas forcément systématique), c'est que quand un programme prend en entrée un autre programme (situation qui va jouer un rôle important dans la suite), j'ai du mal à appeler le deuxième un algorithme (en effet, il doit être écrit dans un cadre bien précis, avec des instructions bien précises, et il ne vient pas avec une sorte de spécification ou de mode d'emploi, et justement on va voir que c'est difficile de l'analyser, donc toutes ces raisons suggèrent que le terme de programme est plus approprié).

Encore une autre difficulté est de savoir si un algorithme a le droit de faire appel au hasard. En calculabilité, la réponse est implicitement non (le hasard n'est pas calculable, il s'oppose même au calculable[#7] en un sens bien précis), mais dans d'autres branches de l'informatique, la notion d'algorithme faisant intervenir le hasard (algorithme « randomisé ») est légitime.

[#7] Ce qui ne veut pas dire qu'il n'y ait pas toutes sortes de questions fascinantes de calculabilité à se poser sur ce qu'on peut faire si on dispose d'une source de hasard (peut-on faire avec le hasard des choses qu'on ne peut pas faire sans hasard ? essentiellement non, mais ça dépend de l'interprétation précise de la question que je viens de dire de façon trop vague ; pour une référence précise, voir le fact ① sous cette question).

Bref, le domaine de la calculabilité a pour but d'étudier ce que, de façon théorique, un algorithme peut ou ne peut pas faire, et donc, pour commencer, de proposer une définition mathématiquement acceptable de ce qu'un algorithme signifie.

☞ Sans préoccupations de ressources !

Mais une autre précision importante est que la calculabilité ne s'intéresse pas aux « ressources » consommées par l'algorithme lors de son exécution, c'est-à-dire : le temps qu'il met, la mémoire qu'il utilise, ou toute autre ressource (l'énergie consommée sur un ordinateur réel). On suppose qu'il dispose de ressources (temps, mémoire, etc.) « finies à chaque instant, mais illimitées a priori », et c'est ce qui rend le sujet assez théorique. (Certains des algorithmes considérés par la calculabilité sont tout à fait inapplicables sur un ordinateur réel, en ce qu'ils prendraient bien plus que la durée de vie de l'Univers à s'exécuter sur une entrée modeste : pour autant, on dira bien que le résultat est calculable en fonction de l'entrée.) En cela, la calculabilité s'oppose à d'autres domaines de l'informatique, tels que :

• l'algorithmique, qui est l'art d'écrire des algorithmes (de préférence, efficaces) pour résoudre des problèmes bien posés,
• la complexité, qui est l'étude mathématique des ressources (principalement : temps, mémoire) consommées par un algorithme lors de son exécution, et de ce que peut faire un algorithme disposant de telles ressources limitées.

La complexité est une discipline beaucoup plus soigneuse que la calculabilité : elle ne cherche pas juste à savoir si des choses sont « en principe possible, avec assez de temps et de mémoire », mais combien ça va effectivement[#8] coûter en temps et en mémoire. La calculabilité se moque de ces questions d'efficacité, elle ne cherche à faire dans la dentelle[#9], donc c'est une discipline assez théorique.

[#8] Bon, effectivement avec des pincettes, quand même, parce que c'est généralement une complexité asymptotique, c'est-à-dire « à l'infini », donc ça reste assez théorique.

[#9] Par exemple, sur la question de savoir décider si un nombre n est premier, la calculabilité peut très bien dire oui, c'est une question décidable [=calculable], parce qu'on peut tester tous les produits i×j pour 2≤i≤n et 2≤j≤n, et voir si l'un d'entre eux est égal à n : c'est une façon ridiculement inefficace de savoir si un nombre est premier, mais pour la calculabilité, c'est un algorithme qui marche, c'est tout ce qui compte.

Par exemple, on pourra dire en calculabilité que les décimales du nombre π sont calculables (il existe un programme qui, quand on lui donne n, renvoie les n premières décimales — ou juste la n-ième, pour la calculabilité ça ne change rien), mais évidemment, si vous voulez les calculer vraiment, il vaut mieux regarder un peu plus finement quel algorithme utiliser pour que ce soit efficace. (Et, dans le monde réel, il est peu vraisemblable qu'on arrive jamais à calculer la 10^1000000-ième décimale de π, alors que pour ce qui est de la calculabilité, il n'y a pas de problème particulier.)

À cause de ces ressources illimitées données aux algorithmes, les résultats positifs de la calculabilité (telle ou telle chose est calculable) sont plus faibles que ceux de la complexité (telle ou telle chose est calculable en temps ceci-cela ou en mémoire ceci-cela) ; mais symétriquement, les résultats négatifs de la calculabilité sont d'autant plus forts : quand on montre que quelque chose n'est pas calculable au sens de la calculabilité, c'est que ce n'est pas possible d'y arriver (de manière systématique), même si on n'a aucune contrainte sur le temps ou la mémoire. Et c'est sans doute pour cette raison qu'on s'intéresse beaucoup, en calculabilité, aux résultats négatifs (je vais notamment démontrer, ci-dessous, l'indécidabilité du problème de l'arrêt, qui est l'exemple fondamental dans ce sens).

☞ La « thèse » de Church-Turing

Mais la première chose avant d'étudier les algorithmes, c'est d'essayer de définir précisément ce qu'est un algorithme, pour pouvoir espérer raisonner[#10] mathématiquement dessus.

[#10] L'algorithmique n'a pas vraiment besoin de définir exactement ce qu'est un algorithme, puisqu'elle cherche juste à en construire : on peut se contenter de savoir, en pratique, reconnaître qu'on a bien construit des algorithmes. Mais pour espérer prouver des résultats négatifs du type aucun algorithme ne peut faire ceci-cela, il faut forcément une définition mathématiquement robuste.

Une des constatations importantes de la théorie de la calculabilité est la thèse de Church-Turing, qui affirme, grosso modo, que toute approche raisonnable pour définir la notion calculabilité algorithmique (déterministe, finitiste) aboutit à la même notion. Expliquons un peu ce que ça veut dire.

D'abord, on dispose de (au moins !) trois grandes approches mathématiquement précises (i.e., formelles, sur lesquelles on peut vraiment appuyer un raisonnement rigoureux) : elles s'appellent

• les fonctions générales récursives (à la Herbrand-Gödel-Kleene),
• le λ-calcul de Church,
• les machines de Turing.

Peu importe ce que ce sont exactement : ce qui importe est ce que ce sont des concepts mathématiquement précis et rigoureux. Mais très grossièrement, les fonctions générales récursives sont une approche très mathématique de la notion de fonction calculable, qui ne cherche pas vraiment à définir la notion d'algorithme mais juste les fonctions que ces algorithmes peuvent calculer. Le λ-calcul est un système symbolique qui s'approche assez de ce qu'on appelle en informatique un langage de programmation « fonctionnel ». Et les machines de Turing[#11] sont une définition opérationnelle d'un algorithme qui peut s'exécuter sur une machine très simple qui s'approche du fonctionnement d'un ordinateur réel, mais très simplifié.

[#11] Des trois approches que j'ai énumérées, les machines de Turing sont la plus simple à décrire. Une machine de Turing est constituée de quatre choses : ① un ruban (ou bande) infinie, divisée en cellules, chacune pouvant contenir le symbole ‘0’ ou le symbole ‘1’, mais seul un nombre fini de cellules contenant le symbole ‘1’ à un instant donné, ② une tête de lecture-écriture qui est située au-dessus d'une des cellules du ruban, et qui possède la possibilité de se déplacer dessus, mais seulement d'une case à la fois, ③ un état interne, qui ne peut prendre qu'un nombre fini N de valeurs différentes (on numérote typiquement ces états par les entiers 1, 2, 3, etc., jusqu'au maximum N de la machine, plus l'état spécial 0 qui signifie arrêter l'exécution du programme), et ④ un programme, qui est juste un grand tableau qui, pour chacune des 2N combinaisons de l'état actuel et du symbole (0 ou 1) lu par la tête, donne trois informations, à savoir le nouvel état dans lequel passer (de 0 à N), le nouveau symbole à écrire à la place de celui qu'on a lu, et la direction dans laquelle déplacer la tête (gauche ou droite, sachant que le déplacement aura lieu d'une seule case à la fois). La machine commence dans l'état 1 (par convention), avec une bande qui contient ce qu'on veut lui donner comme entrée (ou complètement vierge si on ne veut rien lui donner), et à chaque étape de son exécution, en fonction du symbole situé sous la tête de lecture et de l'état actuel, le programme lui dit dans quel nouvel état passer, quel nouveau symbole écrire à la place de la tête, et dans quelle direction déplacer la tête, et ceci se répète jusqu'à ce que la machine passe dans l'état spécial 0 (si ça arrive), auquel cas la bande contient la sortie de la machine. Bref, il s'agit d'un automate extrêmement simple (et justement choisi pour être le plus bête possible), mais dont on peut se convaincre qu'il permet de réaliser, en principe, n'importe quelle sorte d'algorithme. On peut facilement réaliser une machine de Turing dans toutes sortes de cadres, par exemple, il y a des gens qui en ont fait en Lego.

On peut prouver rigoureusement que ces trois approches théoriques sont équivalentes, c'est-à-dire qu'elles aboutissent exactement à la même notion de calculabilité, qu'on appelle la calculabilité au sens de Church-Turing[#12]. Déjà, le fait d'être arrivé à la même notion de trois façons indépendantes suggère que cette notion est mathématiquement intéressante et robuste.

[#12] Non seulement elles sont équivalentes, mais cette équivalence est elle-même algorithmique (ou « constructive »), c'est-à-dire qu'il existe des algorithmes qui convertissent de l'une quelconque en une autre quelconque de ces représentations. Autrement dit, on peut écrire des algorithmes qui prennent en entrée le numéro d'une fonction générale récursive, ou un terme du λ-calcul, ou un programme de machine de Turing, et qui renvoient en sortie l'une de ces trois choses, qui fait « la même chose » (i.e., le même calcul) que ce qu'on a passé en entrée.

Ensuite, on constate que cette notion reflète la possibilité théorique de calcul dans à peu près n'importe que langage de programmation généraliste usuel (Python, Java, JavaScript, ce que vous voudrez) « convenablement idéalisé ». Il y a des notes en bas de page sur ce que signifie convenablement idéalisé (pas d'entrées-sorties, pas de source de hasard ou de non-déterminisme, aucune limite sur la taille des objets), mais en gros, ce que vous pouvez calculer, en principe, avec votre langage de programmation préféré en temps et mémoire illimités est aussi exactement ce que peut calculer n'importe lequel des trois modèles théoriques que j'ai évoqués ci-dessus, i.e., tous les langages de programmation usuels correspondent aussi à cette calculabilité de Church-Turing quand on les idéalise.

En outre, on est philosophiquement convaincu, même si c'est difficile à rendre cette affirmation suffisamment précise pour qu'elle puisse faire l'objet d'une démonstration mathématique, que la calculabilité de Church-Turing rend aussi compte de ce qu'on peut faire avec la notion d'« algorithme » décrit informellement comme un plan précis d'exécution d'étapes simples et mécaniques de calcul ou de traitement de données, pouvant être réalisé sans aucune réflexion pour aboutir à un résultat bien défini. Et enfin, on pense généralement (même si ce point est susceptible de débat[#13]) qu'elle reflète aussi ce qu'il est possible en principe de calculer dans notre univers physique par n'importe quel moyen physique (mécanique, électronique, etc.) si on dispose d'un temps et d'une énergie illimités (mais finis).

[#13] Le débat est compliqué parce qu'il faut définir exactement ce que les termes veulent dire. Voir les réponses sous cette question sur MathOverflow pour une discussion technique sur les différentes approches pour essayer de prouver, ou de réfuter, l'idée que les lois de la physique permettent exactement de calculer ce qui est calculable au sens de Church-Turing. Divulgâchis, cependant : si on arrivait à faire un vrai ordinateur physique qui dépasse la puissance d'une machine de Turing (autrement que par la possibilité de générer des nombres aléatoires), ça se saurait.

Bref, la thèse de Church-Turing, c'est un ensemble d'affirmations qui prétendent que toutes ces approches de la calculabilité (mathématique, théorique, pragmatique, philosophique, physique) conduisent à la même notion. Certaines de ces affirmations sont des théorèmes mathématiques précis (comme l'équivalence entre fonctions générales récursives, λ-calcul et machines de Turing), d'autres sont un peu plus informelles, mais dans l'ensemble, le fait qu'on aboutisse à la même notion par tellement d'approches laisse fortement penser qu'on a trouvé « la bonne » notion de calculabilité, ou du moins une notion particulièrement importante et méritant d'être étudiée avec soin.

Donc désormais, et de façon générale quand on ne précise pas une autre convention, quand on dit que quelque chose est calculable, cela signifie que cette chose est calculable au sens de Church-Turing (donc, par exemple, par une machine de Turing, ou par votre langage de programmation préféré et convenablement idéalisé).

Et l'étude de la calculabilité, c'est l'étude, pour commencer, de la calculabilité de Church-Turing (même si les mathématiciens, étant joueurs, vont forcément s'interroger ensuite sur la manière de l'étendre ou de la modifier de différentes façons[#14]).

[#14] Par exemple en permettant à un programme de « consulter un oracle » qui lui donne magiquement le résultat de certains calculs qu'il ne pourrait pas faire (voir ce billet pour de la vulgarisation à ce sujet, et celui-ci pour quelque chose de plus précis), ou bien en lui permettant de faire une infinité de calculs en un temps fini (voir ici pour une notion de ce genre), ou encore en pouvant manipuler des quantités infinies (voir là à ce sujet), ce genre de choses.

☞ « Données finies » et codage de Gödel

Il y a quand même un point ou deux qui méritent d'être précisés dans la thèse de Church-Turing.

Le premier, c'est qu'on parle ici des calculs (disons, des fonctions mathématiques) qui prennent en entrée une donnée finie et renvoient une donnée finie[#15]. Ce que j'entends par donnée finie ici, c'est n'importe quel objet qui peut être représenté de façon complète et inambiguë par un nombre fini de symboles, donc par exemple dans la mémoire d'un ordinateur (où ce sera une suite finie de 0 et de 1) : un nombre entier est un exemple de donnée finie (c'est même le prototype d'une donnée finie), parce qu'on peut l'écrire complètement, alors qu'un nombre réel exact, avec son infinité de décimales, ne constitue pas une donnée finie[#16].

[#15] Le billet que j'avais initialement pour projet d'écrire aurait parlé de calculabilité d'ordre supérieur, donc ce qui se passe quand on essaie de définir la notion de calculabilité sur des fonctions qui prennent en entrée une autre fonction (et justement, il faut se demander comment cette autre fonction est présentée : comme une boîte noire qu'on peut interroger ? comme un programme qui la calcule ? — il s'avère que, sous certaines hypothèses, ça ne change rien, et c'est une des formulations possibles du théorème de Kreisel-Lacombe-Shoenfield).

[#16] Notons tout de même qu'il y a toutes sortes de nombres réels qu'on peut représenter exactement comme des données finies. Le plus évident est celui des rationnels : par exemple, même si 3/7 = 0.42857142857… a une infinité de décimales, le fait de pouvoir l'écrire comme 3/7, justement, et de savoir faire des calculs sur les fractions, permet de traiter cette écriture comme une donnée finie. Mais de façon plus subtile, on peut aussi traiter les nombres algébriques (des choses comme √2 ou ∛(2−√3), disons) comme des données finies, et des logiciels de calcul formel comme Sage ou Mathematica ou Maple savent les manipuler de façon exacte. D'autres choses qu'on peut considérer comme des données finies sont par exemple : une chaîne de caractères, une suite finie d'entiers, un graphe fini. En revanche, une suite infinie d'entiers n'est plus une donnée finie.

Je viens de dire que les entiers (disons, les entiers naturels, c'est-à-dire positifs) sont des données finies, mais il y a autre chose : on peut représenter (coder) n'importe quelle donnée finie sous forme d'un entier naturel. Qu'est-ce que ça veut dire ?

C'est un point un peu technique, et qui n'est pas vraiment fondamental pour la calculabilité, mais qui simplifie énormément son étude et sa présentation théorique : la calculabilité s'intéresse à des programmes qui prennent en entrée une donnée finie et renvoient une autre donnée finie. Or il y a énormément de sortes[#17] de données finies (déjà, par exemple, le programme peut peut-être prendre 42 nombres en entrée : or 42 entiers, c'est encore « une donnée finie »). Pour pouvoir parler de toutes à la fois, et unifier l'étude de la calculabilité, il est commode d'avoir une seule sorte de donnée finie qui permet de toutes les représenter. Il se trouve que les entiers naturels peuvent jouer ce rôle (ce n'est pas la seule : dans les ordinateurs réels, ce serait plutôt suites finies de ‘0’ et de ‘1’ qui joue ce rôle “universel” ; mais un entier naturel écrit en binaire ou une suite finie de ‘0’ et de ‘1’, c'est un peu la même chose).

[#17] Le typage est la discipline informatique qui étudie, justement, la manière de bien séparer toutes ces données finies pour ne pas les mélanger. C'est en quelque sorte le point de vue exactement opposé au codage de Gödel (tout est un entier naturel) dont je parle ici.

Bref, quand on a affaire à une donnée finie, la théorie de la calculabilité aime bien utiliser les nombres entiers (et plus précisément les entiers naturels, c'est-à-dire positifs), pour les représenter. C'est-à-dire qu'on peut faire comme si toute donnée finie était un entier (naturel), et au lieu de parler de fonction prenant une donnée finie et renvoyant une donnée finie, on parle de fonction prenant un entier et renvoyant un entier, c'est mathématiquement plus simple et plus commode à manier. Cette astuce (représenter toute donnée finie comme un entier), qu'on appelle le (un ?) codage de Gödel est un point technique qui n'est pas vraiment important pour la compréhension profonde du sujet ou sa philosophie, mais simplifie énormément sa présentation théorique[#18]. À titre d'exemple, comme deux entiers naturels (ou trois, ou 42) constituent encore une donnée finie, on peut les coder comme un seul entier naturel, on peut se contenter d'étudier la calculabilité des fonctions d'un seul argument[#19].

[#18] En pratique, c'est une terriblement mauvaise idée : si vous écrivez une fonction informatique qui doit prendre deux entiers en entrée, ce serait vraiment stupide de les coder sous forme d'un unique entier. On a même développé toutes sortes de techniques informatiques (le typage, donc) permettant de bien séparer les différentes sortes de données finies qu'un ordinateur peut manier (et qui sont, en interne, juste des suites finies de 0 et de 1) : le codage de Gödel fait exactement le contraire et met tout dans le même sac, c'est terrible du point de vue programmation, mais pour l'étude théorique de la calculabilité cela simplifie considérablement les choses.

[#19] Il faut, bien sûr, que les fonctions choisies pour coder la donnée considérer comme un entier naturel et pour la décoder soient calculables. En pratique, ça laisse énormément de possibilités. À titre d'exemple, pour représenter deux entiers naturels m,n, un codage assez standard consiste à utiliser l'unique entier ⟨m,n⟩ := m + (m+n)(m+n+1)/2 : le fait que j'aie donné une formule explicite avec uniquement des opérations arithmétiques usuelles assure bien que le calcul de ⟨m,n⟩ à partir de m et n est algorithmiquement faisable (i.e., calculable), et inversement, pour retrouver m et n à partir de p = ⟨m,n⟩ en calculant d'abord s = ⌊(−1+√(1+8p))/2⌋ (où ⌊·⌋ désigne la partie entière), ensuite m = p − s(s+1)/2 et enfin n = s − m.

☞ Programmes qui ne terminent jamais

Un autre point qu'il faut que je signale, c'est la possibilité qu'un programme ne termine jamais, car c'est une complication inévitable de la théorie. Cela correspond à la situation où l'algorithme tourne indéfiniment (il mène des calculs qui n'aboutissent jamais, auquel cas on dira que la fonction qu'il calcule n'est pas définie sur les entrées qu'on lui a passées) : une situation qui a priori ne nous intéresse pas (si on s'intéresse à un algorithme, c'est bien pour qu'il donne un résultat !), mais une conséquence des résultats de Turing est justement qu'on ne pourra pas définir de notion de calculabilité ou d'algorithme sans introduire, fatalement, aussi des algorithmes qui ne terminent pas (il n'y a pas de moyen de les séparer des autres). Autrement dit, même si ces « algorithmes qui ne terminent pas » ne nous intéressent pas (et ne méritent peut-être même pas le nom d'algorithme, en tout cas c'est discutable), on doit accepter la possibilité qu'un algorithme ne termine pas pour l'étude théorique de la calculabilité, car on va expliquer qu'ils sont impossibles à séparer[#20] des autres.

[#20] Par exemple, si j'essaie de définir un langage de programmation informatique dans lequel tout programme termine forcément, en me disant que c'est bien ce que je veux, eh bien ce langage sera forcément incapable de représenter certains programmes qui pourtant correspondent à un vrai bon algorithme qui termine : en cherchant à écarter des « mauvais » algorithmes, on en écarte forcément aussi des « bons ».

☞ Les programmes sont eux-mêmes des données finies

Bon, maintenant, là où la calculabilité devient intéressante, c'est quand on prend note de l'idée suivante :

Un programme informatique constitue une donnée finie, donc il est possible de passer un programme comme entrée à un autre programme, et il est intéressant de se demander ce qu'il peut en faire.

(Un programme pourra aussi produire un autre programme en sortie, pour la même raison, même si cette idée-là n'aboutira pas spécialement à des conclusions surprenantes.)

Le fait de pouvoir manipuler informatiquement des programmes informatique est un des points centraux de l'informatique (on peut parler de façon générale de métaprogrammation), et de fait, il y a toutes sortes de programmes qui manipulent d'autres programmes (par exemple, un compilateur est un programme qui transforme un programme écrit dans un certain langage de programmation dans un programme écrit dans un autre langage de programmation — généralement vers un langage plus simple ; un interpréteur, lui, prend un programme écrit dans un certain langage de programmation, et l'« exécute », c'est-à-dire qu'il le fait tourner, et je vais revenir sur cette possibilité).

Ce qui justifie de manipuler les programmes comme des données finies c'est le fait qu'on peut les écrire formellement : c'est, en quelque sorte, le bénéfice d'avoir défini précisément la notion d'algorithme : quelle que soit la définition précise choisie (soit mathématique — fonction générale récursive, terme du λ-calcul, machine de Turing —, soit pragmatique, comme un langage de programmation réel et « idéalisé »), elle vient avec la possibilité de « coder » un algorithme comme une suite de caractères, ou, en principe, comme un entier naturel (cf. ce que j'ai écrit sur le codage de Gödel).

Maintenant, que peut faire un programme avec un programme qu'on lui passe en argument (= en entrée) ? Il pourrait, par exemple, chercher à l'exécuter, et on va voir que ceci est effectivement possible ; il pourrait aussi chercher à l'analyser, et on va voir que ceci est généralement impossible (enfin, il peut essayer, et il peut certainement faire certaines choses, mais une analyse à coup sûr va être impossible).

Il peut aussi faire des transformations dessus. Par exemple, si on se donne deux programmes p et q, on peut fabriquer algorithmiquement le programme q∘p qui exécute d'abord p puis (si cette exécution termine) exécute q en lui fournissant en entrée la sortie de p : ce que je veux dire, c'est que non seulement il y a un programme q∘p qui fait p puis q, mais aussi et surtout qu'on peut construire un programme (un « méta-programme », si on veut) qui prend en entrée p et q et produit en sortie le programme composé q∘p que je viens de décrire. Ou encore[#21] : si on se donne un entier n et un programme p qui attend deux entrées, il est possible de fabriquer algorithmiquement un programme p(n,—) qui prend une entrée et exécute p sur l'entrée n et cette autre entrée (et là aussi, je veux dire qu'il y a bien un algorithme ou « méta-programme » qui prend en entrée n et p et fabrique p(n,—)). La possibilité de faire ce genre de transformations élémentaires, et de les faire algorithmiquement, est un point un peu technique et qui n'est pas techniquement compliqué, mais il est essentiel à faire marcher la théorie, donc je me dois de le signaler explicitement.

[#21] Ce que j'évoque ici est le théorème s-m-n.

☞ Un programme « universel »

Maintenant, ce qui est déjà plus intéressant, c'est la possibilité pour un programme d'en exécuter un autre. Et c'est là qu'apparaît une des notions fondamentales de la calculabilité :

On peut construire un « programme universel », c'est-à-dire un programme qui prend en entrée un autre programme (ainsi que d'éventuels arguments à passer en entrée à ce programme) et l'exécute, c'est-à-dire qu'il se comporte comme le programme qu'on lui a passé.

Notamment, si le programme passé en argument au programme universel renvoie un résultat, le programme universel renvoie le même résultat. Si le programme passé en argument ne termine jamais, le programme universel ne termine jamais non plus. Il n'y a pas de magie : le programme universel fait juste ce qu'on lui dit de faire.

• Philosophiquement, ça traduit le fait qu'« exécuter un algorithme » est algorithmique (et c'est justifié par le fait, que, justement, cela n'implique aucune sorte de créativité on d'ingéniosité : on suit juste les instructions fournies).

• Informatiquement, ça traduit l'existence d'un programme interpréteur (un programme qui prend un autre programme en entrée et qui l'exécute), et de fait, c'est quelque chose qu'on utilise réellement pour toutes sortes de raisons. (On peut aussi parler de simulation pour souligner que le programme universel, interpréteur fait « comme si » on faisait tourner directement le programme interprété.)

  Mais on peut aussi considérer (toujours sur le plan informatique) que l'idée est au cœur de la notion moderne d'ordinateur : au lieu que l'ordinateur exécute un programme fixé (codé « en dur » dans l'ordinateur, comme les tout premiers ordinateurs qu'il fallait recâbler pour chaque algorithme qu'on voulait leur faire appliquer), le programme est lui-même stocké en mémoire comme les données sur lesquelles il va opérer : l'ordinateur se comporte donc comme une machine « universelle », capable d'exécuter (interpréter, simuler, comme on voudra dire) n'importe quel programme qu'on lui fournit.

• Mathématiquement, c'est dire que la fonction résultat de l'exécution du programme p sur l'entrée x (si elle est définie) est calculable dans ses deux variables (elle est par définition calculable en x à p fixé, mais ce qui est intéressant est qu'on peut aussi faire varier p).

Tout ça à la fois évident et pas du tout évident. C'est évident, parce qu'« il n'y a pas de magie », justement : on demande juste au programme universel de suivre les instructions du programme qu'on lui fournit. Mais en même temps, ce n'est pas évident, parce que, en pratique, écrire un interpréteur d'un langage de programmation dans le langage lui-même n'est généralement pas facile[#22][#23].

[#22] Si le langage est un langage de bas niveau, c'est pénible parce qu'il s'agit d'écrire dans un langage de bas niveau. Si c'est un langage de haut niveau, c'est pénible parce que ça fait d'autant plus de travail pour l'interpréteur. Les langages pour lesquels c'est le moins pénible sont sans doute les langages de la famille Lisp. (Pour en savoir plus à ce sujet, outre le Wizard Book, qui est librement disponible en ligne ici, je peux renvoyer à cet exposé de William Byrd dont voici par ailleurs un compte-rendu. Tout ça est très instructif, mais ce n'est plus vraiment grand public.)

[#23] Peut-être que certains lecteurs seront confusés par le point suivant : j'ai déclaré plus haut comme technique et à peu près évident le fait Ⓐ qu'on puisse écrire un programme qui, donnés deux programmes p et q en entrée, produit un programme composé q∘p dont l'exécution revient à exécuter p puis q (peu importent les détails), et maintenant je parle Ⓑ d'écrire un programme qui, donné un programme p, exécute p. On risque peut-être de se dire que Ⓑ paraît plus simple que Ⓐ puisqu'il n'y a qu'un seul programme à exécuter. Mais ce n'est pas du tout ça le problème : si je change Ⓐ pour qu'il n'y ait qu'un seul programme, je demande d'écrire un programme qui donné un programme p en entrée, produit un programme dont l'exécution fait la même chose que p… et ça c'est complètement évident, il suffit de renvoyer le programme p qu'on a reçu. Ce qui rend la tâche de l'interpréteur délicate, c'est qu'il doit exécuter lui-même (« là, maintenant ») le programme p qu'on lui a fourni, pas renvoyer un autre programme qui fait pareil. ((Méta : voilà typiquement le genre de choses que je ne sais pas bien expliquer sans introduire de notation ou de formalisme mathématique (ici, par exemple, le fait Ⓐ est valable pour les fonctions primitives récursives, mais la propriété Ⓑ ne vaut pas pour elles, ce qui montre bien la différence) ; et c'est le genre de situation où je me demande s'il vaut mieux signaler la difficulté, quitte à embrouiller le lecteur encore plus, ou la passer sous silence. Il y a une vraie difficulté pédagogique.))

☞ Exécution en temps limité

(La section qui suite est peut-être un peu plus technique. On peut l'ignorer et passer à la suivante.)

Comme je l'ai suggéré, et c'est un thème qui va être très important (donc je vais y revenir), on ne peut pas savoir à l'avance si un programme terminera. Le programme universel, je répète, quand on lui donne un autre programme à exécuter, ne fait « pas de magie » : il l'exécute jusqu'à ce que ce programme termine, si ça se produit un jour (et sinon, eh bien l'exécution ne termine jamais). Il est quand même utile et important de savoir qu'on peut exécuter un programme avec une limite de temps :

C'est (essentiellement) le théorème de la forme normale de Kleene : celui-ci affirme, informellement[#24], qu'on peut algorithmiquement simuler l'exécution d'un programme pendant un certain nombre d'« étapes » et savoir si l'exécution s'est terminée dans le temps imparti ; autrement dit, même si vous ne pouvez pas savoir à l'avance combien de temps l'exécution d'un programme mettra, ni même s'il terminera jamais, vous pouvez au moins tester si l'exécution termine en un certain temps imparti (si oui, vous aurez le résultat du calcul avec l'information qu'il a bien terminé à temps ; et sinon, vous aurez l'information qu'il lui faut plus de temps, même si vous ne saurez pas combien de temps, ce qui permet éventuellement de relancer ultérieurement le calcul pour un plus grand nombre d'étapes).

[#24] Un peu plus précisément : on peut construire un programme qui, donné un programme p, des éventuelles entrées à fournir à p, et un entier n (la borne de temps), va lancer l'exécution de p (sur les entrées fournies) pendant au plus n étapes, et si cette exécution a terminé en au plus n étapes, renvoie oui, c'est terminé à temps, et le résultat est ceci (avec le résultat produit par p, et éventuellement le nombre exact d'étapes utilisé si on le souhaite), et sinon renvoie non, en n étapes, l'exécution n'a pas abouti (et éventuellement le contexte qui permet de la continuer plus tard, mais comme on fait de la calculabilité ce n'est pas important de continuer, on peut tout reprendre à zéro et pour un plus grand nombre d'étapes, vu que l'efficacité n'est pas une préoccupation). Je vais commenter sur le sens du mot étape ci-dessous.

Il n'y a toujours rien de magique ici (on ne sait toujours pas si le calcul exécuté va finir un jour), mais on a un contrôle un peu plus fin qu'avec la « pure » machine universelle : on a la garantie que notre tentative d'exécution termine, même si ça peut être avec le message il me faut plus de temps (le programme simulé n'a pas terminé). Je vais expliquer à quoi ça peut servir.

Un mot sur la notion d'étape (ou de temps) d'exécution. Si on pense aux algorithmes comme des machines de Turing, leur fonctionnement se déroule vraiment sous forme d'étapes élémentaires très simples qui se déroulent séquentiellement, et ça rend ce théorème particulièrement transparent : il peut s'agir de simuler l'exécution de la machine de Turing pour (au plus !) le nombre d'étapes qu'on s'est fixé. D'autres présentations de la calculabilité de Church-Turing ne rendent pas forcément cette notion aussi transparente[#25]. Mais peu importe : la seule chose qui importe sur la notion d'« étape » ou de « borne sur le temps d'exécution », c'est que :

• si le calcul termine, alors il y a un nombre d'étapes assez grand tel qu'il termine dans ce temps imparti,
• si le calcul ne termine pas, alors il ne termine en aucun temps imparti,

— et ce sont les seules propriétés dont on a besoin pour l'étude de la calculabilité.

[#25] Si on est passé par les fonctions générales récursives, on une notion d'« arbre de calcul », et on peut dire qu'il s'agit de rechercher un arbre de calcul pour la fonction donnée parmi les n premiers entiers susceptibles d'en coder un ; mais pour le λ-calcul, c'est beaucoup moins évident. Digression technique à ce sujet : le problème dans le cas du λ-calcul est qu'on aurait envie de fournir les programmes à évaluer directement comme des termes du λ-calcul (et pas comme des codages compliqués de ces termes). Et de fait, pour faire une fonction universelle qui prend un programme p et une entrée x et évalue p sur x, sous cette forme, c'est trivial : λp.λx.px fait ce qui est demandé. Mais avec une borne sur le temps (dont je ne sais même pas bien ce qu'elle devrait signifier), est-ce encore possible de prendre le programme « non codé » ? (De manière à faire l'économie d'avoir à écrire un véritable interpréteur du λ-calcul dans le λ-calcul.) Il continue à y avoir là quelque chose qui me dérange, et dont j'avoue ne pas bien comprendre la profondeur : est-ce que quelque chose empêche qu'on puisse écrire un terme du λ-calcul qui, disons, prenant un autre terme p (directement comme terme du λ-calcul, et pas codé comme autre chose), un argument x (je vais supposer p et x en forme normale) et un entier (de Church) n, va évaluer px si celui-ci termine (= admet une forme normale) en au plus n étapes (pour une certaine définition d'étape) et s'évaluer en 0 ou 1 selon que l'évaluation a terminé ? Est-ce qu'il y a un obstacle profond ? Est-ce que c'est juste un problème technique ? Je ne comprends pas bien.

À quoi cela peut-il bien servir d'exécuter un programme avec une limite sur le temps, si on n'obtient qu'un résultat du style il me faut plus de temps s'il n'a pas fini dans le temps imparti ? Cela sert par exemple à prouver un résultat comme celui-ci :

‣ Proposition : on peut construire un programme qui prend en entrée deux programmes p et q (ainsi que d'éventuels arguments à passer en entrée à ces programmes respectifs), et va renvoyer soit le résultat de p soit le résultat de q, pour peu qu'au moins l'un des deux termine (si exactement l'un termine, son résultat sera renvoyé, si les deux terminent, l'un des deux sera renvoyés sans garantie duquel, et si aucun des deux ne termine, l'exécution ne terminera pas).

La preuve est à peu près évidente en utilisant cette possibilité (fournie par le théorème de la forme normale) de lancer une exécution avec une borne de temps : on lance l'exécution alternativement de p et de q avec des bornes de plus en plus longues, jusqu'à ce que l'un soit terminé dans le temps imparti, et on renvoie alors son résultat. On appelle ça une exécution en parallèle[#26]. Évidemment, avec une notion assez informelle d'algorithme, on aurait pu de toute façon dire on lance p et q en parallèle jusqu'à ce que l'un s'arrête, et on renvoie le résultat de l'exécution qui s'est arrêtée en premier, mais le théorème de la forme normale de Kleene justifie rigoureusement le sens donné à ce en parallèle sans que ça fasse forcément partie des constructions autorisées dans la notion d'algorithme.

[#26] Et ce n'est pas qu'une idée complètement théorique : à un certain niveau, c'est ce que font les ordinateurs réels pour exécuter plusieurs programmes « en même temps » même quand ils n'ont qu'un processeur (ou plus généralement, pour lancer plus de programmes en même temps qu'ils n'ont de processeurs) : ils lancent un petit peu de chaque programme, en tournant entre eux, ce qui sous-entend bien la possibilité d'interrompre une exécution inachevée et de la reprendre ultérieurement.

☞ L'astuce de Quine pour l'auto-référence

J'en viens à un point qui peut sembler technique et anecdotique, mais qui est un outil extrêmement puissant en calculabilité : l'astuce de Quine (pour l'auto-référence). Je précise immédiatement que cette astuce n'a pas grand-chose à voir avec son éponyme[#27] ; l'association du nom de Quine à cette astuce (et notamment aux programmes qui impriment leur propre code source) a été proposé par Douglas Hofstadter, mais en vérité il s'agit essentiellement de l'argument diagonal de Cantor, sous une forme réutilisée par Gödel pour démontrer son théorème d'incomplétude (qui passe par une forme d'auto-référence, cf. ce que j'en disais ici et là), puis adapté par Turing dans le contexte de la calculabilité, et enfin formalisé par Kleene, et généralement on parle du (second) théorème de récursion de Kleene. Mais qu'est-ce que ça dit ?

[#27] Illustration parfaite du principe d'Arnol'd : si une notion porte un nom propre, ce n'est pas le nom de son découvreur.

La version informelle que j'aime bien donner est la suivante :

Cela ne change rien aux capacités d'un programme de lui donner accès à son propre code source (i.e., à sa propre représentation informatique comme donnée finie) ; autrement dit, on peut toujours supposer, lors de l'écriture d'un programme, qu'il a accès à « lui-même », même si cette possibilité n'était pas nativement prévue par le cadre ou langage de programmation utilisé pour définir la calculabilité.

Par exemple, grâce à l'astuce de Quine, vous pouvez, dans n'importe quel langage de programmation généraliste, écrire un programme qui affiche son propre code source (sans aller le lire sur disque). C'est un exercice instructif de programmation, et qui ne nécessite aucune prouesse relative au langage : une fois comprise l'astuce de Quine, cela peut se faire de façon systématique, avec un programme clair, propre, joliment présenté et abondamment commenté (et qui affichera, du coup, un code source clair, propre, joliment présenté et abondamment commenté). J'ai écrit il y a très longtemps une page expliquant de façon détaillée (et, j'espère, pédagogique) comment s'y prendre[#28].

[#28] Pour résumer l'idée : votre programme devra contenir à la fois du code (qui sert à imprimer) et des données (qui disent quoi imprimer). L'astuce de Quine est essentiellement que les mêmes données peuvent à la fois servir à imprimer le code et à imprimer l(a représentation textuelle de)s données elles-mêmes. Par conséquent, on choisit une façon de représenter le code sous forme de données, puis on écrit le code qui utilise de telles données pour imprimer le code qu'elles représentent, puis pour imprimer les données elles-mêmes (via la représentation qu'on a choisie), et enfin il n'y a plus qu'à mettre ce code sous la représentation qu'on a choisie. L'analogie (proposée par Hofstadter) avec la biologie est la suivante : le code, c'est l'être vivant qui doit se reproduire, et qui dispose des mécanismes pour le faire, les données, c'est le génome, qui encode, sous une certaine représentation, de quoi reproduire l'être vivant ; l'être vivant doit donc être capable à la fois de se reproduire en utilisant son génome, mais aussi de reproduire le génome lui-même, et le génome doit encoder les outils nécessaire pour ces deux fonctions. Mais une fois qu'on a tout ça, on reproduit bien le tout.

Bien sûr, ce n'est pas que pour « imprimer » son code source que l'astuce de Quine peut servir, on peut en faire n'importe quoi d'autre (l'imprimer à l'envers, le chiffrer, le comparer à autre chose, chercher à l'analyser, ou même, comme je vais discuter plus bas, l'exécuter).

Une version mathématiquement plus précise de l'astuce est la suivante :

‣ Théorème de récursion de Kleene : si f est un programme prenant notamment une entrée e (supposée être un programme), alors il existe un programme e tel que e (exécuté sur certaines entrées) fasse le même effet que f exécuté sur l'entrée e (et les autres entrées fournies). De plus, le (code du programme) e en question peut être fabriqué algorithmiquement à partir du (code du programme) f.

En clair, je peux fabriquer un programme e qui applique une certaine opération f à lui-même (c'est-à-dire à e), et je peux même le fabriquer algorithmiquement à partir du programme f.

La preuve ressemble à un tour de passe-passe. Je l'écris ici même si c'est un peu technique :

Démonstration du théorème de récursion de Kleene : pour t un programme, appelons s(t,t) le programme qui exécute t avec t comme premier argument (et les autres arguments éventuels qu'on lui a passés). La transformation de t en s(t,t) est elle-même algorithmique (il s'agit d'une manipulation de programme comme je l'ai évoqué plus haut). Il en va de même de la transformation de t en le programme qui exécute f avec l'argument s(t,t) (et les autres éventuels que je ne note pas). Appelons c le programme qui réalise cette transformation de t en f invoqué sur s(t,t).

Maintenant, considérons le programme s(c,c), que je vais appeler e : c'est-à-dire qu'il exécute c sur c lui-même ; or d'après la définition de c, cela signifie qu'il exécute f sur s(c,c), c'est-à-dire sur e. Or c'est exactement ce qui était demandé.

De plus, toute la construction que j'ai décrite est explicite et algorithmique, donc on a bien obtenu e algorithmiquement à partir de f. ∎

Dit comme ça c'est un peu illisible. De façon un peu plus informelle[#29], le programme e est le suivant :

Exécuter le programme f sur le code suivant, suivi de lui-même entre guillemets :
Exécuter le programme f sur le code suivant, suivi de lui-même entre guillemets.

[#29] Pour faire la correspondance avec la démonstration qui précède, la construction suivi de lui-même entre guillemets est ce que fait s(t,t), et le bout exécuter le programme f sur le code suivant, suivi de lui-même entre guillemets est ce que fait c.

Mais tout ça devient quand même beaucoup plus clair quand on le programme soi-même[#30].

[#30] Pour des exemples de vrai code dans ce sens, à part les exemples de programmes imprimant leur propre code, je renvoie notamment à ce billet, et spécifiquement le passage qui parle du combinateur Y et de la fonction de Fibonacci.

☞ Récursivité et non terminaison

OK, on a cette astuce de Quine permettant à un programme de faire comme s'il avait accès à « lui-même », i.e., à son propre code source. Mais à quoi cela peut-il servir ? Écrire un programme qui écrit son propre code source, c'est joli, mais pas fantastiquement utile ni même théoriquement instructif.

Voici une première chose qu'un programme peut faire avec « lui-même » (i.e., avec son propre code source) : il peut s'exécuter. C'est, si on veut, la notion de récursivité en programmation, c'est-à-dire la possibilité qu'un programme fasse appel à lui-même au cours de sa propre exécution. Ce que nous dit le théorème de récursion de Kleene (i.e., l'astuce de Quine), c'est que même si le cadre choisi pour la calculabilité ne permet pas « nativement » la récursivité, elle est automatiquement possible grâce à la combinaison entre cette astuce de Quine et l'existence d'un programme universel (le programme qui souhaite s'appeler lui-même peut toujours invoquer le programme universel sur lui-même, l'accès à « lui-même » étant garantie par l'astuce de Quine).

En particulier, ceci nous montre, comme je l'ai suggéré plus haut, qu'il faut obligatoirement admettre la possibilité que des programmes ne terminent pas : car je peux faire un programme qui ne termine pas en disant[#31] je commence par m'invoquer moi-même, et ensuite (si cette invocation termine) j'ajoute 1 au résultat et je renvoie ceci (si un tel programme devait terminer, il renverrait 1 de plus que lui-même, ce qui est absurde, donc c'est qu'il ne termine pas).

[#31] En pratique, pour faire un programme qui ne termine jamais par récursivité, on peut simplement s'appeler soi-même (sans avoir besoin d'ajouter 1 au résultat) : dans n'importe quelle construction raisonnable de la récursivité, ce programme ne termine en effet pas. Néanmoins, les choses sont plus subtiles qu'il n'y paraît, et il est parfaitement possible de faire un programme qui s'invoque lui-même et termine avec une valeur de retour quelconque. (Pour ceux qui veulent un énoncé précis : il existe un p tel que φ_p(q) = φ_q(q) pour tout q, et que φ_p(p) = 42 ; et il existe un p′ tel que φ_p′(q) = φ_q(q) pour tout q, et que φ_p′(p′) = 1729 : ainsi, les programmes p et p′ calculent exactement la même fonction q ↦ φ_q(q), et pourtant, quand on lance p — ou p′ — sur p on obtient un résultat différent de quand on lance p′ — ou p — sur p′ : l'un renvoie 42 quand on l'invoque sur lui-même, et l'autre renvoie 1729. Pour une preuve, je renvoie à ma feuille d'exercices, exercice 1.17.)

Le raisonnement que je viens de tenir fait appel à deux ingrédients : l'astuce de Quine et l'existence d'un programme universel. Comme l'astuce de Quine repose elle-même sur très peu de choses (le théorème s-m-n, c'est-à-dire la possibilité de faire des manipulations vraiment basiques sur un programme), c'est vraiment l'existence d'un programme universel qui est l'enjeu : dès qu'un langage de programmation est capable de s'interpréter lui-même, il est forcément capable de faire des programmes qui ne terminent jamais (et comme on veut généralement cette universalité, il faut admettre la conclusion).

☞ L'indécidabilité du problème de l'arrêt

Mais bon, la plupart des langages de programmation permettaient déjà la récursivité, donc le raisonnement ci-dessus ne nous apprend pas grand-chose. En revanche, le modèle de raisonnement est fondamental en calculabilité et est un exemple-type de la manière dont on utilise l'astuce de Quine : il s'agit de faire un programme « contrariant », qui s'amuse à déjouer les pronostics qu'on fait sur son propre comportement, cette possibilité de les déjouer étant, justement, fournie par l'astuce de Quine.

Voici un exemple fondamental et fondateur de ce type de raisonnement, (essentiellement) dû à Turing, et qu'on peut considérer comme le point de départ de toute la théorie :

‣ Indécidabilité algorithmique du problème de l'arrêt : il n'existe aucun programme qui prenne en entrée un autre programme (ainsi que d'éventuels arguments à passer en entrée à ce programme) et décide (à coup sûr, en temps fini) si cet autre programme termine.

Autrement dit, on voudrait avoir un programme qui prend en entrée un autre programme, l'analyse, et finit (à coup sûr, en temps fini) par dire oui, ce programme va terminer ou non, ce programme va tourner indéfiniment. Ou, pour résumer :

On ne peut pas détecter algorithmiquement (à coup sûr, en temps fini) si un programme va terminer.

La preuve est à peu près évidente compte tenu de ce qui a déjà été dit : je suppose par l'absurde qu'un tel programme « analyseur de l'arrêt » existe, et je fabrique un programme « contrariant » de la manière suivante : le programme contrariant demande au programme analyseur de l'arrêt (supposé exister) s'il va lui-même terminer (où lui-même = le programme contrariant ; et cette auto-référence est possible par l'astuce de Quine), puis il fait exactement le contraire de ce qu'on lui a prédit qu'il ferait — si l'analyseur lui a prédit qu'il s'arrêterait, il lance une boucle infinie, et si l'analyseur lui a prédit qu'il ne s'arrêterait pas, il s'arrête immédiatement. Manifestement ceci conduit à une contradiction (si le programme contrariant s'arrête alors l'analyseur est censé indiquer qu'il s'arrête, donc il ne s'arrête pas, et réciproquement) ; et comme la seule hypothèse qu'on a faite était l'existence de l'analyseur, on en conclut qu'il ne peut pas exister.

Ce « problème de l'arrêt » est fondamental en calculabilité parce que d'une part, comme je l'ai dit, le modèle de raisonnement qu'on a mené ici permet de démontrer toutes sortes de résultats négatifs du même genre, mais aussi parce que c'est un problème algorithmiquement indécidable qui permet de montrer l'indécidabilité de toutes sortes d'autres problèmes. C'est-à-dire que, souvent, on peut obtenir les résultats négatifs directement par une « réduction » (du type : tel ou tel problème permet de résoudre le problème de l'arrêt, donc, si le problème en question était décidable algorithmiquement, le problème de l'arrêt le serait aussi, or il ne l'est pas).

Par exemple, une généralisation du théorème de Turing ci-dessus, qui n'est pas vraiment plus difficile (et qu'on peut démontrer soit en imitant le raisonnement du théorème de Turing, soit en réduisant le problème de l'arrêt au problème évoqué) donne le théorème de Rice qui affirme que non seulement il n'est pas possible de décider si un programme s'arrête sur une entrée donnée, mais, en fait, qu'aucune propriété non-triviale sur le comportement d'un programme général[#32] n'est algorithmiquement décidable (de façon certaine en temps fini !). Autrement dit, si un programme analyseur prend un autre programme en entrée et est supposé renvoyer, à coup sûr en temps fini, une information sur le comportement de ce dernier (i.e., sur la fonction qu'il calcule, ce que j'ai appelé plus haut son extension, et cette information devant être toujours la même pour un comportement donné), alors, en fait, l'analyseur renvoie toujours la même chose pour tous les programmes.

[#32] Général car on ne fait aucune hypothèse sur le programme à analyser. Si on ajoute des garanties dessus, par exemple qu'il termine sur n'importe quelle entrée, alors il devient possible de faire des choses. Notamment, si on sait qu'il termine toujours, alors on peut l'exécuter, et regarder les valeurs qu'il produit sur telle ou telle entrée ; et le théorème de Kreisel-Lacombe-Shoenfield affirme, en gros, que c'est la seule forme d'analyse qu'on peut faire.