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

$\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 !
Qualité Numéro Titre
5 912 Fonctions récursives primitives et non primitives. Exemples.2021
5 913 Machines de Turing. Applications.2021
4 206 Théorèmes de point fixe. Exemples et applications. 2016
4 27 Décidabilité et indécidabilité. Exemples.2022
3 29 Langages rationnels et automates finis. Exemples et applications2022
Rajouter une version