ok Encyclopédie - Théorème de récursion de Kleene & Video

Revue de presse Théorème_de_récursion_de_Kleene
shout shout

var wgScript = "/w/index.php"; var wgVariantArticlePath = false;

Théorème de récursion de Kleene

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

Le théorème de récursion de Kleene est un théorème important de la théorie de la calculabilité. Il permet d'établir l'égalité de fonctions calculables.

Sommaire

[] Formulation avec les énumérations de fonctions récursives

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

\varphi_}(x)=f(\mathbf,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 } tel que pour tout x

\varphi_}(x)=f(\mathbf,x).

[] 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 } tel que pour tout x \varphi_}(x)=\varphi_)}(x).

  • Paramétrisée

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

  • Récursion double

Si f et g sont des fonctions calculables alors il existe deux programmes } et } tels que pour tout x

\varphi_}(x)=\varphi_,\mathbf)}(x)

\varphi_}(x)=\varphi_,\mathbf)}(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 } tel que pour tout x

\varphi_}(x)=\mathbf.

L'exécution du programme \mathbf produit son propre code. De tels programmes sont communément appelés quines.


Mirror_ebab  

shout
Réagissez


Attention! tous les commentaites inaproprié seront supprimés
Titre:
Video YouTube ou google: (doit être en rapport avec le sujet)
Votre mail:
Un pseudo:
Votre site:
Commentaire (le html n'est pas autorisé, nombre de caractère maximum = 400)
  save (Comment eBabylone 1.0 beta)

Le Texte ci-dessus est disponible sous GNU Free Documentation License.
La source est wikipedia http://fr.wikipedia.org/wiki/ Théorème de récursion de Kleene
Base de liens  |  Ajouter lien  |  Contact Rss
On est 22 visiteur(s) en ligne
Server 2.0