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 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.
View the Source 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.