In computability theory Kleene's recursion theorem, first proved by Stephen Kleene in 1938, is a fundamental result about the application of computable functions to their own descriptions. Recursion theory, or computability theory, is a branch of mathematical logic dealing with generalizations of the notion of computable function, and with related notions such as Turing degrees and effective descriptive set theory. ... Stephen Cole Kleene (January 5, 1909 – January 25, 1994) was an American mathematician whose work at the University of Wisconsin-Madison helped lay the foundations for theoretical computer science. ... 1938 (MCMXXXVIII) was a common year starting on Saturday (link will take you to calendar). ... It has been suggested that recursive function be merged into this article or section. ...

Suppose that φ is a scheme for describing partial recursive functions (e.g. a Gödel numbering or programming language), and that the function corresponding to description p is φ_p. If Q is a partial recursive function of two arguments, then there is a description p of a function of one argument such that In mathematical logic and computer science, the recursive functions are a class of functions from natural numbers to natural numbers which are computable in some intuitive sense. ... In formal number theory a Gödel numbering is a function which assigns to each symbol and formula of some formal language a unique natural number called a Gödel number (GN). ... Computer code (HTML with JavaScript) in a tool that uses syntax highlighting (colors) to help the developer see the purpose of each piece of code. ... In mathematical logic and computer science, the recursive functions are a class of functions from natural numbers to natural numbers which are computable in some intuitive sense. ...

In other words, for any computable function of two arguments, there is a program that takes one argument and evaluates the function in question, with its own description as the first argument and the given argument as the second. Note that this program does not have to read its description from an external source, such as a file; It can generate the required information about its description, in the chosen description scheme, by itself.

Proof: Let s₁₁ be given by the S-m-n theorem, and let n be a description of the function λx,y.Q(s₁₁(x, x), y). Let p = s₁₁(n, n). Then, The smn theorem or parameter theorem is a result of recursion theory. ...

A classic example is the function Q(x, y) = x. The corresponding program p in this case generates its own description when applied to any value. Such programs are known as quines. Although the proof of the theorem shows how to construct one quine, students sometimes challenge themselves to find simpler ones. In computing, a quine is a program (a form of metaprogram) that produces its complete source code as its only output. ...

Generalized theorem by A.I. Mal'tsev

A.I. Mal'tsev proved a generalized version of the recursion theorem for any set with a precomplete numbering. A Gödel numbering is a precomplete numbering on the set of computable functions so the generalized theorem yields the Kleene recursion theorem as a special case. Anatoly Ivanovich Malcev Anatoly Ivanovich Maltsev (Malcev) (Russian: Анато́лий Ива́нович Ма́льцев 27 November N.S./14 November O.S. 1909 - 7 June 1967) was born in Misheronsky, near Moscow, and died in Novosibirsk, USSR. He was a mathematician noted for his work on the decidability of various algebraic groups. ... In computability theory complete numberings are generalizations of Gödel numbering first introduced by A.I. Maltsev in 1963. ...

Given a precomplete numbering ν then for any partial computable function f with two parameters there exists a total computable function r with one parameter so that

Example

With a Lisp interpreter, it is straightforward to implement the construction in the proof. Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ...

 ; Q can be changed to any two-argument function. (setq Q '(lambda (x y) x)) (setq s11 '(lambda (f x) (list 'lambda '(y) (list f x 'y)))) (setq n (list 'lambda '(x y) (list Q (list s11 'x 'x) 'y))) (setq p (eval (list s11 n n))) ; The results of the following expressions should be the same. ; φp(nil) (eval (list p nil)) ; Q(p,nil) (eval (list Q p nil)) 

References

• Kleene, Stephen, "On notation for ordinal numbers," The Journal of Symbolic Logic, 3 (1938), 150-155.