Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
Catégories
Techniques
Sciences
Encore plus...
Techno-Science.net
Partenaires
Organismes
 CEA
 ESA
Sites Web
Photo Mystérieuse

Que représente
cette image ?
 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | +
Fonction récursive primitive

Définition d'une fonction récursive primitive

On s'intéresse aux fonctions définies sur l'ensemble \mathbb N des entiers naturels, ou sur les ensembles \mathbb N^k des k-uplets d'entiers naturels, et à valeurs dans \mathbb N.

On construit les fonctions récursives primitives de proche en proche en partant des trois fonctions de base :

  • La fonction identiquement nulle
  • La fonction Successeur : Succ(t) = t + 1
  • Les projections : (x_1, ..., x_k) \rightarrow x_i

et en itérant les deux constructions suivantes :

  • La composition de fonctions : si g1, g2, ..., gk sont récursives primitives sur \mathbb N^n et si h est récursive primitive sur \mathbb N^k, toutes déjà définies, alors la fonction f = h(g1,...,gk) est une nouvelle fonction récursive primitive (On s'intéresse aux fonctions définies sur l'ensemble des entiers naturels, ou sur les ensembles des k-uplets d'entiers naturels, et à valeurs dans .) définie sur \mathbb N^n.
  • La définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) récursive d'une fonction : Si g est récursive primitive sur \mathbb N^n, et h récursive primitive sur \mathbb N \times \mathbb N \times \mathbb N^n, on définit une nouvelle fonction récursive (En informatique et en mathématiques, le terme fonction récursive désigne deux concepts liés, mais distincts. Plus généralement les termes « récursif », « récursivement », « récursion »,...) primitive sur \mathbb N^{n+1} par :
f(0,\vec y) = g(\vec y)
f(Succ(x),\vec y) = h(x,f(x,\vec y),\vec y)

Programmation (La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une étape importante de la conception de logiciel (voire de matériel,...)

Les fonctions récursives primitives se programment dans tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) langage de programmation (Un langage de programmation est un code de communication, permettant à un être humain de dialoguer avec une machine en lui soumettant des instructions...), à l'aide d'une simple instruction (Une instruction est une forme d'information communiquée qui est à la fois une commande et une explication pour décrire l'action, le comportement, la méthode ou la tâche qui devra...) itérative for :

function f(x,y)
z := g(y)
for i from 0 to x-1 do z := h(i,z,y) od
return(z)

Il n'y a pas de boucles while et le calcul des fonctions récursives primitives se termine toujours.

Exemples

Prédécesseur d'un entier

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 (La projection cartographique est un ensemble de techniques permettant de représenter la surface de la Terre dans son ensemble ou en partie sur la surface plane d'une carte.) sur la première composante.

Somme de deux entiers

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.

Somme de fonctions récursives primitives

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

Produit de deux entiers

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.

Produit de fonctions récursives primitives

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

Signe d'un entier

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.

Différence tronquée

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 (Un nombre réel est constitué de deux parties: un signe + ou - et une 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).

Prédicats récursifs primitifs

Définition

A tout prédicat (Les prédicats d’une théorie sont les formules qui contiennent des variables libres.) défini sur \mathbb N^k, on peut associer sa fonction caractéristique :

f(\vec x) = 1 \; {\rm si} \; P(\vec x) \; {\rm vrai}
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 (On rencontre des fonctions caractéristiques dans plusieurs domaines :) 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).

Exemples

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 (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) premier
x mod y = z

Quantification bornée

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

\forall x \le n, P(x,\vec y)
\exists x \le n, P(x,\vec y)

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

\prod_{x=0}^n f(x,\vec y)
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 \forall x, P(x,\vec y) et \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 2006) la valeur de vérité (La notion de valeur de vérité consiste à attribuer aux énoncés des valeurs numériques au travers de fonctions dont il faudra définir les règles de composition :...) de ce dernier prédicat.

Minimisation bornée

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

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

est récursive primitive.

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

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 (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension métonymique, la recherche scientifique désigne également le...) du minimum. La fonction cherchant le plus petit x vérifiant 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 n'est pas récursive primitive.

Limites de la récursion primitive

Une première limitation de la récursion primitive intervient dans les algorithmes susceptibles de ne pas se terminer. Tel est le cas de la quantification non bornée ou de la minimisation non bornée, vues précédemment.

Mais il ne suffit qu'une fonction soit définie récursivement, et par un procédé se terminant pour toute valeur des données, pour que la fonction soit récursive primitive. L'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une...) des fonctions récursives primitives n'est en effet qu'une partie de l'ensemble des fonctions récursives. Ainsi, 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. Pourtant la définition doublement récursive de cette fonction permet en théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une...) de calculer sa valeur pour tout couple (n,p) d'entiers.

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))

Bien que la fonction minimum soit récursive primitive, ce n'est pas la définition précédente qui permet de le montrer.

Pour pouvoir réaliser ces programmes on doit passer (Le genre Passer a été créé par le zoologiste français Mathurin Jacques Brisson (1723-1806) en 1760.) un système plus puissant, comme le Système T (A l'instar de la récursion primitive ou le lambda-calcul, le Système T est un langage de programmation théorique. Il a été inventé par le logicien Kurt Gödel.) de Gödel par exemple.

Un problème indécidable

Indécidabilité (En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique.) de la récursion primitive

Nous avons vu, dans le paragraphe Limites de la récursion primitive, deux exemples de définitions récursives qui ne sont pas récursives primitives :

  • La fonction d'Ackermann, dont on peut montrer qu'elle n'est pas récursive primitive. Il n'existe aucune définition de la fonction d'Ackermann utilisant la récursion primitive.
  • La fonction minimum, qui, elle, est cependant 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. Etant donnée (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) une fonction, définie récursivement ou par un algorithme quelconque, est-il possible de déterminer par un processus automatique (L'automatique fait partie des sciences de l'ingénieur. Cette discipline traite de la modélisation, de l'analyse, de la commande et, de la régulation des systèmes dynamiques. Elle a pour...) 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 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 (En théorie de la calculabilité, le théorème de Rice dit que toute propriété non triviale (c.-à-d. qui n'est pas toujours vraie ou toujours fausse) sur la sémantique dénotationnelle d'un langage de programmation...), qui définit toute une classe de questions indécidables.

Démonstration (En mathématiques, une démonstration permet d'établir une proposition à partir de propositions initiales, ou précédemment...)

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 (De façon générale un codage permet de passer d'une représentation des données vers une autre.) numérique (Une information numérique (en anglais « digital ») est une information ayant été quantifiée et échantillonnée, par opposition à une information dite...) de l'algorithme ou de la machine de Turing qui les définit. On appellera φ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 f = φ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 gn de x définie par :

g_n(x) = \phi_n(n) \times 0

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

RP(gn) = 0 si et seulement si le calcul de φn(n) ne se termine pas.

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

function C(n)
if RP(gn) = 0
then return(0)
else while true do od
if

La fonction C fonctionne comme suit : si RP(gn) = 0, alors C(n) retourne la valeur 0. Mais si RP(gn) = 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 RP(gn) = 0, si et seulement si le calcul de φn(n) ne se termine pas.

C étant défini par algorithme possède un rang ( Mathématiques En algèbre linéaire, le rang d'une famille de vecteurs est la dimension du sous-espace vectoriel engendré par cette famille. Le théorème du rang lie le rang et la dimension du noyau d'une application...) c tel que C = φc. L'équivalence ci-dessus s'écrit alors :

Le calcul de φc(n) se termine si et seulement si le calcul de φn(n) ne se termine pas.

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

Le calcul de φc(c) se termine si et seulement si le calcul de φc(c) ne se termine pas.

ce qui est absurde.

Aboutissant à une contradiction (Une contradiction existe lorsque deux affirmations, idées, ou actions s'excluent mutuellement.), on en conclut que la procédure RP ne peut exister.

Exemple

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 (La conjecture de Syracuse ressemble à un jeu de calcul. On prend n’importe quel nombre entier plus grand que 1 (2, 3, 73, 153…); s’il est pair, on le divise par 2;...) 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 (Dans la langue française, le mot assertion (n,f) représente une vérité absolue : il définit une proposition reconnue comme vraie. -> voir Wiktionary).

Formalismes

La récursion primitive est un langage de programmation théorique qui a la propriété que tous les programmes écrits dans ce langage 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 (En mathématiques et en logique, une variable est représentée par un symbole. Elle est utilisée pour marquer un rôle dans une formule, un prédicat ou un algorithme. En statistiques, une variable peut...) 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 (L'addition est une opération élémentaire, permettant notamment de décrire la réunion de quantités ou l'adjonction de grandeurs extensives de même nature, comme les...) 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 (Le chiffre zéro (de l’italien zero, dérivé de l’arabe sifr, d’abord transcrit zefiro en italien) est un symbole marquant une position vide dans l’écriture des...). C'est une fonction constante.
  • le combinateur Succ d'arité un qui va associer à un combinateur son successeur
  • la ie projection : πin d'arité n qui va associer à un n-uplet (En mathématiques, si n est un entier naturel non nul alors un n-uplet est une collection de n objets tel qu'il soit possible de dire exactement celui qui est le premier élément,...) le ie élément.
  • l'application S(c;c1, ..., cn), c étant un combinateur d'arité n, et les ci 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(π11, S(Succ,π23))

Source: Wikipédia publiée sous licence CC-BY-SA 3.0.

Vous pouvez soumettre une modification à cette définition sur cette page. La liste des auteurs de cet article est disponible ici.