Kleene's recursion theorem
Theorem in computability theory / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Kleene's recursion theorem?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
Not to be confused with Kleene's theorem for regular languages.
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[1] and appear in his 1952 book Introduction to Metamathematics.[2] A related theorem, which constructs fixed points of a computable function, is known as Rogers's theorem and is due to Hartley Rogers, Jr.[3]
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.