Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Théorème de récursion de Kleene
Résumé
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 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.
Un des théorèmes de récursion s'énonce comme suit :
Un théorème de point fixe peut alors être présenté comme corollaire du théorème de récursion par Sipser :
En effet, le théorème de récursion ci-dessus permet de donner une description de F :
F(w)
Obtenir sa description propre description (grâce au théorème de récursion)
Calculer t()
Simuler la machine t() sur w
Par construction, F et t() sont des machines équivalentes.
Si est une énumération acceptable des fonctions récursives et une fonction partielle récursive alors il existe un indice tel que
Pour un langage de programmation
Si est un langage de programmation acceptable et une fonction semi-calculable alors il existe un programme tel que pour tout
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 .
Forme de Rogers
Si est une fonction calculable alors il existe un programme tel que pour tout ,
Paramétrée
Il existe une fonction calculable telle que pour tout et ,
Récursion double
Si et sont des fonctions calculables, alors il existe deux programmes et tels que pour tout ,
On doit le théorème de récursion double à Raymond Smullyan.
La démonstration de ce théorème utilise l'auto-référence 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.
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.