Théorème de récursion de Kleene

Un article de Wikipédia, l'encyclopédie libre.

Sommaire

1 Théorème de récursion de Kleene
2 Autre formes
3 Remarque
4 Applications

[modifier] Théorème de récursion de Kleene

Pour une énumération de fonction récursive

Si $\varphi$ est un enumération acceptable des fonctions recursives et $f$ une fonction partielle récursive alors il existe un indice ${\mathbf{e}}$ tel que

$\varphi_{\mathbf{e}}(x)=f(\mathbf{e},x)$ .

Pour un langage de programmation

Si $\varphi$ est un langage de programmation acceptable et $f$ une fonction semi-calculable alors il existe un programme ${\mathbf{e}}$ tel que pour tout $x$

$\varphi_{\mathbf{e}}(x)=f(\mathbf{e},x)$ .

[modifier] Autre formes

Ce théorème peut être décliné sous différentes formes dont l'une des plus célèbre est dues à H. Rogers. On considère un langage de programmation acceptable $\varphi$ .

Forme de Rogers

Si $f$ est une fonction calculable alors il existe un programme ${\mathbf{e}}$ tel que pour tout $x$ $\varphi_{\mathbf{e}}(x)=\varphi_{f(\mathbf{e})}(x)$ .

Paramétrisée

Il existe une fonction calculable $n$ telle que pour tout $x$ et $y$ . $\varphi_{n(z)}(x)=\varphi_{\varphi_{z}(n(z))}(x)$ .

Récursion double

Si $f$ et $g$ sont des fonctions calculables alors il existe deux programmes ${\mathbf{e_1}}$ et ${\mathbf{e_2}}$ tels que pour tout $x$

$\varphi_{\mathbf{e_1}}(x)=\varphi_{f(\mathbf{e_1},\mathbf{e_2})}(x)$

$\varphi_{\mathbf{e_2}}(x)=\varphi_{g(\mathbf{e_1},\mathbf{e_2})}(x)$ .

On doit le théorème de récursion double à R. Smullyan.

[modifier] Remarque

La démonstration de ce théorème utilise l'auto-référence $s (x, x)$ produite par le théorème d'itération (théorème s-m-n). Cette notion d'autoréférence est très profonde et a été largement traitée par J. von Neumann dans le cadre des automates cellulaires auto-reproducteurs.

[modifier] Applications

Ce théorème est reconnu comme le meilleur outil permettant de produire contre-exemples et cas pathologiques. En particulier, il fournit l'existence de programmes calculant leurs propres codes. En prenant $f$ la première projection, $f (y, x) = y$ et en appliquant le théorème on obtient un programme ${\mathbf{e}}$ tel que pour tout $x$

$\varphi_{\mathbf{e}}(x)=\mathbf{e}$ .