Théorème de récursion de Kleene
Un article de Freepedia.
Sommaire |
Théorème de récursion de Kleene
Pour une énumération de fonction récursive
Si <math>\varphi</math> est un enumération acceptable des fonctions recursives et <math>f</math> une fonction partielle récursive alors il existe un indice <math>{\mathbf{e}}</math> tel que
<math>\varphi_{\mathbf{e}}(x)=f(\mathbf{e},x)</math>.
Pour un langage de de programmation
Si <math>\varphi</math> est un langage de programmation acceptable et <math>f</math> une fonction semi-calculable alors il existe un programme <math>{\mathbf{e}}</math> tel que pour tout <math>x</math>
<math>\varphi_{\mathbf{e}}(x)=f(\mathbf{e},x)</math>.
Autre formes
Ce théorème peur être décliné sous différentes formes dont l'une des plus célèbre est dues à H. Rogers. On onsidère un langage de programmation acceptable <math>\varphi</math>.
Forme de Rogers
Si <math>f</math> une fonction calculable alors il existe un programme <math>{\mathbf{e}}</math> tel que pour tout <math>x</math> <math>\varphi_{\mathbf{e}}(x)=\varphi_{f(\mathbf{e}}(x)</math>.
Paramétrisée
Il existe une fonction calculable <math>n</math> telle que tel que pour tous <math>x</math> et <math>y</math>. <math>\varphi_{n(z)}(x)=\varphi_{\varphi_{z}(n(z))}(x)</math>.
Récursion double
Si <math>f</math> et <math>g</math> sont des fonctions calculables alors il existe deux programmes <math>{\mathbf{e_1}}</math> et <math>{\mathbf{e_2}}</math> tels que pour tout <math>x</math>
<math>\varphi_{\mathbf{e_1}}(x)=\varphi_{f(\mathbf{e_1},\mathbf{e_2}}(x)</math>
<math>\varphi_{\mathbf{e_2}}(x)=\varphi_{g(\mathbf{e_1},\mathbf{e_2}}(x)</math>.
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 <math>s(x,x)</math> 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.
Applications
Ce théorème est reconnue comme le meilleur outil permettant de produire contre-exemples et cas pathologiques. En particulier, il fournit l'existance de programmes calculant leurs propres codes. En prenant <math>f</math> la première projection, <math>f(y,x)=y</math> et en appliquant le théorème ont obtient un programme <math>{\mathbf{e}}</math> tel que pour tout <math>x</math>
<math>\varphi_{\mathbf{e}}(x)=\mathbf{e}</math>.
L'exécution du programme <math>\mathbf{e}</math> produit son propre code. De tels programmes sont communément appelés quines.
