Fonctions Récursives

Approche basée sur les fonctions définies sur les nombres naturels pour caractériser celles qui sont calculables par une procédure effective.

Fonctions calculables connues :

- les fonctions de base dont un algorithme est connu pour les calculer sur une représentation ;

- la composition finie de fonctions de base ;

- la récursion (… en partie).

Exemple : Exemples de fonctions récursives :

- + et x sur les réels,

- la factorielle,

- la racine carré d’un réel positif par la méthode de Newton

Fonctions récursives primitives

def Les fonctions récursives primitives simples sont :

- la fonction \overline{0},

- les fonctions de projection π_{i}^{k} = (λn_{1} … n_{k} n_{i}),

- la fonction successeur (λn (σ n)).

def La composition de la fonction g à l arguments et des fonctions h_{1}, …, h_{l} à k arguments est la fonction f à k arguments définie par : (λn_{1} … n_{k} (g (h_{1} n_{1} … n_{k}) … (h_{l} n_{1} … n_{k}))).

def La récursion primitive à partir des fonctions g à k arguments et h à k + 2 arguments est la fonction f à k + 1 arguments définie par :

(λ n_{1} … n_{k}m (if (m = (σ m′))
then (h (f n_{1} … n_{k} m′) n_{1} … n_{k} m′)
else (g n_{1} … n_{k})))

Fonctions récursives primitives (suite)

def Les fonctions récursives primitives sont définies inductivement par :

- les fonctions récursives primitives simples,

- la composition et la récursion primitive.

Exemple : Les fonctions constantes \overline{j} sont des fonctions primitives récursives : \overline{j} = \underbrace{(σ (σ … (σ \overline{0})))}_{j fois}.

Exemple : L’addition, la soustraction et la multiplication sur les naturels sont des fonctions récursives primitives.

Exemple : La factorielle est une fonction récursive primitive.

Exemple : Le produit borné par m d’une fonction (λn_{1} … n_{k}i (g n_{1} … n_{k} i)) défini par le produit de g pour les m premières valeurs de i est une fonction récursive primitive.

Les prédicats récursifs primitifs

def Un prédicat à k arguments est un sous-ensemble de ℕ^{k}.

def La fonction caractéristique d’un prédicat P ⊆ ℕ^{k} est la fonction f_{P} de ℕ^{k} dans {0, 1} définie par :

\begin{matrix}(f_{P} n_{1} … n_{k}) = & \overline{0} si (n_{1}, …, n_{k}) ∉ P \\ \overline{1} & sinon \end{matrix}

def Un prédicat est récursif primitif si sa fonction caractéristique est récursive primitive.

Exemple : Le prédicat nonzero qui est vrai sauf si son argument est l’entier 0 a pour fonction caractéristique f_{\overline{0̸}} :

(λm (if (m = (σ m′))
then (π_{3}^{3} (f_{\overline{0̸}} m′) m′ \overline{1})
else \overline{0}))

Exemple : Écrire les fonctions caractéristiques (récursives primitives) des prédicats et, ou et non.

Les prédicats récursifs primitifs (suite)

def La quantification bornée universelle teste si un prédicat est vrai pour toutes les valeurs d’un de ses arguments inférieures à une borne.

prop.: La quantification bornée universelle est un prédicat récursif primitif.

Soit f_{P} la fonction caractéristique du prédicat P à k+1 arguments. Alors la fonction caractéristique (récursive primitive) de la quantification bornée de P pour le k+1 argument ∀_{P}^{≤} est définie par : (λn_{1} … n_{k}m (if (m = (σ m′))

then (fois \begin{matrix}(π_{1}^{k+2} (∀_{P}^{≤} n_{1} … n_{k} m′) n_{1} … n_{k} m′) \\ (f_{P} n_{1} … n_{k} m′)) \end{matrix}

else (π_{1}^{k+2} \overline{1} n_{1} … n_{k} m′)))

Les prédicats récursifs primitifs (suite)

def La quantification bornée existentielle teste si un prédicat est vrai pour des valeurs d’un de ses arguments inférieures à une borne.

prop.: La quantification bornée existentielle est un prédicat récursif primitif.

def Pour une borne, la valeur de la fonction de minimisation bornée d’un prédicat (pour un de ses arguments) est le plus petit nombre naturel inférieur à la borne tel que le prédicat soit vrai :

μ_{P} i ≤ m = \{ \begin{matrix}le plus petit i ≤ m tel que \\ (n_{1}, …, n_{k}, i) ∈ P \\ 0 si il n’existe pas de tel i \end{matrix}

prop.: La minimisation bornée est une fonction récursive primitive.

Les fonctions μrécursives

Th.: Il existe des fonctions calculables qui ne sont pas primitives récursives.

def La valeur de la fonction de minimisation non bornée d’un prédicat (pour un de ses arguments) est le plus petit nombre naturel tel que le prédicat soit vrai.

remarque : Dans le cas d’un prédicat toujours faux, la minimisation non bornée n’est pas calculable car ne termine jamais.

def Un prédicat P est sûr si pour tout n_{1}, …, n_{k}, il existe un i tel que (n_{1}, …, n_{k}, i) ∈ P.

def Les fonctions μrécursives sont celles obtenues par induction sur les fonctions récursives primitives simples, la composition, la récursion primitive et la minimisation non bornée des prédicats sûrs.

Fonctions μrécursives et Machines de Turing

2 approches pour la définition des fonctions calculables par des procédures effectives : les fonctions μrécursives et les fonctions calculables par machine de Turing.

Question : Les fonctions μrécursives sont-elles exactement les fonctions calculables par une machine de Turing?

Fonctions μrécursives Machine de Turing
sur les naturels  sur les caractères

Problème de la représentation effective des nombres par des caractères et inversement : nécessité de procédures effectives de codage.

Nombres et caractères

lem.: Il existe une représentation effective des nombres naturels par des chaînes de caractères.

pr. inf.: Le codage binaire des naturels.

lem.: Il existe une représentation effective des chaînes de caractères par des nombres naturels.

def (la Gödelisation) La représentation d’une chaîne de caractère par un nombre de Gödel.

Exemple : Soit A un alphabet. Nous définissons une bijection gd de A dans {1, …, | A |}. Pour tout mot w = σ_{0} … σ_{l} ∈ A^{∗}, le nombre de Gödel de w est défini par :

Gd(w) = Σ_{i=0}^{l} (1+ |A|)^{l−i}gd(w_{i}).

Fonctions μrécursives ≡

machines de Turing

Th.: Toute fonction μrécursive est calculable par une machine de Turing.

pr. inf.: En adoptant un codage des entiers narurels, les fonctions primitives récursives simples, leurs compositions, leurs récursions primitives et leurs minimisations non bornées sûres sont calculables par une machine de Turing.

Th.: Toute fonction calculable par une machine de Turing est μrécursive.

pr. inf.: Soient une machine de Turing M sur un alphabet A calculant une fonction f_{M} de A^{∗} dans A^{∗} et une gödédisation Gd pour A^{∗}. Alors il existe une fonction μrécursive f telle que (∀w ∈ A^{∗}(f_{M}(w) = Gd^{−1}(f(Gd(w))))).

Fonctions partielles

def Une fonction partielle f de A^{∗} dans A^{∗} est calculée par une machine de Turing M si,

- pour tout mot d’entrée w tel que f soit définie, M s’arrête toujours dans une configuration ou se trouve f(w) sur le ruban ;

- pour tout mot d’entrée w tel que f ne soit pas définie, M ne s’arrête pas ou s’arrête sur une configuration conventionnelle.

def Une fonction partielle f de ℕ dans ℕ est μrécursive si elle est définie par induction sur les fonctions récursives primitives simples, la composition, la récursion primitive et la minimisation non bornée.

Th.: Une fonction partielle est μrécursive si et seulement si elle est calculable par une machine de Turing.