Je me dis souvent que la classe des fonctions primitives récursives est le parent mal aimé de l'informatique théorique.
Les fonctions générales récursives — c'est-à-dire, calculables au sens de Church-Turing — figurent dans n'importe quel cours de base : ce sont celles qui peuvent être calculées par une machine de Turing (ou toutes sortes d'autres modèles de calculs, comme des machines à registres), ou encore définies dans le λ-calcul de Church (non typé) ou par le schéma de récursion générale, ou bien calculables par essentiellement n'importe quel langage de programmation idéalisé raisonnable (je recommande la lecture du livre de Hofstadter, Gödel, Escher, Bach, et la description du langage FlooP, comme exemple). Toutes ces descriptions sont équivalentes. Le cours va ensuite généralement souligner deux choses : (A) il est possible de réaliser une machine de Turing universelle (c'est-à-dire, qui prend en entrée une description d'une autre machine de Turing et l'entrée à fournir à cette dernière, et simule son exécution, donc termine ssi l'autre termine, et renvoie le même résultat si c'est le cas), ce qui revient, informatiquement, à écrire un interpréteur d'un langage de programmation dans lui-même (ou dans un autre, peu importe), et (B) il n'est pas possible pour une machine de Turing de résoudre le problème de l'arrêt des machines de Turing, c'est-à-dire de décider (en terminant toujours) si une machine de Turing spécifiée s'arrête (sur une entrée donnée, mais en fait peu importe). La plupart des cours s'arrêtent là.
Une idée fausse que je crains que beaucoup d'étudiants tirent d'une
telle description est que les choses ne vont pas plus loin. J'aime
souligner la chose suivante : la machine de Turing représente une
modélisation de ce qui est (idéalement !) calculable mécaniquement
dans cet Univers, c'est un modèle raisonnable et assez naturel (comme
le prouve le nombre de choses qui lui sont équivalentes), mais il y a
bien des choses au-delà (et d'ailleurs aussi, en-deçà). On peut
notamment considérer des machines de Turing avec oracle :
ce sont des machines semblables au machines de Turing (ou au modèle de
calcul que vous préférez), mais à n'importe quel point dans leur
exécution elles ont le droit de consulter l'oracle, celui-ci
étant une fonction a priori quelconque, et la réponse tombe du
ciel ; par exemple, on peut définir les machines de Turing ayant accès
à un oracle qui répond à la question la machine de Turing suivante
s'arrête-t-elle
(l'oracle du problème de l'arrêt). Le problème de
l'arrêt de ces machines-là est lui-même insoluble
pour ces machines-là (et à plus forte raison pour les
machines de Turing normales), et on peut donc définir un nouvel
oracle, etc. Cette opération s'appelle le saut de Turing :
les choses qu'on obtient en l'itérant un nombre fini de fois
s'appellent la hiérarchie arithmétique, et il y a toute une
problématique consistant à l'itérer de façon transfinie (ce qui
définit la
hiérarchie hyperarithmétique
et, si on va encore plus loin, tisse des liens avec la « structure
fine » de
l'univers
constructible de Gödel — des sujets sur lesquels je reviens
périodiquement dans ce blog). Les cours un peu avancés mentionneront
peut-être la hiérarchie arithmétique (et parfois aussi la hiérarchie
analytique, qui, pour toutes sortes de raisons que je ne veux pas trop
décrire ici, est en fait assez mauvaise au-delà du niveau Δ¹₂ et ne
mérite pas vraiment d'être qualifiée de hiérarchie de calculabilité).
Un jour il faut que j'écrive une entrée de ce blog sur les machines à
ordinaux, mais je digresse. Mon point est surtout qu'il y a beaucoup
de choses mathématiquement très bien définies, et même très
naturelles, au-delà de la machine de Turing. Et si je trollais un
peu, je dirais que la raison pour laquelle on se penche tellement sur
la machine de Turing est qu'on se préoccupe trop de sciences
appliquées comme l'informatique au lieu de sciences pures comme la
logique.
Pour redire un peu la même chose d'une façon différente, on peut définir le concept de degré de Turing : on dit qu'un problème X est Turing-réductible à un autre Y lorsque si on dispose d'un oracle qui résout Y on peut l'utiliser pour résoudre X au sens de Turing (i.e., il existe une machine de Turing qui, si on lui donne un oracle qui résout Y, résout X), et on dit que deux problèmes sont Turing-équivalents lorsque chacun est Turing-réductible à l'autre. (Par exemple, le problème de l'arrêt des machines de Turing est Turing-équivalent au problème du temps maximal d'exécution d'une machine de Turing qui s'arrête en fonction de la longueur de son programme.) L'ensemble des problèmes Turing-équivalents à un problème donné s'appelle le degré de Turing correspondant, les degrés de Turing sont ordonnés par la relation « être Turing-réductible à », et la description de cet ensemble (ou celui des degrés de Turing semi-décidables) mène à une théorie très riche et très intéressante (dont l'article Wikipédia précédemment cité donne un tout petit aperçu).
Tout ceci constitue la théorie de la calculabilité (parfois qualifiée de calculabilité supérieure s'agissant de l'itération possiblement transfinie du saut de Turing).
⁂
La théorie de la complexité, elle, s'interroge sur le temps que prend une machine de Turing (ou un autre modèle de calcul) à résoudre différentes sortes de problèmes. Par exemple, la classe P (ou devrais-je écrire 𝐏 ?) est l'ensemble des problèmes (ou fonctions, ou je ne sais quoi — à un tel niveau d'agitage de mains ça n'a guère d'importance) qu'une machine de Turing peut résoudre en temps polynomial dans la longueur de l'entrée. Il y a tout un zoo de classes de complexité et, en fait, on ne sait quasiment rien dire d'intéressant à leur sujet puisque quand on considère des classes aussi différentes que P ⊆ NP ⊆ PSPACE ⊆ EXPTIME, on sait seulement que l'inclusion entre la première et la dernière est stricte (ce qui est essentiellement trivial) alors qu'on soupçonne que chacune l'est, et d'ailleurs il y a un million de dollars à la clé pour montrer que la première est stricte. Mais en général, les gens qui s'intéressent à ce sujet s'intéressent plutôt aux classes de complexité « basses » comme P ou L, rarement plus haut que EXPTIME, et en tout cas ils restent sagement à l'intérieur de ELEMENTARY (qui est l'ensemble des problèmes résolubles par une machine de Turing en un temps qui peut être borné, en fonction de la taille de l'entrée, ou d'ailleurs de l'entrée elle-même, par une tour d'exponentielle de hauteur constante). Là aussi, j'ai un peu envie de troller en disant que c'est parce que la science appliquée domine tellement les choses qu'on oublie qu'il y a toutes sortes de questions mathématiques intéressantes à résoudre bien au-delà.
⁂
Et puis, dans des limbes perdus entre la complexité et la calculabilité, il y a les fonctions primitives récursives : trop hautes pour que la complexité s'y intéresse, trop basses pour que la calculabilité les voie, elles sont les oubliées de l'informatique théorique.
Certes, très souvent on en apprend une définition : celle-ci est d'ailleurs souvent présentée comme un jalon vers la définition des fonctions générales récursives. Historiquement, c'est le cas : les fonctions primitives récursives ont précédé les fonctions générales récursives (je dirais qu'elles remontent à un article d'Ackermann en 1928), on se rendait bien compte que la définition n'était pas satisfaisante, mais il a fallu du temps pour que se dégage le concept de calcul effectif et l'idée qu'on doit nécessairement passer par des fonctions partielles (i.e., des calculs qui ne terminent pas) pour espérer définir les fonctions récursives générales. Reste que la définition qu'on donne des fonctions primitives récursives est fort peu lisible et ne parle guère à l'intuition, et de toute façon elles ne sont plus mentionnées dans la suite (on se contente de signaler que la fonction d'Ackermann n'est pas primitive récursive, c'est un peu la tarte à la crème du sujet, et c'est tout).
La meilleure présentation que je connaisse des fonctions primitives récursives est, de nouveau, dans Gödel, Escher, Bach, c'est le langage que Hofstadter appelle BlooP. On peut le décrire de la façon suivante : c'est un langage de programmation idéalisé qui (dispose des fonctions arithmétiques usuelles, des tests, etc.) ne peut pas faire d'appels récursifs (toute fonction doit être définie strictement avant d'être appelée) et qui ne peut pas faire de boucle non bornée : les seules boucles autorisées sont des boucles dont le nombre maximal d'itération doit avoir été calculé avant d'entrer dans la boucle. À cause de cela, les programmes terminent toujours : il n'y a tout simplement aucun moyen d'écrire une boucle infinie.
Une autre façon de présenter les fonctions primitives récursives est la suivante, qui ne convient pas comme définition mais qui me semble néanmoins particulièrement éclairante : une fonction primitive récursive est une fonction qui peut être calculée par une machine de Turing en un temps (=nombre d'étapes) qui est lui-même borné par une fonction primitive récursive de l'entrée. C'est pour cette raison que les fonctions primitives récursives sont une classe de calculabilité : au lieu des fonctions calculables en temps polynomial, exponentiel, ou borné par une tour d'exponentielle, ici on prend les fonctions calculables en un temps primitif récursif. Et en fait, dès lors qu'on prend soin d'écarter les cas trop dégénérés, les fonctions primitives récursives sont la plus petite classe qui est de cette manière sa propre classe de complexité.
Je pense que c'est beaucoup plus parlant de définir les choses ainsi. Et cela aide à justifier que cette classe est profondément naturelle.
Cela aide aussi à comprendre précisément ce que les fonctions primitives récursives ne peuvent pas faire, de façon plus claire que la fonction d'Ackermann : on ne peut pas faire une machine primitive récursive universelle comme on peut faire une machine de Turing universelle, c'est-à-dire une fonction primitive récursive qui donnée deux entrées m et n calculerait la valeur de la m-ième fonction primitive récursive sur l'entrée n. Et c'est la principale raison pour laquelle on ne veut pas d'un langage de programmation qui n'autoriserait que les fonctions primitives récursives (même si ça aurait supposément l'avantage de garantir qu'un programme ne puisse jamais faire de boucle infinie) : cela interdirait de réaliser dans ce langage un interpréteur du langage lui-même (ou de n'importe quel autre langage aussi puissant, et bien sûr de n'importe quel langage Turing-complet).
C'est intéressant de remarquer comme cette construction « machine primitive récursive universelle » ressemble pour les fonctions primitives récursives au problème de l'arrêt pour la calculabilité de Church-Turing : j'ai envie d'appeler ça le saut de Kleene comme on appelle « saut de Turing » l'ajout de l'oracle de l'arrêt à une machine de Turing (si on veut, c'est un tout tout tout petit saut de Turing). On peut aussi chercher à itérer ce saut de Kleene : bizarrement, pour aller dans le transfini, c'est plus difficile qu'itérer le saut de Turing (essentiellement parce que l'itération dépend non seulement de l'ordinal sur lequel on l'itère mais aussi de la notation de celui-ci), et si on sait le faire pour des ordinaux « petits », il me semble qu'on n'a pas de description complète, par exemple, comme on pourrait le souhaiter, des fonctions générales récursives par pure itération du saut de Kleene (alors qu'on a une description raisonnablement satisfaisante des fonctions hyperarithmétiques, voire constructibles, par pure itération du saut de Turing).
Il y a aussi un lien (si on veut voir les fonctions primitives récursives, et leurs sauts de Kleene, comme des classes de complexité) avec les fonctions à croissance rapide, notamment la hiérarchie de Grzegorczyk. (On peut aussi préférer définir des fonctions machines primitives récursives « à compteur », qui disposent du droit de faire des appels récursifs mais qui, à chaque fois qu'elles le font, doivent décrémenter un compteur ordinal — malheureusement, ceci dépend là aussi d'une notation pour cet ordinal —, ce qui garantit qu'elles terminent toujours.) Et là, il faudrait faire un lien avec la théorie de la démonstration. (Par exemple, se donner une machine de Turing avec une preuve de la terminaison de celle-ci dans un système formel raisonnable revient plus ou moins à se donner une fonction située dans la hiérarchie au niveau de l'ordinal de preuve de ce système formel.)
Et on peut définir des degrés primitifs récursifs suivant le même modèle que les degrés de Turing : on dit qu'une fonction X est p.r.-réductible à une autre Y lorsqu'on peut calculer X avec une machine primitive récursive (ou une fonction du langage BlooP) disposant de Y comme oracle, i.e., lorsque X appartient à la classe des fonctions définies à partir de Y et des fonctions basiques usuelles par composition et récursion primitive. Et on dit que deux fonctions sont p.r.-équivalentes lorsque chacune est p.r.-réductible à l'autre. (Contrairement au cas de la réduction de Turing, on ne peut pas toujours se ramener à une fonction à valeurs dans {0,1}, i.e. un « problème de décision ».) L'ensemble des fonctions p.r.-équivalentes à une fonction donnée s'appelle le degré p.r. correspondant.
À titre d'exemple, le degré p.r. de la fonction d'Ackermann est le même que le degré p.r. de la fonction « primitive récursive universelle » (ce que j'ai appelé le — premier — saut de Kleene), c'est-à-dire la fonction qui à (m,n) associe la valeur de la m-ième fonction primitive récursive sur l'entrée n : en effet, dans un sens, pour chaque k fixé, il est facile d'écrire un programme BlooP qui prend une entrée n calcule Ackermann(k,n), et ce programme m(k) se calcule lui-même de façon primitive récursive en fonction de k, donc il suffit d'appliquer la fonction universelle ; dans l'autre sens, c'est un chouïa plus fastidieux, il faut remarquer que si f est une fonction primitive récursive, on peut calculer une borne sur le temps de calcul de f(n) sous la forme Ackermann(k,n+p) où k et p se calculent en fonction du numéro m de f dans la numérotation standard choisie des fonctions primitives récursives, et ce, de façon primitive récursive : mais dès lors qu'on peut calculer cette borne, il suffit de lancer une machine de Turing limitée à ce nombre de pas d'exécutions (et j'ai déjà souligné que ça c'est faisable par une machine primitive récursive) pour calculer f(n).
Ce qui est moins évident, par exemple, c'est qu'il existe des degrés p.r. strictement compris entre le degré des fonctions primitives récursives (=le plus petit degré p.r.) et son saut de Kleene (=le degré de la fonction d'Ackermann), et même, il existe ensembles totalement ordonnées denses de tels degrés, et aussi des degrés mutuellement incomparables entre eux : toutes sortes de phénomènes analogues aux degrés de Turing mais apparemment encore moins étudiés (en tout et pour tout, je n'ai trouvé qu'un vieil article de Axt, la thèse de Joel W. Robbin et un preprint(?) de Harold Simmons). C'est dommage : je pense qu'il y aurait sans doute un certain nombre de choses intéressantes à en dire.
(Questions en vrac qui me viennent à l'esprit sans trop réfléchir : l'ensemble des degrés p.r. qui sont Turing-récursifs a-t-il un sup ? ou, à défaut, y a-t-il moyen de définir canoniquement le degré p.r. de la fonction qui borne le temps d'exécution de la m-ième machine de Turing si elle s'arrête ? Si on définit un degré p.r. autobornant comme un degré p.r. d récursif tel qu'une fonction soit de degré ≤d ssi elle est calculable par une machine de Turing dont le temps d'exécution soit lui-même ≤d, alors les degrés autobornants sont-ils totalement ordonnés ?)
Et je n'évoque même pas les choses comme la complexité de Kolmogorov p.r. (analogue évident de la complexité de Kolmogorov utilisant des fonctions/machines primitives récursives au lieu des machines de Turing) ou les nombres aléatoires et génériques p.r. : ceux-ci ont l'« avantage » sur les concepts généraux récursifs correspondants qu'ils sont, eux, calculables par une machine de Turing (bon, évidemment, avec une complexité qui dépasse toute fonction primitive récursive, donc ce n'est pas très utile en pratique).