Développement : Théorèmes de point fixe de Kleene et application

Détails/Enoncé :

$\underline{Thm \ 1}$ : Soient $p>0$ et $\alpha : \mathbb{N} \to \mathbb{N}$ une fonction récursive alors il existe $i \in \mathbb{N}$ tel que : $\Phi_i^{p}=\Phi_{\alpha(i)}^p$.

$\underline{Thm \ 2}$ : Soit $p>0$, il existe une fonction $h_p$ récursive primitive tel que pour tout $j \in \mathbb{N}$, si $\Phi_j^{1}$ est totale alors $\Phi_{\Phi_j^1(h_p(j))}^p=\Phi_{h_p(j)}^p$.

$\underline{Thm \ 3}$ : Soient $p>0, \ n>0$, et $\alpha :\mathbb{N}^{p+1}\to \mathbb{N}$ une fonction récursive totale. Alors il existe une fonction $h : \mathbb{N}^p \to \mathbb{N}$ récursive primitive tel que pour tout $x_1,...,x_p \in \mathbb{N}$, $\Phi_{\alpha(x_1,...,x_p,h(x_1,...,x_p))}^n=\Phi_{h(x_1,...,x_p)}^n$.

$\underline{Application}$ : La fonction d'Ackermann est récursive !

Versions :

Pas de version pour ce développement.