Kleene's Recursion Theorem states that for any computable function that transforms one program into another, there exists a program that computes the same function as the program it is transformed into, so that every such transformation has a fixed point among the programs. Named for Stephen Kleene, it is a foundational result of computability theory underlying self-referential constructions such as programs that access and act on their own source code.
Facts
StatementFor any partial recursive function Q of two arguments there is an index p such that the partial recursive function computed by program p is equivalent to the function sending y to Q(p, y), so a self-referential program can always be constructed for a given task. 1 Classification
Statement Form Connections
Has Statement Form
In Branch
Source Kleene's Recursion Theorem (Wikipedia)
Principal Result Of
Source Stephen Cole Kleene (Wikipedia)
Proved By
Source Kleene's Recursion Theorem (Wikipedia)
Sources
1. Kleene's Recursion Theorem (Wikipedia)
Wikimedia FoundationKleene's second recursion theorem section
One informal interpretation of the second recursion theorem is that it is possible to construct self-referential programs
lead section, second sentence
The theorems were first proved by Stephen Kleene in 1938 and appear in his 1952 book Introduction to Metamathematics.
In Branch: Computability Theory, Lead sentence
In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functio
Proved By: Stephen Cole Kleene, Lead paragraph
In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions.
In Group: Computability and Complexity Theory, Lead section
In computability theory, Kleene's recursion theorems are a pair of fundamental
View the Source Stephen Cole Kleene (Wikipedia)
Principal Result Of: Stephen Cole Kleene, Article textQuote, Principal Result Of: Stephen Cole Kleene, Article text
A number of mathematical concepts are named after him: Kleene hierarchy, Kleene algebra, the Kleene star (Kleene closure), Kleene's recursion theorem and the Kleene fixed-point theorem.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.