David Madore's WebLog: Un peu de programmation transfinie

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

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

(vendredi)

Un peu de programmation transfinie

Ça fait très longtemps que j'ai envie d'écrire cette entrée, parce que je trouve le sujet extrêmement rigolo : en gros, ce dont je veux parler, c'est comment définir et programmer un ordinateur transfini ? (comment concevoir un langage de programmation considérablement plus puissant qu'une machine de Turing parce qu'il est capable de manipuler directement des — certains — ordinaux ?). Techniquement, ce dont je veux parler ici, c'est de la théorie de la α-récursion (une branche de la calculabilité supérieure qui a fleuri dans les années '70 et qui semble un peu moribonde depuis) ; sauf que la α-récursion n'est jamais présentée comme je le fais ici, c'est-à-dire en décrivant vraiment un langage assez précis dans lequel on peut écrire des programmes pour certains ordinateurs transfinis. Ces ordinateurs ont le malheur de ne pas pouvoir exister dans notre Univers (encore que, si on croit certaines théories complètement fumeuses que j'avais imaginées… ?) ; mais même s'ils n'existent pas, je pense que le fait d'écrire les choses dans un style « informatique » aide à rendre la théorie mathématique plus palpable et plus compréhensible (en tout cas, c'est comme ça que, personnellement, j'aime m'en faire une intuition).

Bref, ce que je voudrais, c'est que cette entrée puisse plaire à la fois à ceux qui aiment la programmation et à ceux qui aiment les ordinaux ; ce que je crains, c'est qu'en fait elle déplaise à la fois à ceux qui n'aiment pas la programmation et à ceux qui n'aiment pas les ordinaux — ce qui est logiquement différent. On verra bien.

Il faut que je précise que tout ce que je raconte est un territoire relativement mal couvert par la littérature mathématique (il y a certainement des gens qui trouveraient tout ça complètement évident, mais je n'en fais pas partie, et comme je le disais, je soupçonne que la plupart étaient surtout actifs vers '70 et sont maintenant un peu âgés ou sont passés à autre chose), et jamais de la manière dont je le fais (comme un vrai langage de programmation : il y a des gens qui ont « redécouvert » des domaines proches comme avec les machines de Turing infinies ou les machines ordinales de Koepke, mais c'est un peu différent). Du coup, il faut prendre tout ce que je raconte avec un grain de sel : je n'ai pas vérifié chaque affirmation avec le soin que j'aurais fait si j'étais en train d'écrire un article à publier dans un journal de recherche.

Une autre remarque : cette entrée contient un certain nombre de digressions, notamment parce que je pars dans plusieurs directions un peu orthogonales. Je n'ai pas voulu les mettre en petits caractères comme je le fais souvent, pour ne pas préjuger de ce qui est important et ce qui ne l'est pas, et je n'ai pas eu le courage de tracer un leitfaden, mais tout ne dépend pas de tout : donc, si on trouve un passage particulièrement obscur ou inintéressant, on peut raisonnablement espérer(!) qu'il ne soit pas vraiment important pour la suite.

*

Pour faire une sorte de plan ce dont je veux parler, je vais décrire un langage de programmation assez simple (dont la syntaxe sera imitée de celle du C/JavaScript) et différentes variantes autour de ce langage. Plus exactement, je vais définir quatre langages : un langage (0) « de base » et deux extensions qu'on peut appliquer à ce langage (les extensions « forward » et « uloop », qui seront définies après), de sorte qu'à côté du langage (0) de base, il y aura le langage (1) avec extension « forward », le langage (2) avec extension « uloop », et le langage (3) avec les deux extensions à la fois ; tout ça peut encore être multiplié par deux si j'autorise les tableaux dans le langage, ce qui, finalement, ne changera rien à son pouvoir d'expression, et c'est peut-être surprenant.

Chacun de ces langages pourra servir dans le « cas fini » (le langage manipule des entiers naturels, et chacun des langages (0)–(3) peut être implémenté sur un vrai ordinateur et servir de vrai langage de programmation) ou dans le « cas transfini » (le langage manipule des ordinaux). J'expliquerai plus précisément en quoi consiste ce cas transfini, mais je veux insister dès à présent sur le fait que les langages de programmation (0)–(3) seront exactement les mêmes dans ce cas transfini que dans le cas fini (plus exactement, leur syntaxe sera exactement la même ; la sémantique pour les langages (0)&(1) sera prolongée, tandis que pour les langages (2)&(3) elle sera raffinée et dépendra d'un « ordinal de boucle » λ).

Je commence par le cas fini. Je vais donc décrire un langage de programmation tout ce qu'il y a de plus « normal » (enfin, quatre voire huit, parce qu'il y a des variantes). Certaines de ses caractéristiques seront un petit peu bizarres parce qu'il est pensé dans l'optique de pouvoir s'étendre au cas transfini et parce que toute considération d'efficacité est complètement ignorée, mais à part ça ce langage pourrait tout à fait être implémenté sur un ordinateur réel. (Par ailleurs, quitte à spoiler un peu, je peux révéler d'ores et déjà que mon langage (0) ne sera pas Turing-complet tandis que les langages (1) à (3) le seront.)

Comme annoncé ci-dessus, je vais définir un langage de base (qui ne permet pas de boucles infinies et calcule exactement, comme je le dirai plus loin, les fonctions primitives récursives), et deux extensions orthogonales possibles à ce langage (l'extension « forward » et l'extension « uloop », qui peuvent être combinées, ce qui me donnera donc quatre langages de programmation). Plus tard, sans rien changer à la syntaxe du langage, je vais transformer mon langage fini (et tout à fait implémentable sur un vrai ordinateur) en langage(s) transfini(s) et je vais tenter d'expliquer un peu les mathématiques de la chose.

Commençons par décrire mon langage de base (dans le cas fini, mais le cas transfini ne changera rien à la syntaxe). La syntaxe est fortement imitée de celle du C, mais nettement plus simple par de nombreux aspects.

Mon langage sait manipuler un unique type : dans la version finie que je décris pour commencer, il s'agira du type entier naturel (dans la version transfinie, ils deviendront des ordinaux) ; mais déjà dans cette version de base du langage, ces entiers naturels peuvent être arbitrairement grands (c'est donc déjà un langage idéalisé, si on veut) : on peut donc représenter, par exemple, un couple d'entiers ou une suite finie d'entiers par un unique entier (et le langage fournira un codage pour le faire), même si c'est quelque chose que généralement personne ne veut sérieusement faire dans un langage réel.

Les opérations de base du langage sont assez standard. Commençons par les opérations arithmétiques : x+y calcule la somme des expressions x et y, et x*y calcule leur produit (techniquement, on n'en a pas besoin, mais je ne vais pas être sadique au point de ne pas permettre ça). Il y a aussi les comparisons : x<y retourne 1 (à comprendre comme « vrai ») lorsque x est strictement plus petit que y et 0 (« faux ») sinon, et les autres comparaisons habituelles du C, à savoir x==y qui teste l'égalité de x avec y, x!=y qui teste le contraire, x<=y qui teste si xy, et bien sûr x>y et x>=y qui font ce qu'on imagine. Il y a les opérateurs booléens usuels : !u (« non logique ») renvoie 1 si u est nul et 0 sinon ; u&&v (« et logique ») évalue u et, s'il ne vaut pas 0, évalue v et renvoie sa valeur, sinon 0 (sans évaluer v) ; et u||v (« ou logique ») évalue u et, s'il vaut 0, évalue v et renvoie sa valeur, sinon celle de u (sans évaluer v) ; et plus généralement u?x:y qui évalue u et s'il ne vaut pas 0 évalue et renvoie x tandis que s'il vaut 0 il évalue et renvoie y. (Techniquement, j'ai défini ici la sémantique du Perl ou JavaScript, pas celle du C. Franchement, ça n'a aucune importance pour ce que je veux faire.) Je suppose que je peux aussi mettre l'opérateur « virgule » x,y dans le tas, qui évalue mais ignore x, puis évalue et renvoie y, mais ça ne sert pas à grand-chose.

Pour ce qui est des affectations, l'expression a=x a l'effet de bord d'affecter à la variable a (je dirai plus loin comment déclarer des varibles) la valeur de l'expression x, et renvoie cette valeur (ce qui permet d'écrire légalement a=b=x pour donner à la fois à a et b la même valeur x) ; tant qu'à faire, je peux aussi autoriser a+=x qui affecte à a la valeur de a+x et a*=x qui affecte à a la valeur de a*x (toutes ces expressions ont pour valeur la valeur finale de a, mais c'est franchement de mauvais goût de s'en servir) ; je ne vais pas autoriser le ++ du C parce qu'il s'avérerait source de confusion. Il n'y a pas de pointeurs, de tableaux, ou quoi que ce soit de ce genre. Les valeurs-gauche (c'est-à-dire ce qui peut venir à gauche d'une affectation, a dans mes exemples) sont uniquement les variables.

Je ne vais pas mettre de soustraction dans le langage. Je peux mettre les opérateurs bit-à-bit & et |, ou les décalages (a<<x renvoie 2x·a et a>>x renvoie l'unique b tel que a = 2x·b + r pour un certain 0≤r<2x) mais ils ne seront pas terriblement utiles.

En revanche, je vais mettre dans le langage une construction pour faire des paires : x#y sera un codage des paires d'entiers naturels par des entiers naturels, et précisément ce sera la suivante : y²+x si x<y et x²+x+y si yx. Réciproquement, z.p et z.q (avec littéralement les lettres p et q — ce ne sont pas des identificateurs) renvoient les valeurs de x et y réciproquement pour lesquelles z vaut l'expression que je viens de dire (par exemple, 42.p renvoie 6 et 42.q renvoie 0 car 6#0 renvoie 42). Dès lors qu'on a moyen de faire des couples, on peut s'en servir pour bricoler des listes ou autres structures plus complexes : c'est pénible, mais je préfère ne pas compliquer outre mesure le langage (je décrirai tout de même, ci-dessous, une extension autorisant les tableaux). Pour faire une convention, on va dire que # est associatif à droite (x#y#z signifie x#(y#z)).

Venons-en aux instructions (statements) du langage.

Un bloc d'instructions peut servir à la place d'une instruction : les instructions d'un bloc sont terminées par des points-virgules et entourées par des accolades, selon le modèle { s1; s2; s3; } (valable pour un nombre quelconque, éventuellement nul, d'instructions).

La construction if (e) s exécute s si e est vrai (c'est-à-dire non nul) ; la construction if (e) s1; else s2 fait ce qu'on imagine.

Une nouvelle variable est définie dans un bloc par local a (terminé par un point-virgule) ; on peut en définir plusieurs par quelque chose comme local a1, a2, a3 ; les variables sont garanties initialisées à 0 : on peut aussi initialiser et donner une valeur initiale avec quelque chose comme local a=x (où x est une expression). La portée de la variable est tout ce qui suit sa déclaration jusqu'à la fin du bloc.

Jusque là, rien d'original. Les boucles, en revanche, seront plus originales : la construction de boucle de mon langage s'écrit loop (a<x) ss est une instruction (généralement un bloc), a une variable dite variable de contrôle. (On autorise aussi la variante loop (local a<x) s qui crée une nouvelle variable a avec portée sur toute la boucle.) L'expression x est évaluée au départ, et la variable a va être affectée à toutes les valeurs 0, 1, 2, et ainsi de suite jusqu'à x exclue avant l'exécution de s. Modifier la valeur de a dans le corps de la boucle n'a pas d'incidence sur le déroulement de celle-ci, qui s'exécute donc exactement x fois (au sens : au plus la valeur de l'évaluation préliminaire de x), ou éventuellement moins si on utilise l'instruction spéciale break pour sortir prématurément d'une boucle (on peut sortir de plusieurs boucles imbriquées avec break nn est un entier naturel non nul explicite), ou bien un return prématuré (cf. ci-dessous). Si la variable a est encore visible après la boucle (c'est-à-dire si on a utilisé la forme loop (a<x) s), alors sa valeur à la fin de la boucle est la valeur (initialement calculée) de x s'il n'y a pas eu de fin prématurée de la boucle (par exemple, après local a; loop (a<42) { a=1; } la valeur de a est 42, pas 1).

Si on n'a pas besoin de variable de boucle, on peut écrire loop (<x) s pour boucle x fois (le signe <, en revanche, est nécessaire pour éviter une ambiguïté syntaxique).

Il n'y a pas de boucle while ni de for ou d'autre variante que celle que je viens de décrire.

Le langage permet naturellement de définir des fonctions : function f() {} définit une fonction dont les noms des arguments sont entre parenthèses (séparés par des virgules) et le corps le bloc d'instructions qui suit. La valeur de retour d'une fonction est 0 sauf en cas de return explicite auquel cas c'est la valeur en question. Par exemple : function minus(x,z) { loop (local y<z+1) { if (x+y==z) return y; } } calcule l'unique yx s'il existe tel que x+y=z, et sinon renvoie 0.

Je ne définis pas d'autre notion de « programme » que les fonctions du langage : je pourrais dire que la fonction principale s'appelle main si ça m'amuse, mais peu importe, toujours est-il que quand je parle d'un « programme », il faut juste comprendre une fonction du langage (qui pourrait en appeler d'autres).

Je crois qu'autoriser des fonctions locales (c'est-à-dire à l'intérieur du corps d'une autre fonction, et pouvant faire référence aux variables locales actuellement en portée) ne compliquera pas les choses : je vais donc le faire, quitte à apporter une correction ici s'il s'avère qu'il y a une complication que je n'avais pas vue. La syntaxe pour les fonctions locales sera celle qu'on imagine : je peux écrire function f() {} au sein d'un bloc de code, auquel cas la fonction f sera utilisable jusqu'à la fin du bloc où elle est définie.

Les appels récursifs ne sont pas autorisés dans la version de base du langage que je décris pour l'instant. Autrement dit, on ne peut appeler la fonction f qu'après la fin du bloc définissant f. (Il n'y a pas non plus de fonction variadique, c'est-à-dire au nombre d'arguments variable.)

Le langage tel que je viens de le définir est tout à fait limité : il ne permet pas de faire de boucle infinie (du moins, si je ne me suis pas planté quelque part, ce qui est toujours assez probable vue la tendance de la Turing-complétude à se glisser partout). En effet, chaque bloc de code termine forcément, les boucles loop ayant un nombre d'itérations borné a priori, et on prouve la terminaison de l'exécution des fonctions dans l'ordre dans lequel on les définit. Autrement dit : tout programme (syntaxiquement bien-formé) dans le langage que j'ai décrit termine toujours en temps fini.

Ce langage permet uniquement d'exprimer les fonctions primitives récursives (voir aussi ici) : si vous ne savez pas ce que c'est qu'une fonction primitive récursive, vous pouvez prendre ça comme une définition. Moralement, l'idée est qu'on écrit du code dans lequel chaque boucle doit spécifier, à l'avance, le nombre (maximal) d'itérations de la boucle. Mon langage est très proche du langage BlooP de Hofstadter (j'ai juste utilisé une syntaxe imitée du C et un modèle mémoire un peu plus proche d'un langage réel).

En un certain sens, ce langage est extrêmement limité : il n'est pas possible, par exemple, d'écrire dans ce langage un interpréteur pour le langage lui-même (je vais y revenir dans un instant), ni d'y programmer la fonction d'Ackermann. En revanche, il n'est pas si limité que ça quand on se rend compte que tous les algorithmes pour lesquels on a une analyse de complexité « usuelle » (qu'ils soit, par exemple, polynomiaux, NP, EXPTIME ou même ELEMENTARY) sont programmables, et « essentiellement tous » les algorithmes dont on sait qu'ils terminent toujours en temps fini (il est extraordinairement rare de tomber, sans le faire exprès, sur une fonction calculable (totale) qui ne soit pas primitive récursive).

La raison pour laquelle il n'est pas possible d'écrire un interpréteur du langage (0) dans le langage (0) est la suivante : si on pouvait faire cela, on pourrait écrire un programme p qui appelle l'interpréteur sur p lui-même. (Rappelons qu'il est tout à fait possible de faire comme si on disposait du code source du programme p dans le programme lui-même : c'est l'« astuce de Quine » qui permet de faire des programmes s'écrivant eux-mêmes, que j'explique en détail sur cette page, et qui dépend en fait uniquement du théorème s-m-n, qui est valable sans subtilité particulière pour le langage que j'ai décrit.) Or ceci générerait une boucle infinie, ce qui n'est pas possible dans le langage. Mais je vais dire dans un instant qu'on peut faire presque aussi bien qu'un interpréteur, on peut faire un interpréteur « à essence ».

*

Maintenant que j'ai ce langage de base, je vais lui définir deux extensions orthogonales :

L'une ou l'autre de ces extensions, ou à plus forte raison les deux à la fois, donne au langage la force d'une machine de Turing. J'ai donc quatre langages à ce stade : (0) le langage de base, (1) le langage avec extension forward, (2) le langage avec extension uloop, et (3) le langage avec les deux extensions. Il se trouve que les trois langages (1), (2) et (3) sont équivalents.

*

Avant d'aller plus loin, il est peut-être utile que j'évoque le théorème de la forme normale de Kleene : si vous lisez cet article Wikipédia, vous n'y comprendrez rien du tout (à moins de savoir déjà de quoi il s'agit), alors je vais essayer de le raconter de façon plus intuitive.

J'ai dit qu'il n'était pas possible, dans le langage de base (0), d'écrire un interpréteur pour le langage (0) lui-même ; c'est-à-dire qu'il n'existe pas de fonction « universelle » qui prend deux arguments, [le code d']une fonction e à exécuter et un argument z à lui passer, et qui se comporte comme l'exécution de e(z) ; ce n'est pas non plus possible, à plus forte raison, d'écrire dans le langage (0) un interpréteur pour les langages étendus (1), (2) et (3).

En revanche, ce qui est possible dans le langage (0), c'est d'écrire ce que j'ai envie d'appeler un « interpréteur à essence ». Il s'agit d'une fonction (primitive récursive, donc) qui prend trois arguments : [le code d']une fonction e à exécuter, un argument z à lui passer, et une certaine « quantité d'essence » t qui donne à l'interpréteur un temps imparti pour l'exécution de e(z) avant d'échouer : en gros, l'interpréteur lancer l'exécution de e(z) pour t étapes d'exécution (ce t va donc borner la boucle principale de l'interpréteur), et si l'exécution termine en temps imparti (moins de t étapes), l'interpréteur à essence termine en renvoyant la valeur calculée, sinon, l'interpréteur à essence termine avec une valeur spéciale « manque d'essence » (autrement dit : j'ai exécuté votre programme le temps que vous m'avez dit, il n'a pas fini dans le temps imparti, si vous voulez, vous pouvez réessayer avec plus d'essence). L'interpréteur à essence, qui est essentiellement le prédicat T de Kleene, même s'il est fastidieux à écrire, est codable dans mon langage (0), y compris s'il s'agit d'interpréter l'un des langages plus riches (1), (2) ou (3).

La notion d'« étape » d'exécution dans le paragraphe précédent n'est volontairement pas spécifiée exactement : cela pourrait correspondre au nombre d'étapes de l'exécution d'une machine de Turing, ou autre machine virtuelle, vers laquelle on a compilé le code de e (l'interpréteur à essence commence donc par effectuer cette compilation, ce qui est primitif récursif, puis lance l'exécution pendant e étapes de calcul). Mais cela pourrait aussi correspondre à quelque chose de plus abstrait et de beaucoup plus petit ou plus grand que le nombre d'étapes au sens que je viens de proposer : rien ne dit donc qu'il s'agit d'étapes dans un sens qui permette de développer une théorie usuelle de la complexité (en fait, la seule chose qui importe est qu'il y ait des bornes elles-mêmes primitives récursives entre les « nombres d'étapes » demandés par deux interpréteurs de ce genre). Le fait-clé est que si e est une fonction primitive récursive donnée (autrement dit, le code d'une fonction écrite dans le langage (0)), il existe une autre fonction primitive récursive h telle que l'interpréteur à essence termine l'exécution de e(z) en h(z) étapes : c'est pour cette raison qu'on donne souvent le slogan : une fonction primitive récursive est exactement la même chose qu'une fonction calculable en complexité elle-même primitive récursive (cette affirmation ne suffit pas à définir les fonctions primitives récursives, mais elle est néanmoins utile à retenir).

En particulier, cette histoire d'« interpréteur à essence » implique que tout programme pour un de ces langages (prenant un unique argment z, pour simplifier) peut s'écrire dans le langage (2) (= extension uloop) avec une unique boucle non bornée extérieure à toute autre boucle : il s'agit juste de lancer l'interpréteur à essence avec une boucle qui lui donne de plus en plus d'essence (augmente la valeur de t) jusqu'à ce que l'exécution termine. Du genre : function myprogram(z) { uloop (t) { local ret = universal_fuel_interpreter(e, z, t); if (ret.p) return ret.q; } } (où la fonction universal_fuel_interpreter est écrite entièrement dans le langage (0) et renvoie un couple dont la première composante est 1 si l'exécution est terminée et 0 sinon, et où e est un entier qui représente le code source du programme original écrit dans le langage (3). Ce n'est pas bien surprenant (on sait qu'un simulateur de machine de Turing peut se faire avec une unique boucle non bornée), et ce n'est pas un résultat difficile, mais c'est quelque chose à garder à l'esprit quand on parle de calculabilité.

Digression : je ne sais pas si c'est moi qui invente le terme interpréteur à essence ; Google ne semble pas donner de résultat intéressant pour la recherche, pourtant, dans le monde parallèle dont je viens, ce terme étant standard, enfin, je crois. Si quelqu'un retrouve à quoi je pouvais penser…

*

Disons rapidement un mot sur les tableaux. Ils sont une autre extension que je peux ajouter à mon langage (et qui est orthogonale aux deux que j'ai déjà définies). En voici une spécification possible : un tableau se déclare avec quelque chose comme local t[] (ce qui donne maintenant deux types dans mon langage), il est de taille illimitée, indicé par des nombres quelconques, et initialement rempli par des zéros ; la valeur d'un tableau t à l'indice i s'obtient avec t[i] et peut être affectée (par exemple, t[i]=t[j] affecte à la valeur à l'indice i du tableau la valeur contenue à l'indice j). Pour fixer les idées, on va dire que les tableaux ne peuvent ni être affectés globalement, ni renvoyés par une fonction, ni reçus en argument, et il n'y a aucune espèce de pointeurs. On va aussi dire qu'il n'y a pas de tableaux multidimensionnels (si on veut ça, on peut utiliser t[i#j]). En fait, le principal intérêt des tableaux est, en l'absence de l'extension avec récursion, de permettre à la définition d'une fonction de faire appel à des valeurs antérieures, du genre :

function fibo(n)
{
    local tab[];
    tab[1] = 1;
    loop (local i < n)
        tab[i+2] = tab[i] + tab[i+1];
    return tab[n];
}

Sur l'exemple ci-dessus, il n'est évidemment pas difficile de réécrire la fonction pour ne pas utiliser de tableaux. Mais en fait, dans le cas fini, qui est ce dont je parle pour l'instant, de toute manière, les tableaux n'ajoutent rien à mon langage au niveau expressivité : en effet, je peux toujours les représenter comme des listes, et représenter les listes elles-mêmes au moyen de la fonction de paire. Par exemple, voici une « implémentation » des tableaux dans le langage qui ne les a pas :

/* WARNING: The following functions work in the finite case only. */

function get_tab_value(tab, i)
// Return i-th value stored in table tab (represented as scalar).
{
    loop (local j < i)
        tab = tab.q;
    return tab.p;
}

function set_tab_value(tab, i, v)
// Return table tab with i-th value modified to take value v.
{
    local sizebound = tab;  // Upper bound on number of nonzero values
    if (sizebound <= i)
        sizebound = i+1;
    local size, revtab, newtab;
    loop (local j < sizebound) {  // Compute new array backwards.
        if (j == i)
            revtab = v#revtab;
        else
            revtab = (tab.p)#revtab;
        size += 1;
        tab = tab.q;
        if (tab == 0 && j>=i)
            break;
    }
    loop (local j < size) {  // Reverse it!
        newtab = (revtab.p)#newtab;
        revtab = revtab.q;
    }
    return newtab;
}

— cette implémentation devrait faire frémir d'horreur quiconque a la moindre notion d'efficacité en tête, mais elle fonctionne (dans le cas fini !) et c'est tout ce qui nous importe ici pour conclure que les tableaux n'apportent rien de nouveau dans le cas fini ; bizarrement, dans le cas transfini, cette affirmation va devenir beaucoup plus difficile.

Maintenant je veux passer au transfini. J'ai quatre langages finis (voire huit si je compte les tableaux, mais oublions-les pour le moment) ; chacun d'entre eux va passer au transfini sans le moindre changement à sa syntaxe. En revanche, il faut que j'explique comment la sémantique est modifiée, ou plutôt, étendue.

Le nouveau principe est donc : les variables contiennent maintenant des ordinaux (les entiers naturels étant le cas des ordinaux <ω). Ces ordinaux peuvent, en principe, être arbitrairement grands, mais en fait, (a) il ne sera pas possible de faire apparaître des ordinaux arbitrairement grands à moins qu'ils soient donnés initialement (je vais y revenir), et (b) on ne perdra rien d'intéressant à supposer qu'ils soient dénombrables.

Je n'ai pas grand-chose à changer sur les opérateurs. L'addition et la multiplication sont celles usuelles sur les ordinaux : il faut juste se rappeler que ces opérations ne sont plus commutatives. Cela a d'ailleurs un certain intérêt, par exemple on pourra écrire :

function is_finite(x)  // Return 1 iff x<ω.
{
    return 1+x > x;
}

Les tests et opérations booléennes fonctionnent sans différence notable. Les affectations n'ont pas non plus spécialement à être modifiées (je souligne que a+=x affecte à a la valeur de a+x dans cet ordre, mais c'est de toute façon la logique qu'emploie le C pour les opérations non commutatives). Le codage des paires utilisé par l'opération # est le codage standard de Gödel : il n'est pas nécessaire de savoir exactement ce que c'est pour lire la suite, mais pour ceux qui veulent des détails (voir ici pour différentes présentations), c'est l'énumération des paires d'ordinaux par les ordinaux associée au bon-ordre sur les ordinaux défini par (α,β)<(α′,β′) lorsque max(α,β)<max(α′,β′) ou [max(α,β)=max(α′,β′) et α<α′] ou [max(α,β)=max(α′,β′) et α=α′ et β<β′] ; on peut aussi en donner des formules explicites, mais elles ne sont pas très jolies (par exemple, 0#(ω·k+n), si k et n sont entiers naturels, vaut : ω²·(k−1)+ω·(2kn)+n si k≥2 et ω·(2n+1)+n si k=1 et n² si k=0 ; les formules générales sont de ce style).

Le if fonctionne exactement pareil que dans le cas fini. La boucle loop, elle, nécessite des explications : il n'y a pas de mal à imaginer que loop (a<x) s fasse parcourir à l'ordinal a toutes les valeurs jusqu'à x, mais que se passe-t-il pour les valeurs des variables dans la boucle ? À une étape qui est un ordinal successeur (je rappelle qu'un ordinal successeur est un ordinal de la forme γ+1 pour un certain ordinal, ou, de façon équivalente, un ordinal tel qu'il existe un plus grand ordinal γ strictement plus petit que lui), tout se passe exactement comme dans le cas fini : les valeurs des variables à l'entrée de la boucle (autres que la variable a de contrôle de boucle) sont celles qu'elles avaient à l'étape précédente ; et bien sûr, à l'étape 0, les valeurs sont celles qu'elles avaient avant la boucle. Mais pour une étape limite (par exemple a=ω), où il n'y a pas d'étape « précédente », que valent les variables ? Par exemple, si je considère la fonction suivante

function mystery(x)
{
    local flip = 0;
    loop (local z < x) {
        if (flip == 0)
            flip = 1;
        else
            flip = 0;
    }
    return flip;
}

— quelle est la valeur retournée par la fonction si on lui présente l'ordinal ω comme valeur de x en entrée ? Dans le cours de la boucle, la valeur de la variable flip alternait entre 0 et 1, mais cette suite n'a pas de limite en ω. Il faut faire une convention ici, il y en a plusieurs possibles, et j'aime bien la suivante :

Convention « limite sup » : aux étapes limites des boucles transfinies (y compris en sortie normale de boucle si sa longueur est une limite), les variables visibles dans la boucle prennent pour valeur la limite supérieure des valeurs qu'elles prenaient aux points en fin d'exécution du bloc de la boucle.

La limite supérieure, ici, signifie le plus petit ordinal qui soit supérieur ou égal à toutes les valeurs à partir d'un certain point. Je vais donner quelques exemples pour tenter de faire comprendre ce que cette convention signifie un peu plus concrètement.

Pour donner un premier exemple pertinent, dans la fonction mystery ci-dessus, la variable flip ne prend que les valeurs 0 et 1, et prend infiniment souvent la valeur 1, donc sa limite supérieure est 1 (car l'ordinal 1 est supérieur ou égal à toutes les valeurs de flip à partir d'un certain point, tandis que l'ordinal 0 ne l'est pas vu que flip passe infiniment souvent à 1). En revanche, je souligne que dans ma convention, seules comptent les valeurs prises par les variables en fin de bloc de boucle (ou ce qui revient au même, en début). Notamment, dans la fonction suivante :

function stupid(x)
{
    local flip = 0;
    loop (local z < x) {
        flip = 1;
        flip = 0;
    }
    return flip;
}

— la valeur retournée est toujours 0 (heureusement ! le contraire serait extrêmement contre-intuitif), car à la fin de chaque bloc de boucle, la valeur de flip est 0.

Voici un autre exemple, illustrant pourquoi je prends la limite sup et pas simplement le sup :

function mystery2(x)
{
    local flarp = 0;
    loop (local z < x) {
        if (z == 42)
            flarp = 42;
        else
            flarp = 0;
    }
    return flarp;
}

— cette fonction renvoie la valeur 42 en 43, et 0 en tout autre ordinal : notamment, si x=ω, la valeur de flarp vaut tout le temps 0 sauf à une itération bien précise où elle vaut 42, mais la limite sup est bien 0 (car à partir d'un certain moment, flarp vaut tout le temps 0) ; prendre le sup aurait été extrêmement contre-intuitif.

Quant à la fonction

function mystery3(x)
{
    local flirp = 0;
    loop (local z < x)
        flirp = z;
    return flirp;
}

— elle renvoie x−1 si x est un entier naturel, mais en ω elle renvoie ω car la limite sup de 0,1,2,3,… vaut ω. Plus généralement, cette fonction renvoie le prédécesseur d'un ordinal successeur, mais est l'identité sur les ordinaux limites (qui n'ont pas de prédécesseur). J'en profite pour signaler que je maintiens la convention que la variable de contrôle est affectée, en fin de boucle, à la valeur (initiale) de x, si bien que

function identity(x)
{
    local z = 0;
    loop (z < x)
        /* (nothing) */;
    return z;
}

— renvoie simplement la valeur qu'on lui passe (dans le cas transfini comme dans le cas fini). Mais la fonction identité peut aussi s'écrire ainsi :

function identity(x)
{
    local t = 0;
    loop (< x)
        t += 1;
    return t;
}

— ce qui est peut-être surprenant quand x parcourt les ordinaux (on ne peut pas atteindre ω en ajoutant 1 à 0, mais la convention de la limite sup permet de faire comme si). À ce sujet, si on ne disposait pas d'opérateur exprès pour, la multiplication des ordinaux pourrait être définie par

function mult(x, y)
{
    local val = 0;
    loop (< y)
        val += x;
    return val;
}

D'autres conventions étaient possibles : la limite inf, par exemple, ne changerait pas grand-chose et rien du tout aux fonctions finalement calculables. (Peter Koepke, dans sa définition des machines à registres ordinales, utilise la limite inf ; je crois que j'avais choisi la limite sup parce que d'autres gens prennent le sup tout court, alors que l'inf tout court ne convient pas, et aussi parce que la limite inf est un tout petit peu plus longue à définir en une phrase en français ce que j'ai dit pour la limite sup, le plus petit ordinal qui soit supérieur ou égal à toutes les valeurs à partir d'un certain point.)

Bref, j'ai maintenant défini mon langage de base (0) dans le cas transfini. Les remarques suivantes sont claires, mais il est sans doute utile de les faire explicitement :

Les fonctions calculables par mon langage (toujours (0) sans forward ni uloop) sont ce qu'on appelle les fonctions primitives récursives sur les ordinaux.

Ce qui est extrêmement perturbant dans le cas transfini, c'est que les constantes ne sont pas forcément calculables (calculable signifiant ici primitives récursives, mais la même remarque vaudra pour les langages étendus) : alors que dans le cas fini on peut toujours expliciter une constante en l'entrant dans le code (return 42 par exemple), dans le cas transfini ce n'est plus le cas, faute de notation générale pour les ordinaux. On ne peut pas écrire return ω pour retourner ω si on n'a pas une variable déjà affectée à la valeur ω. En fait, pour le cas (0) du langage sans forward ni uloop, les constantes calculables sont exactement les entiers naturels (tout entier naturel est calculable comme je l'ai dit avant, et aucun ordinal infini n'est calculable sans entrée particulière, puisque comme remarqué ci-dessus, un programme prenant des entrées finis ne va jamais pouvoir produire un ordinal infini).

À cause de ça, il est utile de scinder en deux la terminologie calculable de la manière suivante : dans un langage donné (le langage (0) défini ci-dessus ou une des extensions (1), (2) ou (3), disons), on dira qu'une fonction est calculable sans paramètres lorsqu'il existe une fonction (du langage) qui calcule cette fonction sans faire appel à des données auxiliaires, tandis qu'elle est calculable avec paramètres lorsqu'il existe une fonction qui la calcule lorsqu'on lui fournit les bonnes constantes en entrée ; dans le cas fini, cette distinction est sans objet, mais dans le cas transfini, seules les constantes finies sont primitives récursives sans paramètres alors que toute constante est primitive récursive avec paramètres (trivialement par définition de avec paramètres).

Par exemple, la fonction ordinale ξξ² est primitive récursive [sans paramètres] puisqu'elle est calculée par le programme function square(x) { return x*x; } mais les fonctions ξ↦ω [constante] ou ξξ·ω ne sont primitives récursives qu'en le paramètre ω (je répète : une fonction primitive récursive sans paramètre doit prendre des valeurs finies sur les entiers naturels puisque le langage est exactement le même dans le cas fini).

À défaut qu'un ordinal comme ω soit primitif récursif (sans paramètres), on peut se demander s'il est primitivement récursivement reconnaissable (ou en abrégé p.r.-reconnaissable), autrement dit, puis-je écrire une fonction (de mon langage (0) sans forward ni uloop) qui, prenant un argument, renvoie 1 si cet argument vaut ω et 0 sinon ? Oui, c'est assez facile, en se rappelant que ω est le plus petit ordinal infini :

function is_finite(x)  // Return 1 iff x<ω.
{
    return 1+x > x;
}

function is_ω(x) // Return 1 if x==ω, 0 otherwise
{
    // If x is finite, return false.
    if (is_finite(x))
        return 0;
    // If there is an infinite t<x, return false.
    loop (local t < x)
        if (! is_finite(t))
            return 0;
    // We checked that x is the smallest infinite ordinal: so x==ω.
    return 1;
}

Je n'insiste pas plus sur cette notion, l'intérêt de la remarque étant surtout de souligner que calculer et reconnaître ne sont pas synonymes, au moins dans le langage (0). (Peut-être certains lecteurs se demandent-ils cependant quel est le plus petit ordinal qui n'est pas primitivement récursivement reconnaissable : la réponse à cette question n'est pas évidente, et en tout état de cause, cet ordinal, quoique dénombrable, est « très grand », beaucoup plus grand, par exemple, que l'ordinal ω₁CK de Church-Kleene dont je parlerai plus loin.)

La notion suivante est également logique : un ordinal α est primitivement récursivement clos, ou en abrégé p.r.-clos, lorsque toute fonction primitive récursive appliquée à des arguments <α, a une valeur elle-même <α ; autrement dit, de façon plus imagée, que mon langage (toujours (0) sans forward ni uloop) ne peut pas fabriquer d'ordinal ≥α si on ne lui fournit que des ordinaux <α. J'ai déjà fait observer que ω est p.r.-clos (donnés des arguments <ω, i.e., finis, une fonction du langage (0) ne peut fabriquer que des résultats eux-mêmes <ω). En revanche, ω·2 n'est pas p.r.-clos puisqu'on peut le calculer comme ω+ω (à partir d'ordinaux strictement plus petits que ω·2, donc) ; il en va de même de ω² ; ce qui est peut-être moins évident, c'est que ε₀ n'est pas non plus p.r.-clos, parce qu'il existe une fonction p.r. qui, quand on lui passe ω en argument, renvoie ε₀, comme le montre le programme suivant :

function power(x, y)
// Returns x↑y for ordinals x,y.
{
    local val = 1;
    loop (< y)
        val *= x;
    return val;
}

function compute_ε0_from_ω(input_ω)
// Returns ε₀ when called with ω as argument.
{
    // if (! is_ω(input_ω)) error("Called with wrong value!");
    local exp_tower = 0;
    loop (< input_ω)
        exp_tower = power(input_ω, exp_tower);
    return exp_tower;
}

De même, on pourra s'exercer à écrire une fonction qui renvoie ε₁, voire, ce qui est plus intéressant, la α-ième solution εα de ξξ (en utilisant ω et α comme arguments). Indication : le point crucial est que, donné un ξ vérifiant ξξ, on peut calculer le suivant en partant de ξ+1 et en faisant une tour de puissances ωξ+1, ωωξ+1, etc., comme ci-dessus ; autrement dit, donné εα on peut calculer εα+1, et comme la fonction α↦εα est continue, il n'y a ensuite plus qu'à boucler. On peut s'en servir pour faire une fonction qui (toujours en prenant ω en argument) calcule le plus petit point fixe φ(2,0) de la fonction ξ↦εξ ; ou même le α-ième point fixe.

(Peut-être certains lecteurs se demandent-ils, à ce stade, quel est le plus petit ordinal après ω qui soit p.r.-clos : il s'avère qu'il est n'est pas terriblement grand, et en tout cas nettement plus petit que l'ordinal ω₁CK de Church-Kleene dont je parlerai plus loin. Plus exactement, si on définit la « fonction de Veblen » de deux variables, φ par φ(0,α) = ωα et φ(n+1,α) = le α-ième point fixe de φ(n,—) (en particulier, φ(1,α)=εα), et je n'ai pas besoin de plus que φ(ω,0) = la limite des φ(n,0) où n parcourt les entiers naturels, alors ce φ(ω,0) est le plus petit ordinal p.r.-clos après ω. Moralement, la fonction de Veblen se comporte sur les ordinaux un peu comme la fonction d'Ackermann sur les entiers naturels : chaque φ(n,—), pour n entier naturel fixé, est primitive récursive, selon les idées du paragraphe précédent, mais la fonction φ de deux variables, ou la fonction φ(ω,—), ne le sont pas. Ceci fournit une idée assez claire de la limite de puissance des fonctions primitives récursives et donc du langage (0).)

Je voudrais cependant faire remarquer que, pour ce qui est des fonctions des ℕ→ℕ (des entiers naturels vers les entiers naturels), dès qu'on donne à un programme du langage (0) accès à la constante ω, il devient extrêmement puissant. Pour commencer, il est capable de calculer toute fonction calculable au sens usuel (Church-Turing) : cela résulte du théorème de la forme normale de Kleene : en effet, si e est le code d'une fonction d'un langage (1)–(3) qui, sur les entiers naturels, calcule la fonction qu'on souhaite, on peut écrire dans le langage (0) : function compute(z, ω) { loop (t<ω) { local ret = universal_fuel_interpreter(e, z, t); if (ret.p) return ret.q; } } (où universal_fuel_interpreter est l'« interpréteur à essence » dont j'ai parlé plus haut, qui effectue t étapes de calcul de e exécuté sur z) et, pour peu qu'on invoque cette fonction en donnant à l'argument ω la valeur ω, elle effectuera le calcul voulu puisqu'il y aura toujours une quantité t<ω d'essence qui suffise à mener le calcul… Sauf si le calcul ne termine pas, mais c'est encore mieux, car cela signifie que le langage (0), si on lui donne la valeur ω, est non seulement capable d'émuler n'importe quelle machine de Turing mais même de décider de son arrêt (function halting_problem(z, ω) { loop (t<ω) { local ret = universal_fuel_interpreter(e, z, t); if (ret.p) return 1; } return 0; }). Et on peut continuer encore plus loin : on peut tester l'arrêt des machines de Turing ayant accès à l'oracle d'arrêt des machines de Turing, par exemple. On peut s'imaginer que cela continue jusqu'à la puissance des machines hyperarithmétiques (j'ai expliqué ici ce que sont ces machins), mais ce n'est pas le cas : ce serait le cas dans le langage (1) avec l'extension récursion (forward), mais dans le langage (0), la constante ω permet « seulement » de calculer jusqu'à φ(ω,0) « sauts de Turing », où φ(ω,0) est le plus petit ordinal p.r.-clos après ω.

On peut aussi se demander quelles sont les fonctions ω→ω primitives récursives en paramètres, au sens de n'importe quels paramètres (pas juste ω). Dans ce cas, on obtient vraiment beaucoup de choses : toutes les fonctions ω→ω dans l'univers constructible. Ceci peut servir de définition de ce qu'est une suite d'entiers constructible, même si ce n'est pas la plus pratique ni peut-être la plus intelligible, mais cela explique vaguement l'idée que la constructibilité est une généralisation monstrueuse de la calculabilité.

Maintenant que j'ai passé mon langage de base au transfini, je veux discuter les deux extensions orthogonales que j'ai définies dans le cas fini : l'extension « avec récursion » (c'est-à-dire, avec forward) et l'extension « avec boucles non bornées » (avec uloop). Dans le cas fini, les deux extensions (ainsi que leur combinaison) étaient équivalentes en pouvoir d'expression. Il n'en va plus de même dans le cas transfini.

L'extension « avec récursion » n'est pas spécialement problématique à définir, mais elle n'est pas non plus terriblement intéressante. Il ne semble pas y avoir de manière intéressante de donner un sens à la récursion (au sens : appel récursif de fonctions) dans le cas transfini, donc on va convenir que, comme dans le cas fini, dès que la récursion part à l'infini la fonction est non-définie (c'est-à-dire : on donne à la sémantique du langage la définition la plus restreinte possible de façon à donner un sens à une expression si tous ses appels ont déjà été faits). Entre autres, une fonction comme function stupid() forward; function stupid() { return stupid()+1; } ne termine jamais et ne renvoie donc rien de significatif (et certainement pas ω). Cela signifie aussi qu'on ne peut pas utiliser la récursion terminale dans le langage pour faire des boucles non bornées (comme elles vont être définies ci-après) : ce serait peut-être agréable, mais je ne sais vraiment pas comment donner une sémantique sensée au machin.

L'extension « boucles non bornées » n'est pas compliquée et va utiliser la même convention « limite sup » pour les uloop que pour les loop. Mais avant d'en dire plus, il faut que je signale une chose importante : alors que pour le langage de base et pour son extension « avec récursion » je n'ai fait que prolonger la sémantique (tout programme conservait exactement le même comportement du cas fini au cas transfini, que ce soit un programme terminant ou non-terminant), ici je vais raffiner la sémantique, c'est-à-dire que des programmes qui précédemment ne terminaient pas vont se mettre à terminer (par exemple, le programme function compute_ω() { uloop(a) { if is_ω(a) return a; } } — où la fonction is_ω(x) est définie plus haut —, ne terminait pas dans le cas fini, et va se mettre maintenant à terminer en renvoyant, comme on s'y attend, l'ordinal ω, dès que l'« ordinal de boucle » sera >ω).

Pour définir mon langage avec extension « boucles non bornées » dans le cas transfini, il faut que je choisisse un ordinal de boucle, appelons-le λ. Le cas du langage fini correspond à λ=ω ; généralement, on aura envie de supposer que l'ordinal de boucle λ est « admissible », un concept que je définirai plus loin. La définition est très simple : uloop (a) s est équivalent à [correction : merci jonas] loop (a<λ+1) { if (a<λ) s; else do_not_terminate(); }do_not_terminate() est supposé être une fonction qui ne fait rien et ne termine pas : autrement dit, une uloop (boucle non bornée) fait le même effet qu'une boucle bornée de taille λ, à ceci près que si la boucle n'est pas interrompue avant que la variable de contrôle n'atteigne λ alors le calcul ne termine pas. En particulier, un programme avec l'extension « boucles non bornées » peut faire strictement moins qu'un programme ne disposant pas de cette extension mais disposant d'un accès à une constante valant λ : j'avais déjà fait cette remarque dans le cas λ=ω, mais le phénomène est général.

Pour être bien clair, j'ai donc défini non pas un langage avec extension « boucles non bornées », mais bien un langage pour chaque ordinal λ : si on remplace λ par λ′>λ, certains programmes qui précédemment ne terminaient pas vont se mettre à terminer (mais bien sûr, il y a des programmes qui ne terminent jamais quelle que soit la valeur de λ, par exemple uloop () {}).

J'ai donc défini quatre langages dans le cas transfini : (0) le langage de base, (1) le langage avec extension forward, (2) ou plus exactement (2)λ le langage avec boucles non bornées (et ordinal de boucle =λ), et enfin (3) ou plus exactement (3)λ le langage avec extension forward et boucles non bornées (et ordinal de boucle =λ). Pour chacun de ces langages, on peut s'intéresser aux fonctions f qu'il est capable de calculer, et ce, dans le cas sans paramètres (= je dois écrire une fonction dans le langage qui prend comme arguments juste ceux de la fonction f à définir) ou avec paramètres (= ma fonction a le droit de prendre des arguments supplémentaires et sera appelée avec certains ordinaux particuliers en entrée), éventuellement avec des restrictions sur ces paramètres (par exemple : avec paramètres <κ pour un certain ordinal κ). Cela fait, a priori, beaucoup de choses à regarder !

Voici une hypothèse critique qui va permettre d'éclaircir considérablement les choses : on dit que l'ordinal λ est admissible (ou parfois récursivement régulier) lorsque toute λ est clos par les fonctions calculables du langage (2)λ ou, ce qui revient au même, (3)λ : autrement dit, toute fonction du langage (2)λ (ou (3)λ), invoquée avec des paramètres <λ et qui termine, renvoie une valeur elle-même <λ (je vais donner d'autres caractérisations équivalentes plus bas, qui seront peut-être plus parlantes). C'est un peu l'analogue pour les langages (2)λ/(3)λ de la notion d'ordinal p.r.-clos pour le langage (0), mais il faut que je souligne que l'ordinal λ est utilisé dans la définition du langage lui-même (comme ordinal de boucle).

Bref, un ordinal admissible est un ordinal λ tel que vous ne pouvez pas fabriquer d'ordinal ≥λ à partir d'ordinaux <λ en utilisant le langage que j'ai défini, même si on permet des boucles non bornées de taille λ lui-même.

On fera (presque toujours) cette hypothèse d'admissibilité quand on parle du langage (2) ou (3), et, de plus, quand c'est le cas, on fera aussi (presque toujours) l'hypothèse que les programmes et les fonctions reçoivent des arguments <λ (du coup, tous les calculs intermédiaires seront eux-mêmes <λ à cause de l'admissibilité). En principe, on peut tout à fait considérer ce qui se passe quand on fait tourner un programme du langage (3)λ sur des arguments ≥λ, mais en pratique, ce n'est pas très intéressant (en gros, parce que disposer d'un ordinal ≥λ est beaucoup plus puissant que de pouvoir faire des uloop, donc autant se limiter aux langages (0) et (1)).

Un ordinal admissible est nécessairement p.r.-clos (puisque « p.r.-clos » a la même définition pour le langage (0), qui est plus faible). L'ordinal ω (qui est le premier p.r.-clos) est le premier ordinal admissible. (Mais il n'est pas vrai que tout ordinal p.r.-clos soit admissible : j'ai évoqué plus haut le deuxième ordinal p.r.-clos, à savoir φ(ω,0) : il est très loin d'être admissible car il est facile de programmer la fonction φ elle-même dans le langage (1), ou dans le langage (2) avec n'importe quel ordinal de boucle >ω.) Le plus petit ordinal admissible >ω est appelé ω₁CK, l'ordinal de Church-Kleene, qu'on peut définir de diverses façons (par exemple c'est la borne supérieure des types ordinaux de tous les bons ordres sur ℕ qui soient calculables par une machine de Turing ordinaire, ou, ce qui revient au même, par le les langages (1)–(3), ou d'ailleurs même (0), dans le cas fini) [ajout : j'aurais dû préciser, pour faire le lien avec une entrée passée, que les fonctions ω→ω (c'est-à-dire ℕ→ℕ) qui sont ω₁CK-récursives sont exactement celles qui sont hyperarithmétiques]. Tout cardinal indénombrable (à commencer par le « vrai » ω₁, c'est-à-dire ℵ₁) est admissible (et en fait, récursivement inaccessible, récursivement Mahlo, etc., des notions que j'évoquerai plus bas).

Lorsque λ est admissible, la théorie de la calculabilité sur λ ressemble par certains égards beaucoup à celle qu'elle est sur ω. Voici quelques faits qui peuvent aider à s'y repérer :

(L'écriture de l'interpréteur à essence est véritablement problématique, cependant. Je vais y revenir.)

Je vais introduire la terminologie suivante :

(Une fonction totale est juste une fonction. Une fonction partielle est une fonction définie sur un sous-ensemble des valeurs, ou si on préfère, une fonction qui peut prendre la valeur spéciale ⊥ signifiant « non-défini » ou « calcul qui ne termine pas ».)

Clairement, toute fonction primitive récursive est secondive récursive, et toute fonction secondive récursive (restreinte aux ordinaux <λ) est λ-récursive pour tout λ admissible. Si j'autorise des paramètres ordinaux quelconques, alors ces classes coïncident (à ceci près que les fonctions primitives récursives sont définies partout tandis que les autres peuvent ne pas l'être), puisque j'ai déjà expliqué que l'accès à la valeur λ permet au langage (0) de faire tout ce que le langage (3)λ peut faire. Mais généralement on s'intéressera aux fonctions λ-récursives en paramètres <λ, et une des surprises de l'histoire est qu'il y a de telles fonctions qui ne sont pas λ-récursives sans paramètres (autrement dit, il existe des constantes <λ qu'aucun programme du langage (3)λ ne peut calculer).

Pour faire le lien avec la théorie des ensembles, et pour ceux qui savent ce que tout ceci veut dire : un ordinal λ est admissible (au sens que je viens de définir) si et seulement si le niveau Lλ de l'univers constructible de Gödel est un modèle de la théorie des ensembles de Kripke-Platek (un sous-ensemble raisonnable de ZFC), ou ce qui suffit, vérifie l'axiome de Σ₀-collection (ou Σ₁-remplacement) ; de plus, lorsque c'est le cas, les fonctions λ-récursives (sans ou avec paramètres) sont exactement celles qui ont une définition Σ₁ (sans ou avec paramètres) sur Lλ. L'article Wikipédia pertinent est ici, mais il n'est, ahem, pas très lisible.

Digression : Le langage (1) n'est pas furieusement intéressant, et c'est sans doute pour ça que les fonctions secondives récursives n'apparaissent pas dans la littérature mathématique. Elles apparaissent cependant (c'est de là que je les tire), avec une définition différente (mais je crois équivalente à la mienne) dans le (chapitre VIII du) livre de Hinman, Recursion-Theoretic Hierarchies, où elles sont appelées fonctions (0,∞)-récursives ; en fait, ce que fait Hinman est de supposer d'emblée que le langage possède un auto-interpréteur (sans essence !), ce qui revient au même, je crois, que mon extension forward : son intérêt est de court-circuiter tous les problèmes relatifs à la construction de fonctions universelles, au prix d'une certaine perte de finesse. Je n'ai pas une idée très claire de ce que sont les ordinaux secondivement récursivement clos (je crois que le premier après ω est ω₁CK, qui est admissible, mais que le s.r.-clos suivant n'est pas admissible — par le passé j'avais cru que si mais mon intuition a changé — mais je n'en sais vraiment pas grand-chose ; en revance, ce dont je suis sûr, c'est qu'une limite d'ordinaux admissibles est secondivement récursivement close, et comme elle n'est généralement pas admissible, cela réfute l'implication s.r.-clos⇒admissible).

*

L'extension du langage autorisant les tableaux ne pose pas de difficulté particulière à étendre au cas transfini : les tableaux sont indicés par les ordinaux et peuvent contenir des ordinaux, et on adoptera pour chaque cellule de tableau la même convention « limite sup » qui a été faite pour les variables dans le cas sans tableau. (En revanche, les tableaux ne se remplissent pas par magie : par exemple, la fonction fibo que j'ai donnée plus haut, telle que je l'ai écrite, si on lui passe ω en argument, elle renvoie 0 parce que rien ne remplit jamais la cellule ω du tableau.)

Comme dans le cas fini, l'extension avec tableaux n'apporte, pour aucun des langages (0)–(3) (du moins, pour les langages (2) et (3), lorsque l'ordinal de boucle λ est admissible, mais en fait je pense que même ça n'est pas nécessaire) aucune extension de la puissance du langage : les fonctions (prenant en entrée des ordinaux et renvoyant des ordinaux !) exprimables dans le langage sans ou avec tableau sont exactement les mêmes, dans chacun des langages (0) à (3).

La différence avec le cas fini, cependant, c'est que cette équivalence est étonnamment plus difficile à prouver dans le cas transfini : j'ai donné une implémentation des tableau dans le langage (0) sans tableaux pour le cas fini, il est facile de se rendre compte que cette implémentation ne marche plus du tout dans le cas transfini (par exemple, si je remplis toutes les cases d'un tableau numérotées par des entiers naturels de la valeur 1, avec cette implémentation et à cause de la convention limite sup, j'obtiens un tableau dont toutes les cases sont nulles !).

La démonstration de l'équivalence qu'on trouve dans la littérature mathématique (dans l'article de Ronald Jensen & Carol Karp, Primitive Recursive Set Functions, in: Dana Scott (ed.), Axiomatic Set Theory (Los Angeles 1967) AMS 1971, Proc. Sympos. Pure Math. 13, p. 143–176 ; et spécifiquement théorèmes 3.3 et 4.6) est vraiment compliquée et même si en principe elle donne le codage recherché, il serait extraordinairement fastidieux de la transcrire sous la forme d'un programme : essentiellement, elle utilise une des constructions de Gödel pour représenter les ensembles constructibles comme des ordinaux. On en conclut que toutes les fonctions primitives récursives d'ensembles restreintes aux ordinaux sont primitives récursives sur les ordinaux, donc qu'autoriser le langage à manipuler directement des ensembles (ou, ce qui n'est assurément pas plus fort, des tableaux ordinaux→ordinaux) ne renforce rien : le point crucial est qu'à tout moment, l'ensemble ou le tableau va être constructible.

J'avoue que cette histoire me rend un peu malheureux : je me dis qu'un truc pareil ne devrait pas être trop compliqué, ne devrait pas faire intervenir la théorie des ensembles dans un langage qui se contente a priori de parler d'ordinaux. Je trouve que l'introduction des tableaux gâche un peu la pureté et la simplicité de mon langage de programmation, mais d'un autre côté, si je ne les mets pas, je ne sais pas, dans la pratique, faire tout ce que je veux avec (même si je sais qu'en théorie c'est possible), à commencer par l'écriture d'un « interpréteur à essence », et ça me contrarie. Je ne sais pas à quel point l'obstacle est fondamental ou si la complexité de la démonstration donnée par Jensen & Karp (référence ci-dessus) est due à la technique de leur approche. (Peut-être qu'une réponse est contenue dans la thèse soutenue en 1974 par Stanley H. Stahl sous la direction de Peter Hinman, Classes of Primitive Recursive Ordinal Functions, je vais essayer de mettre la main dessus même si ce n'est pas forcément évident.)

Il reste que le point suivant est notable : même si le contenu d'un tableau, au cours de l'exécution d'un programme d'un de mes langages transfinis, peut être infini (contenir une infinité de valeurs non nulles), mais du point de vue du langage, il est « “fini” » en ce sens que l'ensemble des indices contenant une valeur non nulle dans le tableau est borné et que l'ensemble des valeurs peut être calculé par une fonction du langage ; c'est essentiellement ça l'idée qui fait que les tableaux n'apportent rien de nouveau : tout ce qu'on peut mettre dedans pourrait, de toute façon, être (complètement) calculé autrement. (C'est aussi pour cette raison que je n'autorise pas les tableaux en argument ou en valeur de retour d'une fonction : ça ouvrirait tout un sac de nœuds — intéressant, certes, mais différent de ce dont je veux parler — si on commence à fournir à une fonction un tableau qui n'est pas rempli avec des données « “fini” ».)

*

Maintenant il faut que je reconnaisse une chose, c'est que je n'ai pas une idée totalement claire de la manière dont on peut écrire l'interpréteur à essence (ce que j'ai appelé universal_fuel_interpreter(e, z, t) ci-dessus) dans le cas transfini : autrement dit, comment faire pour écrire, dans le langage (0), une fonction qui prend en argument le code e d'un programme d'un des langages (0)–(3) et un argument z à lui passer, et qui l'exécute pendant t étapes. Dans le cas fini, une façon de faire « à l'informaticien » est essentiellement de compiler le programme e vers une machine virtuelle quelconque (genre, une machine de Turing), ce qui est primitif récursif en la longueur du programme puis de lancer l'exécution de cette machine pour t étapes. Dans le cas transfini, cette approche est certainement possible, mais il n'est pas complètement évident de définir le bon type de machine virtuelle. Il y a bien des modèles de calcul transfinis ressemblant à des machines de Turing, mais leur rapport avec le langage que j'ai décrit n'est pas si clair et je n'ai aucune idée de comment faire une « compilation »).

Si on s'autorise à écrire l'interpréteur dans le langage (1), alors il me semble que les choses sont plutôt faciles, parce qu'on peut faire de la récursion, l'interpréteur s'appelant récursivement pour toute nouvelle fonction ou toute nouvelle boucle (on peut transformer toute affectation de variable en un appel de fonction, et globalement j'ai l'impression qu'il n'y a pas de difficulté substantielle) : ceci permet d'interpréter le langage (1) lui-même ou, par un procédé de coalescence des uloop dont je vais parler ci-dessous, le langage (3) (avec essence !), et du coup tous les autres. Mais je ne vois pas bien comment échapper à la récursion. Peut-être qu'on peut syntactiquement transformer un programme du langage (1) en le langage (2) (compiler l'un en l'autre, par une machine de Turing ordinaire) : cela devrait être possible, mais de nouveau, cela ne me semble pas super clair (c'est surtout cette étape qui diffère du cas fini, où c'est plutôt facile, il suffit de simuler une pile d'appels), ce qui permettrait alors de reconvertir dans le langage (0) en coalescant les uloop, mais j'ai les idées plutôt floues. Je vois déjà mieux comment m'en sortir dans le langage (0) si on dispose de tableaux, ou en fait, simplement, de tableaux finis (j'imagine déjà mieux maintenir un « état courant » dans un tableau, tenant compte de tous les appels ayant été faits), mais même les tableaux finis ne sont pas évidents à simuler dans le langage (0) pur si on veut qu'ils respectent les règles de passage à la limite qu'on impose sur les variables. Bref, je sais que tout est faisable en théorie, mais en pratique je suis un peu confus.

La démonstration faite, dans les différentes sources mathématiques auxquelles j'ai accès (et que j'ai trouvées), du théorème de la forme normale de Kleene pour le cas de la α-récursion, consiste, à chaque fois, à passer par des considérations de théorie des modèles appliquées à l'univers constructible de Gödel L (la définition va ressembler à ceci : il est possible de définir une fonction primitive récursive qui à un ordinal γ et le code ‹φ› d'une formule φ en une variable z, et une valeur z pour cette variable, associe la valeur de vérité de Lγφ(z) ; or les fonctions primitives récursives sont absolues à suffisamment de niveaux Lγ) ; il est certainement possible de dérouler ces démonstrations pour obtenir quelque chose d'explicite à la fin, mais ce sera compliqué et j'ai encore du mal à comprendre où et comment la magie se produit au juste.

Il y a néanmoins un argument important que je peux expliquer et qui n'est pas compliqué, c'est l'argument de coalescence des uloop (en gros, ça va nous permettre de réécrire syntaxiquement tout programme du langage (2) en un programme du langage (2) avec un unique uloop tout à l'extérieur, i.e., de transformer tout programme du langage (2) en un programme « à essence » du langage (0)). Supposons que j'aie un programme du langage (2) ou (3) du genre (imaginez qu'on est dans le cas fini, pour commencer) :

function search_happy(a) {
    uloop (x) {
        uloop (y) {
            local val = am_i_happy(a, x, y);
            if (val >= 2)
                return x;  // Return this x.
            if (val == 1)
                break;     // Proceed to next x.
            // Otherwise, proceed to next y.
        }
    }
}

— qui cherche le premier x pour lequel la première valeur non nulle renvoyée par un certain test (am_i_happy, faisant intervenir un paramètre a et une variable testée y) soit ≥2 (autrement dit, la valeur 0 de retour du test veut dire continuer à chercher sur ce x, la valeur 1 signifie passer au x suivant, et la valeur 2 signifie arrêter le test, on a trouvé) ; c'est en fait un cas archétypique de deux boucles imbriquées (on peut toujours se ramener à quelque chose de ce genre). Or on peut le réécrire de la manière suivante :

function search_happy(a) {
    uloop (t) {
        loop (x<t) {
            loop (y<t) {
                local val = am_i_happy(a, x, y);
                if (val >= 2)
                    return x;  // Return this x.
                if (val == 1)
                    break;     // Proceed to next x.
            }
            break; // Search with larger t.
        }
        // Search with larger t.
    }
}

— autrement dit, limiter les boucles sur x et y à taille bornée t, et faire une seule boucle non bornée sur t. J'appellerai ça la coalescence des deux uloop contenus dans le programme de départ. Dans le cas fini, il est facile de voir que le nouveau programme a le même comportement que l'ancien (si le programme d'origine termine, il existe t fini suffisamment grand qui borne à la fois le x qu'on va renvoyer et chaque y pour lequel la boucle intérieure aura terminé). Dans le cas transfini, ce qui joue de façon cruciale est l'admissibilité de l'ordinal de boucle λ : en effet, l'admissibilité permet d'appliquer essentiellement le même raisonnement que dans le cas fini : si le premier programme ci-dessus termine, à la fois le x renvoyé mais aussi la borne supérieure de tous les y auxquels la boucle intérieure se sera arrêtée seront calculables en fonction de a (implicitement supposé <λ, bien sûr), et du coup, ces quantités doivent être <λ. En fait, l'admissibilité de λ est exactement équivalente à cet argument de coalescence des boucles : le fait que les deux programmes ci-dessus soient équivalents pour toute fonction am_i_happy primitive récursive (et tout argument a<λ) signifie précisément que λ est admissible.

*

Une question apparentée est celle de savoir si on peut reconnaître si un ordinal passé en argument est admissible (= récursivement régulier) ou non. La réponse est oui en appliquant directement la définition :

function is_admissible(x)
{
    if (1+x > x)
        return 0;  // Finite ordinals are not admissible.
    // Now we know that x is infinite: use it to compute ω.
    local ω;
    loop (ω < x+1)
        if (1+ω == ω)  // Stop at the first infinite ordinal.
            break;
    // Now run every possible program e with every possible argument
    // z<x and check that, if it terminates in time t<x, the
    // value returned is still <x.
    loop (local e < ω)
        loop (local z < x)
            loop (local t < x) {
                local ret = universal_fuel_interpreter(e, z, t);
                if (ret.p && (ret.q >= x))
                    return 0;
            }
    return 1;
}

— mais j'ai supposé ici avoir accès à un interpréteur (à essence) pour le langage (2) ou (3) : ce n'est pas très satisfaisant vu que la notion d'ordinal admissible entre déjà dans la définition même de ces langages (du moins si on fait la convention que l'ordinal de boucle doit être admissible), ce qui rend la chose un peu circulaire ; voici une écriture différente de ce test, où on suppose seulement avoir accès à un interpréteur (à essence) pour le langage (0) (toujours dans le langage (0)) :

function is_admissible(x)
{
    if (1+x > x)
        return 0;  // Finite ordinals are not admissible.
    // Now we know that x is infinite: use it to compute ω.
    local ω;
    loop (ω < x+1)
        if (1+ω == ω)  // Stop at the first infinite ordinal.
            break;
    // Now run every possible p.r. program e with every possible
    // arguments z<x and y<x and check that it terminates in time
    // t<x and that, moreover, the sup of y<x for which a nonzero
    // value is returned always remains <x.
    loop (local e < ω)
        if (is_valid_language_0(e)) {
            // We test this for every possible p.r. function e:
            local sup_y;
            loop (local z < x) {
                loop (local y < x) {
                    // Evaluate e at (z,y):
                    local term;
                    loop (local t < x) {
                        local ret = universal_fuel_interpreter_0(e, z#y, t);
                        if (ret.p) {
                            term = 1;
                            if (ret.q) {
                                // If returned value >=1, stop at this y.
                                if (y >= sup_y)
                                    sup_y = y;
                                break 2;  // Break the loop on y.
                            } else
                                break;  // Break the loop on t.
                        }
                    }
                    // If e didn't terminate in time, x isn't even p.r.-closed:
                    if (! term)
                        return 0;
                }
                // Since sup_y is computable from z, if it attains x,
                // then x is not admissible:
                if (sup_y >= x)
                    return 0;
            }
        }
    return 1;
}

Le fait que ce programme fasse bien ce qu'on attend dépend essentiellement de l'argument de coalescence des boucles que j'ai exposé ci-dessus (plus exactement, du fait que la coalescence des boucles soit équivalente à l'admissibilité de l'ordinal de boucle).

Une fois qu'on sait reconnaître (dans le langage (0)) si un ordinal est admissible, on peut s'en servir pour reconnaître toutes sortes d'autres choses. Par exemple, un ordinal ρ est dit récursivement inaccessible lorsqu'il est admissible et que pour les ordinaux admissibles ne sont pas bornés au-dessous de lui (cette deuxième partie signifie : si α<ρ alors il existe λ admissible tel que αλ<ρ), ou, ce qui revient au même, ρ est admissible et limite d'admissibles. Voici comment on peut tester ce fait :

function is_recursively_inaccessible(x)
{
    // Check whether x is admissible:
    if (! is_admissible(x))
        return 0;
    // Compute the limit sup_y of admissibles <x:
    loop sup_y;
    loop (local y < x)
        if (is_admissible(y))
            sup_y = y;
    // Now x is admissible iff sup_y is x:
    return sup_y >= x;
}

Voici une autre propriété qu'on peut tester, et je le laisse en exercice : un ordinal ρ est dit récursivement Mahlo lorsque pour toute fonction f qui soit ρ-récursive en paramètres (c'est-à-dire calculable dans le langage (2)ρ ou (3)ρ, avec éventuellement des paramètres <ρ), il existe un ordinal admissible λ<ρ tel que f(ξ)<λ pour tout ξ<λ. (Remarquez que si je retire le mot admissible, c'est exactement la définition du fait que ρ soit admissible, donc récursivement Mahlo est certainement plus fort qu'admissible ; en fait, cela implique aussi que ρ est récursivement inaccessible comme on le voit en prenant f constante. Remarquez par ailleurs que le fait que λ soit admissible signifie que f(ξ)<λ pour tout ξ<λ lorsque f est une fonction λ-récursive, mais ici elle est supposée ρ-récursive.) On peut tester la récursive mahloïtude de manière semblable à la manière dont on a tester l'admissibilité (= récursive régularité).

Digression : J'avais évoqué (peut-être même plusieurs fois) par le passé le fait qu'il existe une correspondance assez surprenante entre :

  1. les grands entiers naturels (i.e., les ordinaux <ω),
  2. les grands ordinaux constructifs (i.e., les ordinaux <ω₁CK),
  3. les grands ordinaux dénombrables [dans l'univers constructible] (i.e., les ordinaux <ω₁L),
  4. les grands cardinaux [qui ont le droit d'exister dans l'univers constructible],

Ici ce que je décris sommairement par les termes de récursivement inaccessible et récursivement Mahlo, ce sont les analogues au niveau 2 (grands ordinaux dénombrables) de cette liste de notions de niveau 3 (grands cardinaux, en l'occurrence les cardinaux inaccessibles et les cardinaux Mahlo, que je ne vais pas définir). Tous les cardinaux indénombrables sont récursivement inaccessibles, récursivement Mahlo et bien plus, mais ce sont surtout les ordinaux dénombrables qui sont intéressants dans ce contexte.

Bon, cette entrée est en train de devenir très confuse et je traîne de plus en plus à l'écrire, donc il vaut sans doute mieux que je m'arrêter ici. Il y a trois choses liées que j'aurais encore voulu discuter, mais il vaut mieux que je renvoie ça à une éventuelle entrée ultérieure où je récapitulerai(s) tout ce qui précède :

Si vous voulez plus de précisions ou de références sur ces différentes notions d'ordinaux, voyez celles qui sont données dans ce petit texte.

En attendant, je laisse mes lecteurs avec ce défi de programmation transfini que d'écrire un interpréteur intéressant (donc, pour les plus courageux, un interpréteur à essence du langage (3) avec tableaux dans le langage (0) sans tableaux, ce qui est le plus fort qu'on puisse demander), ou du moins, d'expliquer comment ils feraient. Je précise que je n'ai malheureusement pas d'accès à un ordinateur transfini pour tester d'éventuels programmes !

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

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