Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Fonction récursive primitive

Définitions

Définissons les entiers unaires : t est entier si t=0 ou s'il existe t' un entier tel que t=Succ(t') (c'est-à-dire t=t'+1).

Une fonction récursive primitive est définie par

Exemples :

Prédécesseur d'un entier :

predecesseur(0) = ∅

predecesseur(Succ(x)) = x

Somme de deux entiers :

somme(0,y) = y

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

produit de deux entiers :

produit(0,y) = 0

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

Limites de la récursion primitive

La fonction d'Ackermann définie par

ackermann(0,p) = Succ(p)

ackermann(Succ(n),0) = ackermann(n,1)

ackermann(Succ(n),Succ(p)) = ackermann(n,ackermann(Succ(n),p))

n'est pas récursive primitive car la récursion se fait sur deux entiers simultanément.

Le même problème se pose si on veut utiliser cet algorithme du minimum :

minimum(0,p) = 0

minimum(Succ(n),0) = 0

minimum(Succ(n),Succ(p)) = Succ(minimum(n,p))

Formalismes

La récursion primitive est un langage de programmation théorique qui a la propriété que tous les programmes écrits dans ce langages terminent. Pour pouvoir écrire des programmes dans ce langage on peut utiliser différents formalismes.

Les termes de Martin Löf

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.

Sémantique

Exemple

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

Les Combinateurs de Kleene

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.

Sémantique

Exemples

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