Fonction récursive primitive

En théorie de la calculabilité, une fonction récursive primitive est une fonction construite à partir de la fonction nulle, de la fonction successeur, des fonctions projections et des schémas de récursion primitive (ou bornée) et de composition. Ces fonctions constituent un sous-ensemble strict des fonctions récursives. Elles ont été initialement analysées par la mathématicienne Rózsa Péter. On s'intéresse aux fonctions définies sur l'ensemble des entiers naturels, ou sur les ensembles des -uplets d'entiers naturels, et à valeurs dans . On construit les fonctions récursives primitives par induction en partant des trois fonctions de base : La fonction identiquement nulle ; La fonction successeur : ; Les projections : . et en itérant les deux constructions suivantes : La composition de fonctions : si , , ..., sont récursives primitives sur et si est récursive primitive sur , toutes déjà définies, alors la fonction est une fonction récursive primitive définie sur ; La définition récursive d'une fonction : si est récursive primitive sur , et récursive primitive sur , on définit une nouvelle fonction récursive primitive sur par : Les fonctions récursives primitives se programment dans la plupart des langages de programmation, à l'aide d'une simple instruction itérative for : function f(x,y): z := g(y) for i from 0 to x-1 do z := h(i,z,y) do return(z) Il n'y a pas de boucles qui s'exécutent tant qu'une condition de sortie n'est pas vérifiée (boucle tant que, en anglais while), et le calcul des fonctions récursives primitives se termine toujours. 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.