Cours 5 : Fonctions récursives/récursives primitives/récursives partielles, Hiérarchie de Grzegorczyk, Fonction d’Ackermann

Fonctions récursives

Fonctions récursives

fonctions de $ℕ^k ⟶ ℕ$

Fonctions récursives primitives

Ensemble des fonctions récursives primitives :

Le plus petit ensemble tel que :

contient les fonctions :
- $Z: ℕ⟶ℕ, n \mapsto 0$
- $S: ℕ⟶ℕ, n \mapsto n+1$
- $𝜋_n^i: ℕ^n⟶ℕ, (x_1, ⋯, x_n) \mapsto x_i$
- $0: ℕ^0⟶ℕ, \mapsto 0$
clos par composition : $g(f_1(x_1, ⋯, x_m), ⋯, f_k(x_1, ⋯, x_m))$ (noté $Comp_m(g, f_1, ⋯, f_k)$) reste réc. prim. si $f : ℕ^m⟶ℕ$ et $g: ℕ^k ⟶ ℕ$ le sont
clos par récursion primitive : $f(x, n_1, ⋯, n_k) = \begin{cases} g(n_1, ⋯, n_k) \text{ si } x=0 \\ h(f(x-1, n_1, ⋯, n_k), x-1, n_1, ⋯, n_k)\text{ sinon} \end{cases}$ à $k+2$ arguments (si $g$ à $k$, $h$ à $k+1$ arguments)
$f$ est notée $Prim(g,h)$

NB :

Ce sont toutes les fonctions qu’on peut ne coder qu’avec des boucles for
Elles sont moins expressives que les fonctions calculables : certaines fonctions calculables ne sont pas réc. prim.

EX :

l’addition $+$ est primitive :
- $+ = Prim(𝜋_1^1, Comp_3(S, 𝜋_3^1))$
multiplication :
- $× = Prim(Z, Comp(+, 𝜋_3^1, 𝜋_3^3))$

Hiérarchie de Grzegorczyk

$𝜓_n$ par réc :

$𝜓_0(m) = m+1$
$𝜓_{n+1}(m) = \begin{cases} 𝜓_n(1) \text{ si } m=0
𝜓_n(𝜓_{n+1}(m-1)) \text{ sinon} \end{cases}$

Intuitivement : $𝜓_{n+1}(m) = 𝜓_n^m(1)$

$𝜓_1(n) = n+2$
$𝜓_2(n) = 2n+3$
$𝜓_3(n) = 2^{n+3}-3$
$𝜓_4(n) = 2\uparrow (n+3) -3$

Théorème :

Si $f$ est réc. prim., il existe $n$ tq :$∀n_1, ⋯, n_k, f(n_1, ⋯, n_k) ≤ 𝜓_n(\max n_i)$

Par réc. sur le nb de $Prim$ et de $Comp$ utilisés pour définir $f$

DONC :

$n \mapsto 𝜓_n(n)$ n’est pas réc. prim.
$Ack(n,m) = 𝜓_n(m)$

Théorème : $Ack$ est récursive et pas réc. prim.

Ack(n,m) =
  | m+1 si n=0
  | Sinon :
    Si m=0 :
      Ack(n-1,1)
    sinon
      Ack(n-1, Ack(n, m-1))

Ex :

$h: ℕ⟶ℕ$ : itération de $h$, $f(n,x)$

\[f(n,x) = \begin{cases} x \text{ si } n=0 \\ h(f(n-1, x)) \text{ sinon} \end{cases}\]

Mq l’ensemble des fonctions récursives primitives est le + petit ensemble de fonctions de $ℕ^k⟶ℕ$ clos par composition, itération, contenant les fonctions de base $J, K, L$

$J$ : bijection de $ℕ^2 ⟶ ℕ$, $J(x,y) = \frac{(x+y)(x+y+1)}{2} + y$ (autre ex : $J(x,y) = 2^x(2y+1)$)

\[K(J(x,y)) = x \\ L(J(x,y)) = y\]

Fonctions récursives partielles

Fonctions récursives partielles :

plus petit ensemble de fonctions de $ℕ^k⟶ℕ$

qui contient les fonc. rec. prim
clos par minimisation : $f(\vec{n}) = \min \{x \vert g(\vec{n},x) = 0\}$ est rec. partielle si $g$ est rec partielles ($\min = \bot$ si non défini)
qui est clos par composition et rec. prim.

NB: ce sont les focntions qu’on peut écrire avec des boucles while : i.e peuvent ne pas terminer.

Th : $Ack$ est réc. totale

(i.e rec partielle définie pour tous ses arguments)

Dém : on utilise une minimisation :

Le graphe de la fonction $Ack$ est réc. prim, i.e la fonction :
- \[𝜒_{Ack} = \begin{cases} ℕ^3 ⟶ ℕ \\ (n, m, p ) \mapsto \begin{cases} 1 \text{ si } p=Ack(n,m) \\ 0 \text{ sinon} \end{cases} \end{cases}\]

Heuristique : on veut transformer les boucles while en for, en trouvant un majorant du nombre de passages. On donne une borne

\[Ack(n,m)= \min\{p \vert 𝜒_{Ack}(n,m,p)=1\}\]

Th : Une fonction $f : ℕ^k ⟶ ℕ$ est réc. partielle (resp. totale) ssi ∃ une MT $M_f$ à $k+1$ rubans tq, sur la donnée $n_1, ⋯, n_k$ (en base 2) :

s’arrête avec $f(n_1, ⋯, n_k)$ sur le ruban $k+1$ si $f(n_1, ⋯, n_k) ≠ \bot$

boucle si $f(n_1, ⋯, n_k) = \bot$

Corollaire : $E$ est réc én ssi $𝜒_E$ est réc partielle (⟺ calculable)

⟹ : Mq l’ensemble des fonctions “calculées” partielles par MT:

contient les fonctions de base
est clos par récursion primitive, composition, et minimisation.

Clôture par réc prim :

\[f(x, \vec{n})\begin{cases} g(\vec{n}) \text{ si } x=0 \\ h(f(x-1, \vec{n}), x, \vec{n}) \text{ sinon} \end{cases}\]

$M_g, M_h ⟶ M_f$

1) $M_g$ à $\vec{n}$ : résultat $z$ 2)

for i=1 to x do
  z := M_h(z, i, n)

Clôture par composition :

$f(\vec{n}) = g(h_1(\vec{n}), ⋯, h_k(\vec{n}))$

$M_{h_1}, ⋯, M_{h_k}, M_g$ (utiliser $\vert \vec{n}\vert +k+1$ rubans)

Clôture par minimisation :

\[f(\vec{n}) = \min \{x \vert g(\vec{n},x) = 0\}\]

$M_g ⟶ M_f$ :

while g(i, n) <> 0 do
  i++

⟸ : $𝛾$ config ⟶ $𝛾’$ config suivante : est réc. prim

$(q, w_1, w_2) ∈ ℕ$, $\overline{w_i}$ entier en base $\vert 𝛴\vert +1$

Première lettre de $w_2$ : $\overline{\widetilde{w_1}}$
- c’est le reste $\mod \vert 𝛴\vert +1$
reste de $w_2$
- c’est la division entière par $\vert 𝛴\vert +1$
Concaténer $a$ à $w$
- multiplication de $w$ par $\vert 𝛴\vert +1$, puis $+a$

De plus, la fonction “case” est réc prim :

\[f(\vec{x}) = \begin{cases} n_1 \mapsto f_1(\vec{x}) \\ \vdots \\ n_k \mapsto f_k(\vec{x}) \\ \text{ sinon} \mapsto 0 \end{cases}\]

Dém : c’est le cas pour une seule condition, puis on conclut par une réc immédiate :

if f(x) then g(x) else h(x)

$≝ f(\vec{x}) × g(\vec{x}) + (1- f(\vec{x})) h(\vec{x})$

\[g(m, \vec{n}) = \begin{cases} \vec{𝛾_m} \text{ si $m$-ième config de } M \\ 0 \text{ si a machine s'est arrêtée} \end{cases} = \begin{cases} 𝛾_0(\vec{n}) \text{ si } m=0 \\ next(g(m-1, \vec{n})) \text{ sinon} \end{cases}\]

Si $M$ calcule $g$ :

\[f(\vec{n}) = Decode(\underbrace{g(\min \{x \vert g(x, \vec{n}) = 0\} - 1}_{\text{nb d'étapes de calcul de $M$ sur $f$}}, \vec{n}))\]

Corollaire (Kleene) : Toutes les fonctions réc partielles s’obtiennent avec une seule minimisation

Dém : car, dans la preuve précédente : $g$ est réc prim.

NB : Dans un programme, on ne peut peut-être pas se passer de plusieurs boucles for, mais on peut n’utiliser qu’une seule boucle while.

Avec la logique du premier ordre : on peut définir la minimisation :

\[f(\vec{x}) = \min \{n \vert g(n, \vec{x}) = 0\} ≝ z\\ 𝜑_g(\vec{x},z) = 𝜑_g(z, \vec{x},0) ∧ ∀y, y<z ⟹ \lnot 𝜑_g(z,\vec{x},0)\]

$𝒞$ = le plus petit ensemble de fonctions de $ℕ^k⟶ℕ$ tq $𝒞$

contient les fonctions de base, et +, ×, =
est close par composition et minimisation

Th : $𝒞$ est l’ensemble des fonctions réc. partielles.

Lemme :

$≥ ∈ 𝒞$
$∧, ∨, ¬ ∈ 𝒞$
$J, K, L ∈ 𝒞$

On code le quantificateur universel, mais borné

Lemme : Fonction $𝛽$ de Gödel.

Share on

Twitter Facebook Google+ LinkedIn