Fonction récursive primitive

predecesseur(0) = 0

predecesseur(Succ(x)) = x

On utilise ici la définition récursive de predecesseur en prenant n=0, g la fonction identiquement nulle, h(x,y) = x projection sur la première composante.

somme(0,y) = y

somme(Succ(x),y) = Succ(somme(x,y))

On utilise ici la définition récursive de somme en prenant n=1, g(y) = y, h(x,z,y) = Succ(z), composée de la fonction Successeur et de la projection sur la deuxième composante.

Plus généralement, si ${\displaystyle g(i,{\vec {x}})}$ est une fonction récursive primitive de ${\displaystyle (i,{\vec {x}})}$, alors ${\displaystyle f(n,{\vec {x}})=\sum _{i=0}^{n}g(i,{\vec {x}})}$ est une fonction récursive primitive de ${\displaystyle (n,{\vec {x}})}$.

produit(0,y) = 0

produit(Succ(x),y) = somme(y,produit(x,y))

On utilise ici la définition récursive de produit en prenant n=1, g identiquement nulle, h(x,z,y) = somme(y,z), composée de la fonction somme déjà définie et de deux projections.

Plus généralement, si ${\displaystyle g(i,{\vec {x}})}$ est une fonction récursive primitive de ${\displaystyle (i,{\vec {x}})}$, alors ${\displaystyle f(n,{\vec {x}})=\prod _{i=0}^{n}g(i,{\vec {x}})}$ est une fonction récursive primitive de ${\displaystyle (n,{\vec {x}})}$.

Il s'agit de la fonction valant 0 pour x = 0 et 1 pour x > 0.

sg(0) = 0

sg(Succ(x)) = 1

On a pris n = 0, g nulle, h égale à la constante 1.

La différence tronquée de y par x vaut y-x si x < y et 0 sinon.

soustrait(0,y) = y

soustrait(Succ(x),y) = predecesseur(soustrait(x,y))

On a pris g(y) = y et pour h la fonction predecesseur déjà définie appliquée sur sa deuxième composante.

Il en résulte que la valeur absolue | x - y | = soustrait(x,y) + soustrait(y,x) est également récursive primitive.

Il en est de même de max(x,y) = x + soustrait(x,y) et de min(x,y) = soustrait(max(x,y),x+y).

À tout prédicat défini sur ${\displaystyle \mathbb {N} ^{k}}$, on peut associer sa fonction caractéristique :

${\displaystyle f({\vec {x}})=1\;{\rm {si}}\;P({\vec {x}})\;{\rm {vrai}}}$

${\displaystyle f({\vec {x}})=0\;{\rm {si}}\;P({\vec {x}})\;{\rm {faux}}}$

On dira que le prédicat P est récursif primitif lorsque sa fonction caractéristique est récursive primitive.

On peut montrer que, si deux prédicats P et Q sont récursifs primitifs, il en est de même des prédicats (non P), (P et Q), (P ou Q), (P implique Q).

Le prédicat x < y est récursif primitif, puisque sa fonction caractéristique est égale à sg(soustrait(x,y)), qui est une fonction récursive primitive.

Sont également récursifs primitifs les prédicats suivants :

x divise y

x est un nombre premier

x mod y = z

Si ${\displaystyle P(x,{\vec {y}})}$ est un prédicat récursif primitif de ${\displaystyle (x,{\vec {y}})}$, alors les deux prédicats suivants sont des prédicats récursifs primitifs de ${\displaystyle (n,{\vec {y}})}$ :

• ${\displaystyle \forall x\leq n,P(x,{\vec {y}})}$ ;
• ${\displaystyle \exists x\leq n,P(x,{\vec {y}})}$.

En effet, si ${\displaystyle f(x,{\vec {y}})}$ est la fonction caractéristique associée à ${\displaystyle P(x,{\vec {y}})}$, alors les fonctions caractéristiques associées aux deux prédicats de quantification bornée précédents sont respectivement :

• ${\displaystyle \prod _{x=0}^{n}f(x,{\vec {y}})}$ ;
• ${\displaystyle 1-\prod _{x=0}^{n}(1-f(x,{\vec {y}}))}$.

Il est très important de borner la quantification par un nombre n. En effet, les prédicats ${\displaystyle \forall x,P(x,{\vec {y}})}$ et ${\displaystyle \exists x,P(x,{\vec {y}})}$ ne sont pas récursifs primitifs.

Ainsi, le prédicat « il existe un nombre parfait impair inférieur à n » est récursif primitif, mais pas le prédicat « il existe un nombre parfait impair ». On ignore d'ailleurs (en 2015) la valeur de vérité de ce dernier prédicat.

Si ${\displaystyle P(x,{\vec {y}})}$ est un prédicat récursif primitif de ${\displaystyle (x,{\vec {y}})}$, alors la fonction définie par :

${\displaystyle f(n,{\vec {y}})=}$ le plus petit ${\displaystyle x\leq n}$ vérifiant ${\displaystyle P(x,{\vec {y}})}$, si un tel x existe, et = n+1 sinon

est récursive primitive.

En effet, si ${\displaystyle g(x,{\vec {y}})}$ est la fonction caractéristique associée à ${\displaystyle P(x,{\vec {y}})}$, alors f est définie comme suit :

${\displaystyle f(n,{\vec {y}})=\sum _{k=0}^{n}\prod _{i=0}^{k}(1-g(i,{\vec {y}}))}$

Là aussi, il est important de borner la recherche du minimum. La fonction cherchant le plus petit x vérifiant ${\displaystyle P(x,{\vec {y}})}$ n'est plus récursive primitive en général.

Ainsi, la fonction cherchant le plus petit nombre parfait impair inférieur à n (ou n+1 s'il n'existe pas) est une fonction récursive primitive de n. Mais la fonction donnant le plus petit nombre parfait impair supérieur à n n'est pas récursive primitive.

Nous avons vu, dans le paragraphe Limites de la récursion primitive, deux exemples d'algorithmes non récursifs primitifs qui définissent des fonctions :

• La fonction d'Ackermann, dont on peut montrer qu'elle n'est pas récursive primitive. Il n'existe aucun algorithme primitif récursif définissant la fonction d'Ackermann ;
• La fonction minimum, qui, elle, est récursive primitive. Il existe une autre définition de la fonction minimum n'utilisant que la récursion primitive (cf. Exemples/Différence tronquée).

Se pose alors la question suivante. Étant donné une fonction, définie récursivement (par un algorithme quelconque) est-il possible de déterminer par un processus automatique si cette fonction est récursive primitive ? Est-il possible de savoir si sa définition peut être modifiée pour ne faire appel qu'à la récursion primitive ? La réponse à cette question est négative. Il n'existe aucune procédure permettant de dire si une fonction récursive est récursive primitive ou non. On dit que la détermination du caractère récursif primitif d'une fonction définie par un algorithme est indécidable. C'est un cas particulier du théorème de Rice, qui définit toute une classe de questions indécidables.

Nous pouvons donner schématiquement le raisonnement conduisant à cette conclusion. Les fonctions définies par un algorithme peuvent être numérotées par ordre croissant, au moyen d'un codage numérique de l'algorithme ou de la machine de Turing qui les définit. On appellera ${\displaystyle \phi _{n}}$ la n-ème fonction ainsi définie.

Raisonnons par l'absurde et supposons qu'il existe une procédure RP s'appliquant à l'algorithme définissant une fonction f (ou à l'entier n tel que ${\displaystyle f=\phi _{n}}$) et qui vaut 1 si f est récursive primitive et 0 sinon. Notons RP(f) cette valeur 0 ou 1. Considérons alors, pour chaque entier n la fonction ${\displaystyle g_{n}}$ de ${\displaystyle x}$ définie par :

${\displaystyle g_{n}(x)=\phi _{n}(n)\times 0}$

Si l'algorithme de la fonction ${\displaystyle \phi _{n}}$ se termine par une valeur quelconque lorsqu'on l'applique à l'entier n lui-même, alors ${\displaystyle g_{n}}$ est identiquement nulle. Elle est alors récursive primitive, et ${\displaystyle RP(g_{n})}$ = 1. Par contre, si l'algorithme de la fonction ${\displaystyle \phi _{n}}$ se met à boucler indéfiniment lorsqu'on l'applique à l'entier n lui-même, alors le calcul de ${\displaystyle g_{n}(x)}$ ne se termine pas. ${\displaystyle g_{n}}$ n'est pas récursive primitive, et ${\displaystyle RP(g_{n})}$ = 0. On a donc :

${\displaystyle RP(g_{n})=0}$ si et seulement si le calcul de ${\displaystyle \phi _{n}(n)}$ ne se termine pas.

Considérons enfin la fonction C définie par l'algorithme suivant :

function C(n)

if ${\displaystyle RP(g_{n})}$ = 0

then return(0)

else while true do od

fi

La fonction C fonctionne comme suit : si ${\displaystyle RP(g_{n})=0}$, alors C(n) retourne la valeur 0. Mais si ${\displaystyle RP(g_{n})=1}$, alors C(n) entre dans une boucle dont elle ne ressort pas, et l'algorithme ne se termine pas. Autrement dit :

Le calcul de C(n) se termine si et seulement si ${\displaystyle RP(g_{n})=0}$, si et seulement si le calcul de ${\displaystyle \phi _{n}(n)}$ ne se termine pas.

C étant défini par algorithme possède un rang c tel que ${\displaystyle C=\phi _{c}}$. L'équivalence ci-dessus s'écrit alors :

Le calcul de ${\displaystyle \phi _{c}(n)}$ se termine si et seulement si le calcul de ${\displaystyle \phi _{n}(n)}$ ne se termine pas.

Que se passe-t-il lorsqu'on donne à n la valeur c ? L'équivalence devient :

Le calcul de ${\displaystyle \phi _{c}(c)}$ se termine si et seulement si le calcul de ${\displaystyle \phi _{c}(c)}$ ne se termine pas.

ce qui est absurde.

Aboutissant à une contradiction, on en conclut que la procédure RP ne peut exister.

Considérons la fonction définie comme suit, pour n>0 :

function Collatz(n)

while n<>1 do

if n mod 2 = 0 then n := n/2

else n := 3*n+1 fi

od

return(1)

On ignore si, pour tout n, la boucle while se termine ou si, au contraire, il existe un entier n pour lequel le programme boucle indéfiniment. La conjecture de Syracuse postule que c'est le premier cas qui se produit. Il en résulterait alors que la fonction Collatz est la fonction constante égale à 1, et donc récursive primitive. Mais on est actuellement dans l'incapacité de prouver cette assertion.

Les termes de Martin-Löf sont soit :

• le numéral 0 ;
• le successeur d'un terme Succ ;
• une variable a, b, c…
• une récursion : Rec(t, b, (x,y) s).

Dans la récursion, t est un terme sur lequel on fait la récursion, b est le cas de base et s l'étape de récurrence. Dans l'étape de récurrence, la variable x représente le prédécesseur de l'entier sur lequel on fait la récurrence et le y est l'étape de récurrence.

L'addition de n et p s'écrit Rec(n,p,(x,y)Succ(y)).

Kleene a introduit les combinateurs qui sont une autre manière de représenter les fonctions récursives primitives. Les combinateurs sont munis d'arité, c'est-à-dire qu'ils ont un nombre de paramètres défini (sauf dans un cas particulier).

Un combinateur est :

• le combinateur 0 d'arité zéro. C'est une fonction constante ;
• le combinateur Succ d'arité un qui va associer à un combinateur son successeur ;
• la i^e projection : π_iⁿ d'arité n qui va associer à un n-uplet le i^e élément ;
• l'application S(c ; c₁, …, c_n), c étant un combinateur d'arité n, et les c_i des combinateurs d'arité m et le combinateur en entier est d'arité m. Ce combinateur sert à donner à un combinateur des paramètres quelconques ;
• la Récursion : Rec(b,s) avec b un combinateur d'arité n, s un combinateur d'arité n+2 et le combinateur en entier est d'arité n+1. b est le cas de base et s l'étape de récurrence.

L'addition se programme ainsi : Rec(π₁¹, S(Succ, π₂³))