David Madore's WebLog: Qu'est-ce qu'une machine hyperarithmétique ?

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

Entry #2337 [older|newer] / Entrée #2337 [précédente|suivante]:

(lundi)

Qu'est-ce qu'une machine hyperarithmétique ?

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 nk 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 nk 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 PNP (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 xy,u,v ; (v) si ‹pi, a, vi› ∈ pour tout 1≤ik 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› ∈ vi≠0, 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› ∈ 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.

↑Entry #2337 [older|newer] / ↑Entrée #2337 [précédente|suivante]

Recent entries / Entrées récentesIndex of all entries / Index de toutes les entrées