Les fonctions récursives constituent une autre façon de définir la notion de calculabilité. Elles sont définies à partir de quelques fonctions de base, de la composition, d'un schéma de récurrence et d'un schéma de minimisation.
Les fonctions récursives sont des fonctions, éventuellement partielles, qui calculent des n-uplets d'entiers naturels. Chaque fonction récursive est une fonction d'un sous-ensemble de Nk dans Nr pour des entiers k et r. On commence par définir la sous-famille des fonctions primitives récursives qui sont des fonctions totales.
On introduit maintenant un certain nombre de fonctions primitives récursives de base.
Soit p un entier et soient p entiers k1, …, kp. Soit k l'entier égal à k1 + … + kp. Pour chaque i tel que 1 ≤ i ≤ p, soit ni un ki-uplet. On appelle identité et on note id la fonction qui associe aux ki-uplets n1, …, np le k-uplet formé en concaténant les p uplets n1, …, np. Par un abus de notation le k-uplet id(n1, …, np) est simplement noté (n1, …, np).
Pour tous entiers k ≥ 0 et i ≥ 0, on appelle fonction constante la fonction qui à tout k-uplet associe l'entier fixe i. Cette fonction est directement notée par l'entier i.
Pour tous entiers k ≥ i ≥ 0, la i-ème projection pk,i est définie par pk,i(n1, …, nk) = ni. Lorsqu'il n'y a pas d'ambiguïté, cette fonction est simplement notée pi.
Pour tout entiers r ≥ 0, la fonction de duplication dr est définie par dr(n) = (n, …, n) où l'entier n est répété r fois.
La fonction successeur s est définie par s(n) = n+1.
On définit maintenant les schémas de composition et de récurrence.
Soit p un entier et soient p+2 entiers k, r, k1, …, kp. Soient p fonctions f1, …, fp où chaque fonction fi pour 1 ≤ i ≤ p est une fonction de Nk dans Nki et soit g une fonction de Nk1+ … + kp dans Nr, alors la composée g(f1, …, fn) est la fonction de Nk dans Nr qui à chaque k-uplet n = (n1, …, nk) associe le r-uplet g(f1(n), …, fp(n)).
Soit k et r deux entiers. Soit f une fonction de Nk dans Nr et soit g une fonction de Nk+r+1 dans Nr. La fonction h = Rec(f, g) est la fonction de Nk+1 dans Nr définie récursivement de la manière suivante pour tout entier n et pour tout k-uplet m = (m1, …, mk).
La famille des fonctions primitives récursives est la plus petite famille de fonctions qui vérifie les conditions suivantes.
On donne ici les exemples classiques de fonctions primitives récursives. Ces fonctions seront utilisées dans la preuve de l'équivalence avec les machines de Turing.
La fonction sum définie par sum(n, m) = n+m est primitive récursive. Elle peut en effet en effet être définie de la manière suivante.
La fonction somme est donc égale à Rec(p1, s(p2)).
La fonction prédécesseur p définie par p(n) = max(0, n-1) est primitive récursive. Elle peut en effet en effet être définie de la manière suivante.
La fonction prédécesseur a pu être définie car le schéma de récurrence permet à la fonction g qui calcule h(n+1, m) d'utiliser la valeur de n. Sinon la fonction prédécesseur est difficile à définir. Une autre possibilité est de la mettre dans les fonctions de base à côté de la fonction successeur.
La fonction sub définie par sub(n, m) = n-m si n ≥ m et 0 sinon est aussi primitive récursive. Elle peut en effet en effet être définie de la manière suivante.
Comme la récurrence porte sur le second argument, la fonction sub est égale à sub'(p2, p1) où la fonction sub' est égale à Rec(p1, p(p2)).
La fonction prod définie par prod(n, m) = n*m est primitive récursive. Elle peut en effet en effet être définie de la manière suivante.
La fonction somme est donc égale à Rec(0, sum(p2, p3)).
La fonction eq0 définie par eq0(m) = 1 si m = 0 et eq0(m) = 0 sinon est primitive récursive. Elle est égale à Rec(1, 0). La fonction eq définie par eq(m, n) = 1 si m = n et eq(m, n) = 0 sinon est primitive récursive. Elle est égale eq0(sum(sub(p1, p2), sub(p2, p1))).
Les fonctions div et mod où div(n, m) et mod(n, m) sont respectivement le quotient et le reste de la division entière de n par m sont primitives récursives. La fonction div peut être définie de la manière suivante.
La fonction mod peut être alors définie par mod(n, m) = n - m*div(n, m).
La fonction pow où pow(n, m) = mn est primitive récursive. Elle peut être définie de la manière suivante.
La fonction root où root(n, m) est la racine m-ième de n, c'est-à-dire le plus grand entier k tel que km ≤ n est primitive récursive. Elle peut être définie de la manière suivante.
La fonction log où log(n, m) est le logarithme en base m de n, c'est-à-dire le plus grand entier k tel que mk ≤ n est primitive récursive. Elle peut être définie de la manière suivante.
On commence par définir la fonction ndiv(n) qui donne le nombre de diviseurs de l'entier n. Cette fonction est définie par ndiv(n) = pndiv(n, n) où la fonction pndiv qui donne le nombre de diviseurs de n inférieurs à p est définie de la manière suivante.
La fonction premier est alors définie par premier(n) = eq(ndiv(n), 2).
Montrer que la fonction val où val(n, m) est le plus grand entier k tel que mk divise n est primitive récursive.
On définit la fonction d'Ackermann A de N3 dans N par
Proposition. Pour tous m et n,
Une version simplifiée de la fonction de N2 dans N peut être obtenue en prenant m = 2 dans la définition ci-dessus. On prend aussi souvent comme définition la définition suivante qui est légèrement différente.
On dit qu'une fonction g de N dans N majore une fonction f de Nk dans N si f(n1, …, nk) ≤ g(max(n1, …, nk)).
Proposition. Pour toute fonction primitive récursive f de Nk dans N, il existe un entier k tel que f est majorée par la fonction g(n) = A(k, n).
Corollaire. La fonction d'Ackermann n'est pas primitive récursive.
Pour définir les fonctions récursives, on introduit un schéma de minimisation. Soit k et r deux entiers et soit f une fonction de Nk+1 dans Nr éventuellement partielle. On définit alors la fonction g = Min(f) de Nk dans N de la manière suivante. Pour m dans Nk, g(m) est l'entier n, s'il existe, tel que d'une part les valeurs f(0, m), …, f(n-1, m) sont égales à dr(0) et d'autre part f(n, m) est défini et différent de dr(0) (on rappelle que dr(0) est (0, …, 0) ou le 0 est répété r fois). Si un tel entier n n'existe pas, g(m) n'est pas défini. Même si la fonction f est totale, la fonction g = Min(f) peut être partielle.
La famille des fonctions récursives est la plus petite famille de fonctions qui vérifie les conditions suivantes.
Nous allons maintenant montrer le théorème suivant qui établit que les notions de calculabilité des fonctions récursives et des machines de Turing sont identiques.
Théorème. Une fonction de Nk dans Nr est récursive si et seulement si elle est calculable par une machine de Turing.
Pour les machines de Turing, il faut préciser comment sont codés les entiers. Ils peuvent être codés en binaire, en base 10 ou en base 1. Le choix du codage est en réalité sans importance puisqu'il est possible de passer d'un quelconque de ces codages à n'importe quel autre avec une machine de Turing.
Il est facile de de se convaincre qu'une fonction récursive est calculable par une machine de Turing. Les fonctions de base comme les fonctions constantes, les projections, les fonctions de duplication sont bien sûr calculables par machine de Turing. Ensuite avec des machines calculant des fonctions f, g, f1, …, fp, il n'est pas difficile de construire des machines de Turing pour les fonctions g(f1, …, fp), Rec(f, g) et Min(f).
Nous allons maintenant montrer qu'une fonction calculable par une machine de Turing est récursive. Soit M une machine de Turing qu'on suppose déterministe et avec un seul état d'acceptation q+. On suppose que le machine ne se bloque jamais. Soit n le nombre d'états de M et soit m le cardinal de son alphabet de bande. On suppose que les états de M sont les entiers {0, 1, 2, …, n-1} et que les symboles de bande sont les entiers {0, 1, …, m-1}, le symbole blanc # étant l'entier 0. Pour tout mot w = a0…ak sur l'alphabet de bande, on associe les deux entiers α(w) = ∑i=0kaimk-i et β(w) = ∑i=0kaimi obtenus en lisant w comme un nombre écrit en base m (avec les unités respectivement à droite et à gauche pour α et β). Les fonctions α et β permettent de considérer les mots de la bande comme des entiers.
Soit w une entrée de M et soit C0 ⇒ … ⇒ Cn le calcul de M sur w. On suppose que chaque configuration Ck est égale à ukqkvk. On va montrer que la fonction c définie par
c(β(w), k) = (α(uk), qk, β(vk))
est primitive récursive. À partir des transitions de M, on peut définir une fonction t telle que
t(q, a) = (p, b, x) si q, a → q, b, x est une transition de M.
On complète t sur N2 en posant t(i, j) = (0, 0, 0) si i ≥ n ou j ≥ m. La fonction t est bien sûr primitive récursive. On note t1, t2 et t3 les fonctions p1(t), p2(t) et p3(t) qui donnent respectivement le nouvel état, la symbole à écrire et le déplacement de la tête de lecture.
On a alors la définition récursive de c.