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.
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 and appear in his 1952 book Introduction to Metamathematics.
A related theorem, which constructs fixed points of a computable function, is known as Rogers's theorem and is due to Hartley Rogers, Jr. 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. But, because e is an index of F \circ h , \varphi_e(e) = (F \circ h)(e) = F(h(e)) , and thus \varphi_{h(e)} \simeq \varphi_{F(h(e))} .
Hence \varphi_n \simeq \varphi_{F(n)} for n = h(e) . This proof is a construction of a partial recursive function that implements the Y combinator. The theorem can be proved from Rogers's theorem by letting F be a function such that \varphi_{F(p)}(y) = Q(p,y) (a construction described by the theorem). One can then verify that a fixed-point of this F is an index p as required.
The theorem is constructive in the sense that a fixed computable function maps an index for Q into the index p . A classic example using the second recursion theorem 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.
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 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. \varphi p(nil) (eval (list p nil)) Q(p, nil) (eval (list Q p nil)) \Phi(X) = \{ n \mid \exists A \subseteq X [(A,n) \in \Phi]\}. A recursive operator is an enumeration operator that, when given the graph of a partial recursive function, always returns the graph of a partial recursive function.
A fixed point of an enumeration operator Φ is a set F such that Φ(F) = F. The first enumeration theorem shows that fixed points can be effectively obtained if the enumeration operator itself is computable. First recursion theorem. The following statements hold.
For any computable enumeration operator Φ there is a recursively enumerable set F such that Φ(F) = F and F 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.
The first recursion theorem is also called Fixed point theorem (of recursion theory). There is also a definition that can be applied to recursive functionals as follows: Let \Phi: \mathbb{F}(\mathbb{N}^k) \rightarrow (\mathbb{N}^k) be a recursive functional.
Then \Phi has a least fixed point f_{\Phi}: \mathbb{N}^k \rightarrow \mathbb{N} which is computable i.e. 1) \Phi(f_{\phi})=f_{\Phi} 2) \forall g \in \mathbb{F}(\mathbb{N}^k) such that \Phi(g)=g it holds that f_{\Phi}\subseteq g 3) f_{\Phi} is computable Consider the recursion equations for the factorial function f: \begin{align} &f(0) = 1 \\ &f(n+1) = (n + 1) \cdot f(n) \end{align} The corresponding recursive operator Φ will have information that tells how to get to the next value of f from the previous value. However, the recursive operator will actually define the graph of f. First, Φ will contain the pair ( \varnothing, (0, 1)) .
This indicates that f(0) is unequivocally 1, and thus the pair (0,1) is in the graph of f. Next, for each n and m, Φ will contain the pair ( \{ (n, m) \}, (n+1, (n+1)\cdot m)) . This indicates that, if f(n) is m, then is , so that the pair is in the graph of f. Unlike the base case , the recursive operator requires some information about f(n) before it defines a value of . The first recursion theorem (in particular, part 1) states that there is a set F such that .
The set F will consist entirely of ordered pairs of natural numbers, and will be the graph of the factorial function f, as desired. The restriction to recursion equations that can be recast as recursive operators ensures that the recursion equations actually define a least fixed point.
For example, consider the set of recursion equations: \begin{align} &g(0) = 1\\ &g(n + 1) = 1\\ &g(2n) = 0 \end{align} There is no function g satisfying these equations, because they imply g(2) = 1 and also imply g(2) = 0. Thus there is no fixed point g satisfying these recursion equations.
It is possible to make an enumeration operator corresponding to these equations, but it will not be a recursive operator. The proof of part 1 of the first recursion theorem is obtained by iterating the enumeration operator Φ beginning with the empty set. First, a sequence F k is constructed, for k = 0, 1, \ldots .
Let F 0 be the empty set. Proceeding inductively, for each k, let F k + 1 be F_k \cup \Phi(F_k) . Finally, F is taken to be \bigcup F_k . The remainder of the proof consists of a verification that F is recursively enumerable and is the least fixed point of Φ. The sequence F k used in this proof corresponds to the Kleene chain in the proof of the Kleene fixed-point theorem.
The second part of the first recursion theorem follows from the first part. The assumption that Φ is a recursive operator is used to show that the fixed point of Φ is the graph of a partial function.
The key point is that if the fixed point F is not the graph of a function, then there is some k such that F k is not the graph of a function. \forall n \in \mathbb{N} : \nu \circ f(n,t(n)) = \nu \circ t(n).
Text derived from https://en.wikipedia.org/w/index.php?oldid=1353842766 under CC BY-SA 4.0; modifications have been made.