Théorème de récursion de Kleene

Cet article est une ébauche concernant la logique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Consultez la liste des tâches à accomplir en page de discussion.

En théorie de la calculabilité, plusieurs théorèmes dus à Kleene sont appelés théorèmes de la récursion. Ils établissent l'existence de points fixes pour des transformateurs^[1] de programmes, au sens où le programme et le programme image calculent la même fonction partielle et ils sont nommés également théorèmes du point fixe de Kleene. Ils ont de nombreuses applications.

Énoncés modifier

Théorème de récursion modifier

Un des théorèmes de récursion s'énonce comme suit^{[réf. nécessaire]} :

un programme a accès à sa propre description (i.e. à son propre code source).

Théorème de point fixe modifier

Un théorème de point fixe peut alors être présenté comme corollaire du théorème de récursion par Sipser^[1] :

Soit t une fonction calculable. Il existe alors une machine de Turing F telle que t(<F>) décrit une machine de Turing équivalente à F.

En effet, le théorème de récursion ci-dessus permet de donner une description de F :

F(w)
      Obtenir sa propre description <F> (grâce au théorème de récursion)
      Calculer t(<F>)
      Simuler la machine t(<F>) sur w

Par construction, F et t(<F>) sont des machines équivalentes.

Formulation avec les énumérations de fonctions récursives modifier

Si $\varphi {}$ est une énumération acceptable des fonctions récursives 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)$ .

Autre formes modifier

Ce théorème peut être décliné sous différentes formes dont l'une des plus célèbres est due à 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étrée

Il existe une fonction calculable $n$ telle que pour tout $x$ et $y$ , $\varphi _{n(y)}(x)=\varphi _{\varphi _{y}(n(y))}(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 à Raymond Smullyan.

Démonstration modifier

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.^{[réf. nécessaire]}

Applications modifier

Programmes minimaux modifier

On dit qu'un programme est minimal s'il n'existe pas de programmes équivalents avec un code source plus court). Savoir si un programme est minimal n'est pas récursivement énumérable.

Nous le démontrons par l'absurde. Supposons qu'il existe un programme E qui énumère les programmes minimaux (un tel programme s'appelle un énumérateur). On construit alors le programme C suivant :

C(w)
      Obtenir sa propre description <C> (grâce au théorème de récursion)
      Lancer l'énumérateur E jusqu'à ce qu'il écrive une description <D> d'une machine D, strictement plus longue que <C>
      Simuler D sur w

Il y a un nombre infini de programmes minimaux. Donc au bout d'un moment, E va écrire une description <D> plus longue que <C>. Mais C a le même comportement que D, donc D n'est pas minimal. Contradiction.

Existence de quines modifier

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 quines.

Bibliographie modifier

René Cori et Daniel Lascar, Logique mathématique II. Fonctions récursives, théorème de Gödel, théorie des ensembles, théorie des modèles [détail des éditions], chapitre 5.

Raymond Smullyan, Le livre qui rend fou, partie 3.

Références modifier

↑ ^{a et b} (en) Michael Sipser, Introduction to the Theory of Computation, Cengage Learning, 27 juin 2012, 504 p. (ISBN 978-1-285-40106-5 et 1-285-40106-9, lire en ligne).

[:0-1] {a et b} (en) Michael Sipser, Introduction to the Theory of Computation, Cengage Learning, 27 juin 2012, 504 p. (ISBN 978-1-285-40106-5 et 1-285-40106-9, lire en ligne).

[1]