Kleene's recursion theorem

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.

This article uses the convention that $phi$ is a scheme for indexing partial recursive functions (that is, a Gödel numbering) and that the function corresponding to index "e" is $phi\_e$. The notation $f\; simeq\; g$ indicates that, for each input, the partial functions "f" and "g" are either both undefined or are both defined and share the same value.

The second recursion theorem

The second recursion theorem is closely related to definitions of computable functions using recursion. Because it is more well known than the first recursion theorem, it is sometimes called just the recursion theorem.

:The second recursion theorem. If "F" is a total recursive function then there is an index "e" such that $phi\_e\; simeq\; phi\_\{F(e)\}$.

For example, if "g" and "h" are computable functions then a recursive definition for a computable function such as

:$f(0,y)\; simeq\; g(y),,$

:$f(x+1,y)\; simeq\; h(f(x,y),x,y),,$

can be converted to a computable function "F(e)" that takes an index for a program "e" and returns an index "F(e)" such that

:$phi\_\{F(e)\}(0,y)\; simeq\; g(y),,$

:$phi\_\{F(e)\}(x+1,y)\; simeq\; h(phi\_e(x,y),x,y).,$

The recursion theorem says that there is an index "e" such that $phi\_e\; simeq\; phi\_\{F(e)\}$, in other words, an index for a computable function "f" satisfying the original recursion equations. Such a function is known as a fixed point of the recursion equations; the recursion theorem is sometimes called the Fixed point theorem for this reason. The theorem does not guarantee that "e" is an index for the smallest fixed point of the recursion equations; this is the role of the first recursion theorem described below.

Proof of the second recursion theorem

Let "f" be any computable function. Let "h" be a total computable function such that for all "x", if $phi\_x(x)$ halts then $phi\_\{h(x)\}\; =\; phi\_\{phi\_x(x)\}$, and if $phi\_x(x)$ doesn't halt then $phi\_\{h(x)\},$ doesn't halt (this is denoted $phi\_\{h(x)\}\; simeq\; phi\_\{phi\_x(x)\}$). Given input "x", the function "h" outputs the index of a program which first computes $phi\_\{x\}(x),$ and, if that computation gives an output, uses its output as the index of a computable function to be simulated. The function "h" can be constructed from partial computable function $g(x,y)=phi\_\{phi\_x(x)\}(y)$ and s-m-n theorem: for each "x", $h(x)$ is the index of a program which computes the function $y\; mapsto\; g(x,y)$.

Once "h" is constructed, take "e" to be an index of the composition $f\; circ\; h$, which is a total computable function. Then $phi\_\{h(e)\}\; simeq\; phi\_\{phi\_e(e)\}$ by the definition of "h".But, because "e" is an index of $f\; circ\; h$, $phi\_e(e)\; =\; (f\; circ\; h)(e)$, and thus $phi\_\{phi\_e(e)\}\; simeq\; phi\_\{f(h(e))\}$. Hence $phi\_n\; simeq\; phi\_\{f(n)\}$ for $n\; =\; h(e)$.

Application to Quines

One informal interpretation of the second recursion theorem is that any partial computable function can guess an index for itself. This follows from the following corollary of the theorem.

:Corollary. For any partial recursive function "Q"("x","y") there is an index "p" such that $phi\_p\; simeq\; lambda\; y.Q(p,y)$.

The corollary is proved by letting $F(p)$ be a function that gives an index for $lambda\; y.Q(p,y)$.

The corollary shows that for any computable function "Q" of two arguments there is a program that takes "one" argument and evaluates "Q" with the index of that very program as the first argument and the given argument as the second. Note that this program is able to generate its index from information built in to the program; it does not require any external resources in order to find the index.

A classic example is the function "Q"("x","y") = "x". The corresponding index "p" in this case yields a computable function that outputs its own index when applied to any value. When expressed as computer programs, such indices are known as quines. Although the proof of the theorem can be used to generate one quine, students sometimes challenge themselves to find simpler ones than the proof provides.

The following example in Lisp illustrates how the "p" in the corollary can be effectively produced from the function "Q". The function "s11" in the code is the function of that name produced by the S-m-n theorem.

; 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))

Fixed point free functions

A function "F" such that $phi\_e\; ot\; simeq\; phi\_\{F(e)\}$ for all "e" is called fixed point free. The recursion theorem asserts that no computable function is fixed point free. Arslanov's completeness criterion states that the only recursively enumerable Turing degree that computes a fixed point free function is 0′, the degree of the halting problem.

The first recursion theorem

The first recursion theorem is related to fixed points determined by enumeration operators, which are a computable analogue of inductive definitions. An enumeration operator is a set of pairs ("A","n") where "A" is a (code for a) finite set of numbers and "n" is a single natural number. Any enumeration operator Φ determines a function from sets of naturals to sets of naturals given by:$Phi(X)\; =\; \{\; n\; mid\; exists\; A\; subseteq\; X\; [(A,n)\; in\; Phi]\; \}$.These operators are important in the study of enumeration reducibility. A recursive operator is an enumeration operator which when given the graph of a partial recursive function always returns the graph of a partial recursive function.

:First recursion theorem. The following statements hold.:# For any computable enumeration operator Φ there is a recursively enumerable set "A" such that Φ("A") = "A" and "A" is the smallest set with this property.:# For any recursive operator Ψ there is a partial computable function φ such that Ψ(φ) = φ and φ is the smallest partial computable function with this property.

One difference between the first and second recursion theorems is that the fixed points obtained by the first recursion theorem are guaranteed to be least fixed points, while those obtained from the second recursion theorem may not be least fixed points. Rogers [1967] uses the term weak recursion theorem for the first recursion theorem and strong recursion theorem for the second recursion theorem.

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.

Given a precomplete numbering $u$ then for any partial computable function $f$ with two parameters there exists a total computable function $t$ with one parameter such that

:$forall\; n\; in\; mathbb\{N\}\; :\; u\; circ\; f(n,t(n))\; =\; u\; circ\; t(n).$

References

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

* Rogers, H. "The Theory of Recursive Functions and Effective Computability", MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1

See also

* Denotational semantics, where another least fixed point theorem is used for the same purpose as the first recursion theorem.
* Fixed point combinators, which are used in lambda calculus for the same purpose as the first recursion theorem.
* The Church-Turing thesis, by which all these approaches act on equivalent fields.