Méta : J'étais initialement parti pour écrire un
billet sur la calculabilité d'ordre supérieur (il aurait eu pour
titre calculabilité d'ordre supérieur : comment un programme
peut-il interroger un autre programme ?
). Mais en commençant à
écrire l'introduction pour la rendre aussi compréhensible que
possible, je me suis dit que, tant qu'à faire, ce serait plus
intéressant d'essayer de faire un billet autonome sur les bases de la
calculabilité, en cherchant à le rendre à peu près accessible au grand
public[#]. Après tout, ce sont
des notions que j'enseigne à
Télécom Paris, ça peut être intéressant d'essayer d'isoler, de façon
moins mathématique, les messages principaux que j'essaie de
communiquer aux étudiants.
[#] La notion
de grand public
est, évidemment, assez mal définie. Par
exemple,
on m'a
affirmé que si je fais une phrase avec une subordonnée, l'immense
majorité des gens ne savent plus lire. Bon, c'est peut-être vrai,
mais je pense que de toute façon cette immense majorité ne sera en
aucun cas intéressé par faire l'effort de concentration minimal pour
comprendre une tentative de vulgarisation d'un sujet scientifique,
même si cette vulgarisation est optimalement faite ; et de toute
façon, elle ne lira jamais mon blog vu que, même sur un sujet qui n'a
rien de technique, j'ai tendance à faire des phrases à la Proust.
Donc disons que je parle à des gens capables de lire une phrase de
plus que quelques mots sans perdre le fil de leurs pensées, et qui
acceptent de faire un peu d'efforts de concentration. En revanche,
j'essaie de ne présupposer du lecteur aucune connaissance préalable en
maths ni en informatique. (Ce n'est pas toujours évident, parce que
parfois on utilise un terme technique sans s'en rendre compte, et ça a
évidemment pu m'échapper.)
(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 101000000-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.