Développement #548

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

Contenu : $\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$.\r\r$\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$.\r\r$\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$.\r\r$\underline{Application}$ : La fonction d'Ackermann est récursive !

Créé le : 23/07/2026 12:42

Mis à jour : 23/07/2026 12:42