David Madore's WebLog: 2025-02

(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.