Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Fonction récursive primitive
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.