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. Énoncés Théorème de récursion Un des théorèmes de récursion s'énonce comme suit : Théorème de point fixe 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. Formulation avec les énumérations de fonctions récu
À 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.
Publications associées

Aucun résultat

Personnes associées

Aucun résultat

Unités associées

Aucun résultat

Concepts associés

Aucun résultat

Cours associés

Chargement

Séances de cours associées

Chargement