Théorème de récursion de Kleene

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

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

y

\varphi_{n(z)}(x)=\varphi_{\varphi_{z}(n(z))}(x)

Récursion double

f

g

sont des fonctions calculables alors il existe deux programmes

{\mathbf{e_1}}

{\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.

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 John von Neumann dans le cadre des automates cellulaires auto-reproducteurs.

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}$ .

L'exécution du programme $\mathbf{e}$ produit son propre code. De tels programmes sont communément appelés quiness.