Concept# Kleene's recursion theorem

Summary

In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions. The theorems were first proved by Stephen Kleene in 1938 and appear in his 1952 book Introduction to Metamathematics. A related theorem, which constructs fixed points of a computable function, is known as Rogers's theorem and is due to Hartley Rogers, Jr.
The recursion theorems can be applied to construct fixed points of certain operations on computable functions, to generate quines, and to construct functions defined via recursive definitions.
Notation
The statement of the theorems refers to an admissible numbering \varphi of the partial recursive functions, such that the function corresponding to index e is \varphi_e.
If F and G are partial functions on the natural numbers, the notation F \simeq G indicates that, for each n, eith

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications

No results

Related people

Related courses

Related lectures

No results

No results

No results

Related units

No results

Related concepts

No results