Voici un concept mathématique (voire, informatique ?) dont je suis tout étonné de découvrir que je ne l'ai jamais encore proprement défini sur ce blog, alors même que ça aurait été logique et pertinent de le faire dans différentes entrées que j'ai déjà écrites. (Par exemple, j'y fais explicitement référence dans cette entrée, et il aurait été logique d'en parler dans celle-ci ; et au sujet de cette entrée récente, je pourrais dire qu'il s'agit exactement de la puissance de calcul du niveau ω₁CK de la « Théorie de la Totalité Transfinie de Turing ».) Je voudrais donc réparer ce manque, d'autant plus que je trouve que le sujet devrait être standard, et connu, notamment, de tous les informaticiens théoriciens vaguement préoccupés de calculabilité ou de complexité (or je suis sûr que ce n'est pas le cas[#]) : une machine hyperarithmétique est un type d'ordinateur théorique strictement plus puissant que les machines de Turing, et il me semble qu'avoir en tête à la fois la notion de fonctions hyperarithmétiques (plus générales que les fonctions calculables au sens de Church-Turing, donc) et la notion de fonctions primitives récursives (plus restreintes) aide à mieux comprendre les contours de la calculabilité (y compris si on ne s'intéresse, in fine, qu'aux machines de Turing). Il me semble par ailleurs qu'il s'agit d'une notion relativement intuitive (je vais donc essayer de la présenter comme telle), qu'il est donc dommage de laisser cachée dans des textes de calculabilité supérieure un peu oubliés et au formalisme souvent obscur.
Je commence par rappeler[#2] ce que c'est que la calculabilité au sens habituel, i.e., de Church-Turing : les lecteurs pour lesquels ce concept est familier peuvent sauter jusqu'au symbole ♠ plus bas.
En bref, [une fonction] calculable
(sous-entendu : au sens
de Church-Turing) signifie [une fonction] qui pourrait être
calculé(e), en principe, par un algorithme tournant sur un
ordinateur
— sachant que cet ordinateur n'a aucune limite sur la
quantité de mémoire qu'il peut utiliser, ni sur le temps qu'il peut
prendre, à part que le temps doit être fini (et la mémoire,
du coup, automatiquement aussi).
Pour donner une définition plus précise, il y a plein de possibilités : la première qui ait été introduite historiquement, vers 1930, est le lambda-calcul de Church, mais même si elle est utile pour modéliser les langages de programmation fonctionnels, elle n'est pas très parlante intuitivement ; la seconde définition est venue par les fonctions générales récursives (je n'ai pas réussi à comprendre exactement quelle en était l'histoire, mais elles doivent être associées à un ensemble intersectant les noms suivants : Herbrand, Gödel, et Kleene) ; mais la définition de la calculabilité qui a vraiment achevé de convaincre le monde des mathématiciens qu'il s'agissait de la bonne notion est venue en 1936 quand Turing a défini la machine qui porte maintenant son nom. Quantité d'autres définitions ont été données depuis (par exemple avec des machines à registres). J'en donnerai moi-même une (illisible) ci-dessous comme produit dérivé d'une définition rigoureuse du sujet principal de cette entrée (pour les fonctions calculables, retirer la clause (vii) qui me sert à définir les fonctions hyperarithmétiques). Le point important est que toutes ces définitions sont équivalentes au sens où elles conduisent à la même classe de fonctions « calculables » : la fameuse thèse de Church-Turing affirme que n'importe quelle tentative pour définir la notion de « fonction calculable par un algorithme » aboutira, in fine, à cette même classe des fonctions calculables (au sens de Church-Turing, donc), étant bien entendu que l'« algorithme » doit manipuler à tout instant des données finies, et terminer en temps fini (et, par ailleurs, ne peut pas faire appel au hasard, ou en tout cas le résultat final ne doit pas en dépendre).
Ainsi, la notion de fonction calculable est une de ces notions
qu'il vaut sans doute mieux ne pas définir formellement :
parce qu'il est beaucoup plus efficace de décrire des algorithmes de
façon informelle (informel
ne voulant pas
dire imprécis
!) que de faire appel à un modèle particulier de
calcul (personne n'a vraiment envie de programmer une machine de
Turing). Par exemple, si je veux expliquer que la fonction décide si
un entier n est un nombre premier (i.e., renvoie 1 si oui
et 0 si non) est calculable, le mieux est de dire c'est bien le
cas, parce qu'on peut tester pour tout
1<i<n si i divise n
en calculant le reste de la division
que d'écrire un programme
explicite ou une fonction générale récursive ou que sais-je encore.
C'est d'ailleurs ça qui rend le style des articles
de Post très
agréable et ceux de Kleene illisibles. Néanmoins, si on tient
vraiment à définir formellement la notion, on peut partir
d'essentiellement n'importe quel langage de programmation informatique
réel ou simplifié[#3], et
supposer qu'il tourne sur un ordinateur sur lequel la mémoire ne
viendra jamais à manquer (on va aussi supposer, pour éviter des
difficultés, que les entiers peuvent prendre des valeurs
arbitrairement grandes, et par ailleurs il faut interdire l'appel à un
générateur aléatoire) : Douglas Hofstadter a, par exemple, défini
exprès
le langage
FlooP dans son célèbre ouvrage de vulgarisation Gödel,
Escher, Bach (l'intérêt est en outre qu'il l'accompagne du
langage BlooP qui permet, lui, d'exprimer exactement l'ensemble plus
limité des fonctions primitives
récursives). À partir du moment où le langage peut faire des
opérations arithmétiques, des tests et des boucles, il est quasiment
garanti d'être
« Turing-complet »,
i.e., de définir justement les fonctions calculables au sens de
Church-Turing. Les fonctions calculables au sens de Church-Turing
sont donc bien celles qui sont calculables par un algorithme, ou, si
on préfère, implémentables dans n'importe quel langage de
programmation idéalisé (idéalisé
au sens où on aurait retiré
les limites évidentes d'implémentation).
Bref, la notion de calculabilité est en fait connue de toute personne qui a déjà étudié ou écrit un algorithme ou un programme. Il y a néanmoins quelque chose que je dois souligner : quelle que soit l'approche choisie (lambda-calcul, fonctions générales récursives, machines de Turing, ou tel ou tel autre langage ou modèle de calcul), pour définir les fonctions calculables, il faut nécessairement définir au passage des fonctions « partielles », c'est-à-dire, qui ne sont pas forcément définies partout. La raison en est que l'algorithme qui les calcule ne termine pas forcément en temps fini, et comme je vais l'expliquer il peut être impossible de le savoir en général : on laissera donc la valeur de la fonction non définie si l'algorithme censé la calculer ne termine pas. • Je crois que cette subtilité est ce qui a été le principal obstacle historique à dégager la notion de calculabilité : on a d'abord tenté de formaliser des concepts d'algorithmes qui terminent forcément (par exemple, la notion de fonction primitive récursive, dont je ne connais pas non plus exactement l'histoire), Ackermann a montré que ce concept n'était pas exhaustif, et on voyait bien que quelle que soit la notion d'algorithme-terminant-forcément qu'on dégage, l'argument diagonal va donner un nouvel algorithme terminant forcément mais qui n'est pas décrit par cette notion. Depuis Church et Turing, le point de vue est différent : on définit les fonctions calculables partielles, c'est-à-dire celles qui sont calculées par un algorithme pouvant terminer ou non (s'il ne termine pas en temps fini, la fonction n'est juste pas définie), et parmi ces fonctions, celles qui ont le bon goût d'être effectivement définies partout sont dites calculables [totales]. Et ce que Turing montre avec l'argument diagonal (que je vais reproduire ci-dessous en substance), c'est qu'il n'est justement pas algorithmiquement faisable, i.e., pas calculable, de décider si un programme donné s'arrête (sur une entrée donnée, ou, en fait, sur une entrée fixée quelconque) : c'est ce qu'on appelle le problème de l'arrêt. Finalement, en admettant la possibilité de fonctions calculables non totales, l'argument diagonal, au lieu de montrer que la notion de calculabilité ne capture pas toutes les fonctions algorithmiquement calculables, montre maintenant qu'il existe des fonctions qui ne sont pas calculables.
♠ Maintenant,
imaginons qu'on veuille définir des machines strictement plus
puissantes que les machines de Turing. On peut certainement le faire
de façon ad hoc : par exemple, comme les machines de Turing ne
peuvent pas résoudre le problème de l'arrêt (i.e., décider en temps
fini si une — autre — machine de Turing donnée s'arrêtera en temps
fini ou non), on peut donner à la machine la possibilité
supplémentaire d'avoir cette information ; on définit ainsi une
machine de Turing « avec l'oracle de l'arrêt », qui peut faire ce que
peut faire une machine de Turing ordinaire, mais qui peut aussi à tout
moment « consulter l'oracle », ce qui signifie que la machine présente
à l'oracle une machine de Turing ordinaire (et éventuellement une
bande initiale finie, mais ce n'est pas important), et l'oracle
répondra (instantanément !) si cette machine termine en temps fini ou
non. Ou, si on préfère imaginer un langage de programmation idéalisé
plutôt qu'une machine de Turing, ce langage est enrichi par une
fonction (magique !) halting_oracle(), qui prend en
argument un programme ou une fonction f du même langage,
mais n'utilisant pas la
fonction halting_oracle() en question, et elle renvoie
(instantanément !) vrai ou faux selon que le calcul de f(0)
termine en temps fini ou pas (le 0 est sans importance ici : ça ne
changerait fondamentalement rien de mettre une autre valeur, de ne pas
en mettre du tout — ou de prendre la valeur à passer en argument en
paramètre à halting_oracle(), ce qui est peut-être plus
standard).
Il va de soi qu'une telle machine n'est pas réalisable physiquement
(ou en tout cas, on ne sait pas comment, et ce serait vraiment
extrêmement surprenant qu'elle le
soit[#4]), mais elle est
néanmoins mathématiquement bien définie. La famille des fonctions
qu'elle sait calculer (i.e., les fonctions « calculables à partir de
l'oracle de l'arrêt ») est strictement plus vaste que celle des
fonctions calculables au sens de Church-Turing (i.e., sans cet oracle
de l'arrêt). Par définition, l'oracle de l'arrêt permet de résoudre
le problème de l'arrêt (des machines de Turing ordinaires), mais en
fait, il permet de répondre à énormément d'autres questions. Par
exemple, si je veux savoir si
la conjecture
de Goldbach (celle qui affirme que tout nombre pair est la somme
de deux nombres premiers) est vraie, j'écris un programme qui
énumère les nombres pairs n et, pour chacun d'eux, énumère
tous les entiers impairs k plus petits et teste
si k et n−k sont tous les deux
premiers : si oui, le programme passe au n suivant
(i.e., n+2) ; tandis que si pour un n donné on ne
trouve pas de k tel que k
et n−k soient premiers, le programme s'arrête ;
ainsi, ce programme tournera indéfiniment si la conjecture de Goldbach
est vraie, et s'arrêtera si elle est fausse ; en utilisant l'oracle de
l'arrêt sur ce programme, on décide donc la question. Et énormément
de problèmes mathématiques sont ainsi décidables par une telle machine
(autre exemple,
l'hypothèse
de Riemann, même s'il faut travailler un peu plus pour le voir).
En outre, une machine disposant de l'oracle de l'arrêt permet de
décider si n'importe quel énoncé mathématique est ou n'est
pas un
théorème [de ZFC] (il suffit d'appliquer l'oracle de
l'arrêt à un programme qui énumère toutes les démonstrations
mathématiques possibles [dans ZFC] — par exemple en
énumérant toutes les chaînes de caractères possibles et en ignorant
celles qui ne vérifient pas toutes les lois de la logique — et
s'arrête s'il trouve une démonstration de l'énoncé proposé) : je
renvoie à cette entrée passée sur
la distinction entre être vrai
et être un théorème
, qui
est très importante dans cette phrase. En tout cas, l'oracle de
l'arrêt est extrêmement puissant.
Pourtant, l'oracle de l'arrêt a ses limites : les machines de
Turing-avec-oracle-de-l'arrêt peuvent (par définition) résoudre le
problème de l'arrêt des machines de Turing ordinaires, mais pas le
problème de l'arrêt des machines de Turing-avec-oracle-de-l'arrêt.
Autrement dit, on obtient quelque chose d'encore plus puissant si on
permet de décider l'arrêt de ces machines-là. Ou, si on préfère, j'ai
représenté ci-dessus l'oracle de l'arrêt comme une
fonction halting_oracle() qui prend en argument une
fonction f et décide si cette fonction termine en temps
fini, mais à condition que f ne fasse pas appel
à halting_oracle() : on peut introduire une fonction plus
puissante, halting_oracle_2(), qui fonctionne même
si f fait appel à halting_oracle() — mais pas,
cette fois, à halting_oracle_2(). Grâce à cet oracle
plus puissant, on peut décider d'autres problèmes mathématiques, par
exemple la question de si P≟NP (en gros, on
applique halting_oracle_2() à un programme qui énumère
tous les algorithmes possibles et toutes les bornes polynomiales
possibles et qui, pour chaque paire,
utilise halting_oracle() pour décider si l'algorithme
résout bien toutes les instances d'un problème NP-complet
(fixé) en temps imparti). • On peut continuer ainsi à accumuler les
niveaux finis d'oracles, ce qui correspond en gros à
la hiérarchie
arithmétique. Mais comme le nom le suggère, une machine
hyperarithmétique est encore plus puissante que tout ça. (Elle est
même strictement plus puissante que la possibilité
d'appeler halting_oracle_omega(), qui fonctionne avec les
programmes utilisant n'importe quel niveau
de halting_oracle_n().)
Pourquoi, me demandera-t-on peut-être, ne pas directement imaginer
une fonction halting_oracle_ultimate() qui fonctionnerait
sur les fonctions f pouvant faire appel
à halting_oracle_ultimate() ? Tout simplement parce que
ceci serait immédiatement contradictoire : en utilisant une technique
proche des quines (c'est-à-dire les programmes qui écrivent leur
propre code source :
cf. cette page où
j'explique très en détail comment une telle chose se fait), on
pourrait écrire un programme qui demande à la
fonction halting_oracle_ultimate() est-ce
que je vais m'arrêter ?
, et, si la fonction répond oui,
lancer une boucle infinie, tandis que si elle répond non, s'arrêter,
ce qui contredit la réponse de l'oracle et montre que celui-ci n'est
pas bien défini (vu qu'il est circulaire, ce n'est pas très
surprenant). Ce que je viens d'expliquer, d'ailleurs, montre en
particulier pourquoi le problème de l'arrêt ordinaire n'est pas
résoluble par une machine de Turing ordinaire, ou pourquoi
essentiellement aucune sorte de machine ne peut résoudre le problème
de l'arrêt de sa propre classe (bon, il y a quelques hypothèses
implicites sur la classe de calculabilité dans ce raisonnement, mais
pas grand-chose). La machine hyperarithmétique va passer aussi près
qu'elle peut de cette impossibilité en l'évitant subtilement : une
machine hyperarithmétique ne pourra pas déterminer si une machine
hyperarithmétique s'arrête, mais elle pourra faire « presque aussi
bien » en considérant une infinité de valeurs simultanément.
Pour comprendre comment, considérons une autre capacité par
laquelle on pourrait enrichir une machine de Turing (ou un langage de
programmation idéalisé, ou tout autre modèle du genre). Cette fois,
je vais lui donner la capacité de détecter, pour une
fonction f (prenant des valeurs entières positives et
renvoyant des valeurs entières positives) si la fonction f
prend une valeur non-nulle ou non. Si je me place dans l'optique d'un
langage de programmation, je suppose donc que j'ai une fonction
« magique », non_zero(), qui, quand on lui fournit en
argument une fonction f, va considérer l'infinité de
valeurs f(0), f(1), f(2), etc., et si
l'une est différente de 0 va renvoyer vrai (1, disons), et sinon va
renvoyer faux (0, disons) ; si l'un des calculs
de f(i) ne termine pas (i.e., la valeur n'est
pas définie), alors non_zero(f) peut ne pas
terminer non plus (pour le moment, disons qu'on n'a aucune garantie) ;
en revanche, si tous sont définis, alors on obtient une réponse
(instantanément !), bien qu'il y ait une infinité de valeurs à
considérer. • Si la fonction f n'a pas elle-même le droit
de faire appel à non_zero(), alors cette fonction
magique non_zero() est tout à fait équivalente à
l'oracle halting_oracle() considéré plus haut : en effet,
dans un sens, si j'ai accès à halting_oracle(), je peux
programmer non_zero() (il suffit de considérer le
programme qui calcule
successivement f(0), f(1), f(2),
etc., et qui s'arrête dès qu'il calcule une valeur ≠0, et de demander
à halting_oracle() si ce programme s'arrête), et dans
l'autre sens, si j'ai accès à non_zero(), je peux
programmer halting_oracle() (il suffit, pour décider si
un programme s'arrête, de faire une
fonction f(n), qui exécute les n
premiers pas de ce programme et renvoie 1 si le programme est terminé
à ce moment-là, et 0 sinon).
Maintenant, une machine hyperarithmétique, c'est une machine qui
peut faire appel à cette fonction non_zero(), y compris
sur une fonction f qui peut elle-même faire appel à la
fonction non_zero(), i.e., y compris sur une fonction
hyperarithmétique. Autrement dit :
Une machine hyperarithmétique est une machine capable des
mêmes opérations qu'une machine de Turing ordinaire, mais aussi de
tester la nullité d'une infinité de valeurs d'une
fonction f elle-même calculée par une machine
hyperarithmétique. I.e., une fonction hyperarithmétique est
une fonction calculable par une machine, qui, en plus des capacités
d'une machine de Turing, a la capacité d'examiner simultanément une
infinité (f(0), f(1), f(2), etc.) de
valeurs calculées par une fonction
hyperarithmétique f, à condition que toutes ces valeurs
soient bien définies, et de décider si elles sont toutes nulles
ou s'il y en a une non-nulle (bien sûr, dans ce cas, on peut aussi lui
donner la capacité de trouver le premier indice pour
lequel f(i)≠0, ça ne changera rien). Si l'une
au moins des valeurs f(i) n'est pas définie
(i.e., si son calcul ne termine pas), alors une tentative pour en
examiner toute ses valeurs sera elle-même non-définie. Cette
définition est circulaire (une fonction peut très bien examiner une
infinité de ses propres valeurs), mais ce n'est pas problématique,
parce que contrairement à l'hypothétique
fonction halting_oracle_ultimate() plus haut, on évite le
paradoxe puisque la fonction peut ne pas être définie. Par exemple,
si j'essaye d'écrire une fonction f qui va examiner ses
propres valeurs et renvoyer 0 (pour toute entrée) si elles sont
non-nulles et vice versa, la fonction f sera tout
simplement non-définie partout (exactement comme, dans un langage de
programmation ordinaire, une fonction f dont la valeur
en i serait définie récursivement
par f(i) = f(i) + 1 ou
quelque chose comme ça : c'est juste une récursion qui ne termine
pas). • Pour donner une définition mathématiquement plus rigoureuse,
il faudrait dire : la notion de terminaison et de valeur des fonctions
hyperarithmétiques est la plus petite (au sens de
l'inclusion) telle que, (entre autres règles communes avec la
calculabilité au sens de Church-Turing ordinaire,)
si f(i) est défini pour tout i
alors non_zero(f) est défini et vaut 0 lorsque
chaque f(i) vaut 0, et 1 sinon.
Ajout/clarification : mon poussinet se plaint que
cette définition avec la plus petite notion
n'explique pas
vraiment les choses (et que la définition formelle qui suit
immédiatement n'aide pas vraiment). Voici une tentative pour
expliquer comment la circularité de la définition est brisée : (0) on
part d'un langage équivalent aux machines de Turing, et pour
l'instant non_zero(f) n'est jamais défini (la
fonction ne fonctionne pas) ; puis, si f(i) est
défini pour tout i (ce f est alors, forcément,
calculable au sens de Church-Turing), (1) on
définit non_zero(f) (valant 0 ou 1 selon
que f ne prend que des valeurs 0 ou pas) dans ce cas
précis, ce qui fait terminer plus de calculs ; et (2) on répète
l'opération : si f(i) est défini pour
tout i (pour la terminaison qui vient d'être un peu
étendue), alors on définit non_zero(f) pour
ces nouveaux cas ; et (3) on répète ; et (4) encore, et (5) encore, et
(6) encore… Et on doit parcourir
des ordinaux transfinis dans
l'opération (par exemple, parce que la
terminaison f(i) pourrait avoir été obtenue
après i étapes pour chaque i, ce qui donne un
sens à non_zero(f) seulement à l'étape
(ω)) : mais les ordinaux finissant toujours par gagner, la
définition finit par se stabiliser : ceci définit les
fonctions/machines hyperarithmétiques, et l'ordinal auquel la
définition se stabilise est le ω₁CK qui va
réapparaître occasionnellement dans ce qui suit.
Pour ceux qui
veulent vraiment une définition mathématique parfaitement rigoureuse,
en voici une possible. Je vais noter ‹m:a› pour
une représentation des couples d'entiers naturels par des entiers
naturels non nuls, disons ‹m:a› :=
2m·(2a+1), et
‹m1,…,mk› :=
‹m1:‹…:‹mk:0›…››
(il sera éventuellement utile de poser aussi
‹m1,…,mk:a›
:=
‹m1:‹…:‹mk:a›…››).
J'appelle alors ℰ le plus petit ensemble d'entiers
naturels qui vérifie les propriétés
suivantes : (o) ‹‹0›, a, a›
∈ ℰ pour
tout a ; (i) ‹‹1,q›, a, q›
∈ ℰ pour tous q
et a ; (ii) ‹‹2›,
‹x:a›, x+1› ∈ ℰ pour
tous x
et a ; (iii) ‹‹3,k›,
‹x1,…,xk:a›, xk›
∈ ℰ pour tous k≥1 et
tous x1,…,xk
et a ; (iv) ‹‹4›,
‹x,x,u,v›, u›
∈ ℰ pour tous x,u,v et
‹‹4›,
‹x,y,u,v›, v›
pour
tous x≠y,u,v ; (v) si
‹pi, a, vi›
∈ ℰ pour tout 1≤i≤k et ‹q,
‹v1,…,vk›, w›
∈ ℰ, alors
‹‹5,q,p1,…,pk›, a, w›
∈ ℰ ; (vi) si
‹p, a, v› ∈ ℰ alors ‹‹6›,
‹p:a›, v› ∈ ℰ ;
et (vii) si, pour un certain p on a, pour
tout i, que ‹p, ‹i›, 0›
∈ ℰ, alors ‹‹7›, ‹p›, 0› ∈ ℰ, tandis
que si (toujours pour un certain p) on a, pour
tout i, que ‹p,
‹i›, vi› ∈ ℰ
où vj≠0 pour au moins un j,
alors ‹‹7›, ‹p›,
1› ∈ ℰ. Cet ensemble ℰ est bien défini (car les
conditions sont positives, donc une intersection quelconque
d'ensembles d'entiers naturels qui les satisfait le satisfait encore,
et il en existe bien un plus petit). • L'interprétation de
‹p, a, v› ∈ ℰ est censée
être le programme p, quand on l'exécute sur la liste
d'arguments a (normalement,
‹x1,…,xk›),
termine et renvoie la valeur v
: le (i) exprime le fait
que les fonctions constantes sont calculables, le (ii) que la fonction
successeur l'est, le (iii) que les fonctions sélectionnant tel ou tel
argument (i.e., les projections) le sont, le (iv) permet de faire des
tests d'égalité, le (v) des compositions de fonctions, le (vi) des
invocations de programmes passés en argument (donc, in fine,
des boucles par invocation récursive), le (o), qui n'est probablement
pas nécessaire mais peut-être utile pour utiliser le (vi), assure
qu'on peut calculer la fonction ‹m:a› elle-même,
et le (vii) est justement la spécificité des fonctions
hyperarithmétiques (le non_zero() ci-dessus). • On peut
montrer que, pour p et a fixés, la propriété
‹p, a, v› ∈ ℰ ne peut être
vérifiée que pour au plus un v. On dira donc
alors qu'une fonction f:ℕ→ℕ (ou une fonction
partielle f:ℕ⇢ℕ) est hyperarithmétique lorsqu'il
existe p entier naturel tel que pour tout i on
ait équivalence entre ‹p, ‹i›, v›
et v=f(i) (ce qui sous-entend
que f(i) soit définie). •
Une remarque (♣) plus bas fera
remarquer qu'on peut, sans changer les fonctions hyperarithmétiques
(mais en changeant l'ensemble ℰ), modifier (vii)
en : (vii♣) si, pour un
certain p on a, pour tout i, que ‹p,
‹i›, 0› ∈ ℰ, alors ‹‹7›, ‹p›, 0›
∈ ℰ, tandis que si pour un certain p, un
certain i et un certain v on a que
‹p, ‹i›, v› ∈ ℰ
où v≠0, alors ‹‹7›, ‹p›, 1› ∈ ℰ. • Si
on supprime carrément le (vii), on doit obtenir une définition des
fonctions calculables au sens de Church-Turing (c'est, en quelque
sorte, une vérification du fait que je ne me suis pas
trompé[#4½] ; mais même si je
me suis trompé, il est certainement facile de corriger (i)–(vi) pour
obtenir les fonctions calculables au sens de Church-Turing, et l'ajout
de la condition (vii) devrait définir les fonctions
hyperarithmétiques).
Ces machines hyperarithmétiques sont extrêmement puissantes : comme
je l'ai expliqué plus haut, elles peuvent résoudre non seulement le
problème de l'arrêt pour les machines de Turing ordinaires, mais aussi
pour les machines de Turing disposant de cet oracle-là, et ainsi de
suite jusqu'à un nombre d'itérations d'oracles donné par
un ordinal ω₁CK
(appelé ordinal de Church-Kleene
) qui n'est pas évident à
décrire puisque justement il n'est pas manipulable par les machines de
Turing ni même par les machines hyperarithmétiques. En particulier,
elles peuvent décider tous les énoncés arithmétiques (que je définis
par exemple dans cette entrée). •
Par ailleurs, une machine hyperarithmétique peut manipuler des données
infinies (des suites d'entiers, c'est-à-dire, si on préfère, des
nombres réels) comme si elles étaient finies : pas « n'importe
quelle » suite entière / « n'importe quel » nombre réel, certes,
seulement justement ceux qui sont hyperarithmétiques, mais ça en fait
quand même beaucoup, et ce qui est intéressant, c'est qu'une machine
hyperarithmétique peut non seulement effectuer toutes les opérations
algébriques et transcendantes usuelles (et quantité d'autres choses)
sur les réels hyperarithmétiques, mais elle peut aussi tester leur
égalité de façon exacte (en comparaison, une machine de Turing
peut certes manipuler dans une certaine mesure
les réels
calculables, mais elle ne peut pas tester leur égalité exacte).
En fait, une machine hyperarithmétique peut faire plus que manipuler
des réels : elle peut manipuler — de façon exacte — toutes sortes
d'ensembles (qu'on peut appeler les ensembles hyperarithmétiques, et
qui sont en fait le niveau ω₁CK de
l'univers
constructible de Gödel) ; ces ensembles ne vérifient pas tous les
axiomes
de Zermelo-Fraenkel,
mais ils en vérifient un bout déjà intéressant (la théorie des
ensembles
de Kripke-Platek
avec infini).
Une question qu'on risque sans doute de me poser,
c'est si une machine hyperarithmétique dispose d'une mémoire infinie :
la réponse est surtout que la question n'a pas vraiment de sens (la
définition des machines hyperarithmétiques n'utilise pas vraiment le
paradigme « mémoire », et d'ailleurs
la définition rigoureuse
que j'ai proposée ne fait aucune mention de ce terme) ; mais
intuitivement, il faut s'imaginer que la réponse est plutôt : oui,
à condition que la donnée stockée sur cette mémoire infinie soit
hyperarithmétique
(c'est la condition permettant de manipuler une
donnée infinie : elle sera juste stockée sous la forme de la fonction
hyperarithmétique qui la calcule, mais pour beaucoup d'opérations on
peut faire comme si elle était stockée intégralement en mémoire et la
manipuler en bloc comme une donnée infinie).
Malgré toute cette puissance, les machines hyperarithmétiques ont leurs limitations. Elles ne peuvent pas, bien sûr, résoudre leur propre problème de l'arrêt (l'argument diagonal s'applique toujours). Mais, de façon peut-être plus surprenante, les ordinaux que peut « manipuler » (pour à peu près n'importe quel sens de ce mot) une machine hyperarithmétique sont exactement les mêmes qu'une machine de Turing ordinaire (dans les deux cas, ce sont précisément les ordinaux strictement inférieurs à l'ordinal ω₁CK de Church-Kleene — ceci est plus une définition de ce dernier qu'un théorème). Une machine hyperarithmétique n'est pas capable en général de décider si un graphe orienté dénombrable défini par une machine de Turing possède un chemin infini (même si ce graphe est supposé être un ordre total, i.e., la machine arithmétique n'est pas capable en général de décider si un ordre total calculable sur les entiers est un bon ordre). Et une machine hyperarithmétique n'est pas capable en genéral de décider si une suite hyperarithmétique (i.e., comme ci-dessus, f(0), f(1), f(2), etc., avec f hyperarithmétique) a une infinité de valeurs non-nulles (de fait, si on donne à la machine la capacité de répondre à cette question, on obtient un type de machine encore plus puissant, dont l'ordinal assez naturellement associé est le premier ordinal dit « récursivement inaccessible » au lieu de ω₁CK qui est plus petit).
Mais je veux aussi défendre l'idée que les machines
hyperarithmétiques sont quelque chose d'assez naturel : même si dans
le monde physique dans lequel nous vivons, la machine de Turing est le
modèle de calcul qui s'impose, mathématiquement, la machine
hyperarithmétique est peut-être bien aussi naturelle. Un argument
dans ce sens est qu'il y a, comme pour les fonctions calculables au
sens de Church-Turing, toutes sortes de définitions possibles des
fonctions hyperarithmétiques. J'en ai donné une ci-dessus (qui
s'inscrit dans le cadre de ce qui s'appelle formellement
la calculabilité [au sens de Kleene] en une fonctionnelle de
type 2
, la fonctionnelle de type 2
en question étant ici la
fonction E = non_zero, qui à une
fonction f:ℕ→ℕ
associe[#5] 0 ou 1 selon
que f est constamment égale à 0 ou non). Une autre
description possible est qu'il s'agit du niveau Δ¹₁ de
la hiérarchie
analytique, mais je ne veux pas expliquer ici ce que ça signifie
(par contre, c'est ce qu'on a le plus de chances de trouver dans un
livre un peu standard de calculabilité — ce qui est con, parce que
c'est une notion fort peu intuitive) ; l'équivalence avec la notion
que j'ai définie ci-dessus est un résultat de Kleene de 1959.
Encore une autre définition
consiste à considérer des machines (à registres, disons, mais il y a
encore toutes sortes de variantes possibles) qui, au lieu de manipuler
des entiers, manipulent des ordinaux, et qui peuvent effectuer des
boucles dont le temps va jusqu'à l'ordinal ω₁CK
(le plus petit ordinal qui n'est pas calculable : on remarquera qu'il
réapparaît régulièrement dans cette
entrée[#6]) : les fonctions sur
les entiers qui sont calculables par une telle machine ordinale sont
précisément les fonctions hyperarithmétiques. Enfin, on peut
accumuler les « sauts de Turing », c'est-à-dire les niveaux de
l'oracle de l'arrêt, jusqu'à ce qu'on observe quelque chose de nouveau
(là aussi, je préfère rester vague), et ça se produit précisément
quand on atteint le niveau ω₁CK et les fonctions
hyperarithmétiques. En quelque sorte, les machines hyperarithmétiques
sont les plus simples, ou les moins puissantes, du monde de la
calculabilité supérieure. Enfin, comme je le remarque ci-dessus, on
peut les définir comme l'extension la plus simple de la machine de
Turing qui ait la capacité à comparer deux réels qu'elles-mêmes
calculent, ce qui est certainement une condition naturelle.
Il y a encore un point
un peu technique que je veux signaler, parce que je pense qu'il joue
pour expliquer que les machines hyperarithmétiques sont quelque chose
de naturel. J'ai défini ci-dessus les machines hyperarithmétiques
comme des machines analogues à celles de Turing mais auxquelles on
ajoute la capacité (l'appel à non_zero(f))
d'examiner simultanément une infinité
(f(0), f(1), f(2), etc.) de valeurs
calculées par une fonction hyperarithmétique f, à
condition que toutes ces valeurs soient bien définies, et de
décider si elles sont toutes nulles ou s'il y en a une qui est
non-nulle. Si ne serait-ce qu'une seule
des f(i) est non-définie, alors l'examen de
toutes les valeurs échoue, i.e., le calcul ne termine pas et le
résultat n'est pas défini. Mais il est possible de rendre cette
contrainte moins rigoureuse et d'obtenir au final exactement la même
notion de machine hyperarithmétique. Par exemple, il est facile de
voir que cela ne change rien au final si on décide que les
valeurs f(0), f(1), f(2), etc.,
seront examinées dans cet ordre, et que l'examen s'arrêtera
si f(i) est définie et non-nulle et que
les f(j) pour j<i sont
définies (auquel cas non_zero(f) renvoie
1=vrai), ou bien si tous les f(i) sont définies
et nulles (auquel cas non_zero(f) renvoie
0=faux). Pour s'en convaincre, il suffit, avant l'opération (i.e.,
avant le calcul de non_zero(f)) de
remplacer f par une fonction g telle
que g(i) calcule successivement
les f(j) et s'arrête si elle trouve une valeur
non-nulle, en renvoyant cette valeur, ou bien si j atteint
la valeur i, auquel cas elle renvoie 0. • Ce qui est
nettement plus subtil, c'est (♣) qu'on ne change rien non plus à la
notion de machine hyperarithmétique si on suppose que l'examen des
valeurs f(0), f(1), f(2), etc.,
termine dès qu'il y a une quelconque valeur qui est définie
et non-nulle (auquel cas le résultat sera 1=vrai), ou que toutes les
valeurs sont définies et nulles (auquel cas le résultat sera 0=faux).
Si on a l'habitude des machines de Turing, on aurait envie de
dire oui, ce n'est pas surprenant, il suffit d'écrire une
fonction g qui lance l'exécution de f de
façon parallèle
déployée
, mais en fait ce n'est pas si simple, parce que la
notion d'un pas d'exécution d'une machine hyperarithmétique n'est pas
du tout évidente (vu que ce pas pourrait faire lui-même appel à
l'examen d'une infinité de valeurs d'une autre fonction, etc.) !
Pourtant, le résultat est correct, mais il fait appel à
un théorème de sélection non-trivial, qui est vrai aussi bien
pour les machines de Turing (auquel cas il est facile) que pour les
machines hyperarithmétiques (où il est nettement moins facile) : à
savoir, il est possible d'écrire un programme qui prend en entrée une
fonction f (d'un paramètre entier i) et qui,
si f(i) termine pour au moins une valeur
de i, termine lui-même en renvoyant une telle valeur
de i. Dans le cas hyperarithmétique (défini tel que je
l'ai fait ci-dessus), ce résultat s'appelle le théorème de
sélection de Gandy (ceux qui veulent voir une preuve peuvent la
trouver en VI.4.1
du livre
de Hinman de 1978, Recursion-Theoretic
Hierarchies, ou dans un contexte un petit peu différent,
X.4.1
du livre
de Sacks de 1990, Higher Recursion
Theory).
Voici encore une façon de présenter les machines
hyperarithmétiques : ce sont des machines qui ont la capacité de
calculer des conjonctions (=et logiques), ou de façon
équivalente des disjonctions (=ou logiques), infinies,
à condition que les termes de la conjonction/disjonction soient
eux-mêmes calculés par une machine hyperarithmétique. (Le paragraphe
précédent, en petits caractères, explique en substance (♣) que cela ne
change rien si qu'on suppose ou non que la machine évalue ces
conjonctions et disjonctions infinies de façon minimale, c'est-à-dire
qu'une disjonction renvoie vrai dès qu'un des termes est vrai, même si
les autres ne sont pas définis.) Ceci donne aux machines
hyperarithmétiques un lien fort avec certaines logiques infinitaires,
et notamment avec
le théorème
de compacité de Barwise (dont un énoncé très très très grossier
serait que si on remplace fini
par hyperarithmétique
,
une des propriétés essentielles de la logique usuelle reste
valable).
⁂ J'espère avoir convaincu que les machines hyperarithmétiques sont
une notion relativement naturelle. Mais je veux aussi souligner qu'il
est à mon avis intéressant de la comprendre parce que la notion de
fonctions calculables au sens de Church-Turing est encadrée par la
notion (plus restreinte) de fonctions primitives récursives et la
notion (plus générale) de fonctions hyperarithmétiques que je viens de
définir. Or ces deux bornes présentent une certaine similarité : la
classe des fonctions primitives récursives fait une sorte de pont
entre les classes de complexité et la théorie de la calculabilité
(c'est une classe de complexité, parce qu'une fonction est primitive
récursive ssi elle est calculable en temps ou en espace donné par une
fonction primitive récursive ; bien sûr, en tant que telle, c'est une
classe énorme ; mais c'est aussi le début de la calculabilité, parce
que cette classe se définit syntaxiquement et sans avoir besoin de
parler de complexité) ; et la classe des fonctions hyperarithmétiques
fait une sorte de pont entre la théorie de la calculabilité et la
logique (c'est une classe de calculabilité, manifestement, mais c'est
le début de la calculabilité supérieure qui s'inscrit plus
naturellement dans la vision de l'univers constructible de Gödel). Et
la similarité va plus loin : on peut partir des fonctions primitives
récursives et créer des fonctions de plus en plus puissantes par
diagonalisation (il n'existe pas de machine universelle pour les
fonctions primitives récursives : si on en ajoute un, on crée une
classe plus puissante, et on peut recommencer l'opération de façon
transfinie ; dans cette entrée
j'appelais ça le saut de Kleene
, ce qui est un très mauvais
terme pour plein de raisons — j'aurais dû dire saut
d'Ackermann
—, mais en tout cas le concept est important), ceci
fabrique ce qu'on appelle les hiérarchies sous-récursives ; tandis
qu'on peut partir des fonctions calculables au sens de Church-Turing
et créer des fonctions de plus en plus puissantes par une autre forme
de diagonalisation (ajouter le problème de l'arrêt de façon répétée et
transfinie), ce qui fabrique la hiérarchie hyperarithmétique. Il
existe certes des différences importantes entre ces deux
constructions[#7], mais la
similarité est assez significative pour mériter l'attention. Je pense
qu'on comprend bien mieux la notion de fonction calculable au sens de
Church-Turing en ayant ces autres notions présentes à l'esprit.
[#] Pour commencer, le
terme machine hyperarithmétique
n'est pas vraiment standard :
celui de fonction hyperarithmétique
l'est, mais pour trouver
une description explicite d'une machine qui calcule ces fonctions, il
faut fouiller dans des livres
(parfois poussiéreux) de
calculabilité supérieure. La description des fonctions
hyperarithmétiques qu'on trouvera dans la plupart des livres sur la
calculabilité est de les présenter comme le niveau Δ¹₁ de
la hiérarchie
analytique (lightface) : mais franchement, quand on décrit les
choses comme ça, je pense qu'il est absolument impossible pour un
débutant de s'en faire une intuition, encore moins de comprendre
pourquoi les niveaux Δ¹₁ et Δ¹₂ sont beaucoup plus importants que tout
ce qui vient après (ni pourquoi ce sont les ensembles Π¹₁, et pas les
Σ¹₁, qui se comportent un peu comme les ensembles récursivement
énumérables =Σ⁰₁).
[#2] Ceci dit, je
voudrais bien lancer le défi de définir de la façon la plus
compréhensible / intuitive, et néanmoins concise, cette notion de
calculabilité (imaginer, pour fixer les idées, qu'on s'adresse à
quelqu'un qui est scientifique et sait se servir d'un ordinateur,
peut-être même programmer, mais n'est pas vraiment mathématicien ni
informaticien : comment expliquer le concept efficacement ?). Je
demande notamment, parce qu'à Télécom ParisMachinBiduleTech, je
participe à un enseignement (appelé théorie des langages
) où le
concept doit être rapidement introduit, et pour l'instant nous n'avons
pas vraiment trouvé de façon de faire comprendre aux élèves qu'il
s'agit d'une notion que, fondamentalement, ils connaissent
déjà parce que tout ce pour quoi ils peuvent imaginer un
algorithme est ipso facto calculable. (Par exemple, si on leur
demande si l'ensemble des mots (=chaînes de caractères) qui sont des
palindromes est calculable, il y en a bien la moitié qui ne savent pas
répondre ou qui répondent au pif, au lieu d'écrire oui, bien sûr
que ce n'est pas difficile d'écrire un programme qui teste si une
chaîne de caractères est la même à l'envers !
.) La difficulté, à
la base, c'est que si on donne une définition informelle, les élèves
ont l'impression que c'est de l'agitage de main et qu'on ne peut rien
prouver dessus, et si on donne une définition formelle, ils n'y voient
rien : on voit bien, à la lecture de la présente entrée, que je me
débats avec cette difficulté.
[#3] Bon, en toute honnêteté, si je dois donner rapidement une définition formelle des fonctions calculables, je crois que je le ferai par une approche proche de ce que je fais ici même pour les fonctions hyperarithmétiques, et il faut admettre que c'est illisible dans le style de Kleene.
[#4] En fait, il y a des physiciens qui spéculent sur le fait que la thèse de Church-Turing « physique » serait fausse, et que la relativité générale permettrait, en fait, d'effectuer certains « hyper-calculs » : voir ce exposé de Mark Hogarth pour des explications à ce sujet. Je pense en fait que la notion de fonction hyperarithmétique serait justement adaptée à son propos (je devrais peut-être le lui signaler).
[#4½] Par acquit de
conscience, j'ai voulu vérifier que j'arrivais au moins à
« programmer » la fonction d'addition dans l'espèce de langage de
programmation que je définis avec les clauses (i)–(vi) (le (o) n'est
sans doute pas utile ; il aurait été nécessaire si j'avais écrit le
(vi) sous la forme (vi′) si
‹p, a, v› alors ‹‹6›,
‹p,a›, v› ∈ ℰ — avec ‘,’
au lieu de ‘:’). Et il faut admettre que c'était plus dur que ce que
je pensais (ça ressemble beaucoup à programmer
en Unlambda, et ce n'est
d'ailleurs pas complètement un hasard). Je suis arrivé à p
:= ‹5, ‹5, ‹6›, ‹5, ‹4›, ‹3, 4›, ‹3, 3›, ‹1, ‹3, 2››, ‹1, ‹5, ‹2›, ‹5,
‹6›, ‹3, 1›, ‹3, 1›, ‹3, 2›, ‹3, 3›, ‹5, ‹2›, ‹3, 4››››››, ‹3, 1›, ‹3,
2›, ‹3, 3›, ‹3, 4››, ‹1, ‹5, ‹6›, ‹5, ‹4›, ‹3, 4›, ‹3, 3›, ‹1, ‹3,
2››, ‹1, ‹5, ‹2›, ‹5, ‹6›, ‹3, 1›, ‹3, 1›, ‹3, 2›, ‹3, 3›, ‹5, ‹2›,
‹3, 4››››››, ‹3, 1›, ‹3, 2›, ‹3, 3›, ‹3, 4›››, ‹3, 1›, ‹3, 2›, ‹1,
0››, pour lequel on a ‹p,
‹x,y›, x+y› ∈ ℰ
pour tous x,y∈ℕ. Pour ceux qui voudraient le
vérifier, voici un programme Scheme qui interprète ce langage
bizarre : (define (ev prgm args) (if (not (list? prgm)) (error
"prgm is not a list")) (let ((inst (car prgm))) (case inst ((0) args)
((1) (cadr prgm)) ((2) (+ (car args) 1)) ((3) (list-ref args (- (cadr
prgm) 1))) ((4) (if (= (car args) (cadr args)) (caddr args) (cadddr
args))) ((5) (let ((vals (map (lambda (p) (ev p args)) (cddr prgm))))
(ev (cadr prgm) vals))) ((6) (ev (car args) (cdr args))) (else (error
"unknown instruction"))))) (pour donner un exemple, si on
fait (define plusprg '(5 (5 (6) (5 (4) (3 4) (3 3) (1 (3 2)) (1
(5 (2) (5 (6) (3 1) (3 1) (3 2) (3 3) (5 (2) (3 4)))))) (3 1) (3 2) (3
3) (3 4)) (1 (5 (6) (5 (4) (3 4) (3 3) (1 (3 2)) (1 (5 (2) (5 (6) (3
1) (3 1) (3 2) (3 3) (5 (2) (3 4)))))) (3 1) (3 2) (3 3) (3 4))) (3 1)
(3 2) (1 0))), alors (ev plusprg '(30 12))
renvoie 42) ; et pour ceux qui voudraient essayer de
comprendre comment ce programme p=plusprg est
foutu, il est obtenu en faisant une sorte de traduction de la fonction
Scheme suivante : (lambda (x y) ((lambda (f x y z) ((if (= z y)
(lambda (f x y z) x) (lambda (f x y z) (+ (f f x y (+ z 1)) 1))) f x y
z)) (lambda (f x y z) ((if (= z y) (lambda (f x y z) x) (lambda (f x y
z) (+ (f f x y (+ z 1)) 1))) f x y z)) x y 0)) (dont on peut
vérifier qu'elle calcule bien la somme de deux entiers naturels passés
en argument, sans utiliser autre chose que des λ, des applications, la
fonction successeur, et un if qui a même le droit
d'évaluer toutes ses branches complètement). On remarquera au passage
que j'ai codé les listes d'entiers à partir des paires, à savoir
‹m1,…,mk› :=
‹m1:‹…:‹mk:0›…››,
sur l'inspiration de Lisp/Scheme. Bref, ayant fait cet exercice, je
suis raisonnablement convaincu que je capture toutes les fonctions
générales récursives avec les clauses (i)–(vi), mais je ne prétends
pas forcément que c'était la façon la plus intelligente de s'y prendre
(même avec la contrainte supplémentaire de se généraliser facilement
aux fonctions hyperarithmétiques par l'ajout d'une clause
supplémentaire).
[#5] Je crois qu'en fait le plus standard est de décider que E(f) vaut 0 si f:ℕ→ℕ prend au moins une fois la valeur 0, et 1 si elle est constamment non-nulle. Ceci n'a, évidemment, aucune importance fondamentale.
[#6] On pourrait du coup objecter que ma notion de fonction/machine hyperarithmétique n'est pas si naturelle que ça, puisqu'elle dépend de cet ordinal ω₁CK. (Et il est vrai que d'autres ordinaux sont naturellement associés à d'autres notions de calculabilité elles aussi plus ou moins naturelles : je mentionnais par exemple le plus petit ordinal « récursivement inaccessible », qui est associé aux machines qui ont la capacité de décider si une suite f(0), f(1), f(2), etc. calculée par elles-mêmes, comporte une infinité de valeurs non-nulles ; beaucoup de résultats que je mentionne se transposent à de telles machines — mais pas tous, parce que par exemple cela change alors des choses de relaxer la contrainte que tous les f(i) soient définis : le point (♣) du corps du texte ne s'applique pas ici tel quel.) Néanmoins, le choix de ω₁CK est un choix particulièrement important et naturel : c'est le plus petit ordinal qui n'est pas manipulable par une machine de Turing ordinaire (au sens où aucun bon ordre sur les entiers calculable par une machine de Turing n'a pour type ω₁CK, alors qu'ils peuvent avoir pour type tous les ordinaux plus petits) ; et après l'ordinal ω des entiers naturels, c'est le plus petit pour lequel on ait une notion de calculabilité qui se comporte vraiment bien.
[#7] Notamment parce que les hiérarchies sous-récursives, i.e., la diagonalisation itérée à partir des fonctions primitives récursives, se construisent non pas à partir d'ordinaux mais à partir de notations ordinales, et il est en gros impossible d'atteindre toutes les fonctions calculables de la sorte ; alors que la hiérarchie hyperarithmétique se construit vraiment à partir d'ordinaux (elle ne dépend pas de la notation choisie pour un ordinal donné) et elle atteint toutes les fonctions hyperarithmétiques.