Kleene's recursion theorem: Difference between revisions

Revision as of 00:20, 16 March 2021

Revision as of 11:49, 23 April 2021

Line 2:

{{distinguish|text=[[Kleene's theorem]] for regular languages}}

{{Format footnotes|date=January 2021|reason=Parenthetical referencing has been [[WP:PARREF|deprecated]]; convert to [[Help:Shortened footnotes|shortened footnotes]].}}

In [[computability theory]], '''Kleene's recursion theorems''' are a pair of fundamental results about the application of [[computable function]]s to their own descriptions. The theorems were first proved by [[Stephen Cole Kleene|Stephen Kleene]] in 1938 and appear in his 1952 book ''[[#CITEREFKleene1952|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.]] {{harv|Rogers|1967}}.

The recursion theorems can be applied to construct [[fixed point (mathematics)|fixed points]] of certain operations on [[computable function]]s, to generate [[quine (computing)|quines]], and to construct functions defined via [[recursive definition]]s.

Line 28:

This proof is a construction of a [[partial recursive function]] which implements the [[Fixed-point combinator|Y combinator]].

=== Fixed-point -free functions ===

A function <math>F</math> such that <math> \varphi_e \not \simeq \varphi_{F(e)}</math> for all <math>e</math> is called '''fixed -point free'''. The fixed-point theorem shows that no total computable function is fixed -point free, but there are many non-computable fixed-point -free functions. '''Arslanov's completeness criterion''' states that the only [[recursively enumerable]] [[Turing degree]] that computes a fixed -point -free function is '''0&prime;''', the degree of the [[halting problem]] {{harv|Soare|1987|p=88}}.

== Kleene's second recursion theorem ==

Line 142:

In the context of his theory of numberings, [[Yury Yershov|Ershov]] showed that Kleene's recursion theorem holds for any [[precomplete numbering]] {{harv|Barendregt|Terwijn|2019|p=1151}}. 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. See {{harv|Ershov|1999|loc=§4.14}} for a survey in English.

Given a precomplete numbering <math>\nu</math>, then for any partial computable function <math>f</math> with two parameters there exists a total computable function <math>t</math> with one parameter such that

:<math>\forall n \in \mathbb{N} : \nu \circ f(n,t(n)) = \nu \circ t(n).</math>