Kleene's recursion theorem: Difference between revisions

Revision as of 16:35, 10 May 2018

Revision as of 08:25, 15 July 2018

Line 11:

== Rogers's fixed-point theorem ==

Given a function <math>F</math>, a '''fixed point''' of <math>F</math> is an index <math>e</math> such that <math>\varphi_e \simeq \varphi_{F(e)}</math>. Rogers (Rogers 1967: &sect;§11.2) describes the following result as "a simpler version" of Kleene's (second) recursion theorem.

:'''Rogers's fixed-point theorem'''. If <math>F</math> is a total computable function, it has a fixed point.

Line 28:

=== 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 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&acuteprime;''', the degree of the [[halting problem]] (Soare 1987, p.&nbsp;88)

== Kleene's second recursion theorem ==

Line 85:

== The first recursion theorem ==

While the second recursion theorem is about fixed points of computable functions, 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 ([[G&ouml;delGödel number|code]] for a) finite set of numbers and ''n'' is a single natural number. Often, ''n'' will be viewed as a code for an ordered pair of natural numbers, particularly when functions are defined via enumeration operators. Enumeration operators are of central importance in the study of [[enumeration reducibility]].

Each enumeration operator &Phi;Φ determines a function from sets of naturals to sets of naturals given by

:<math>\Phi(X) = \{ n \mid \exists A \subseteq X [(A,n) \in \Phi]\}.</math>

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 &Phi;Φ is a set ''F'' such that &Phi;Φ(''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 &Phi;Φ there is a recursively enumerable set ''F'' such that &Phi;Φ(''F'') = ''F'' and ''F'' is the smallest set with this property.

:# For any recursive operator &Psi;Ψ there is a partial computable function &phi;φ such that &Psi;Ψ(&phi;φ) = &phi;φ and &phi;φ is the smallest partial computable function with this property.

=== Example ===

Line 107:

<math>f(n+1) = (n + 1) \cdot f(n)</math>

The corresponding recursive operator &Phi;Φ 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, &Phi;Φ will contain the pair <math>( \varnothing, (0, 1))</math>. 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'', &Phi;Φ will contain the pair <math>( \{ (n, m) \}, (n+1, (n+1)\cdot m))</math>. This indicates that, if ''f''(''n'') is ''m'', then ''f''(''n''&nbsp;+&nbsp;1) is (''n''&nbsp;+&nbsp;1)''m'', so that the pair (''n''&nbsp;+&nbsp;1,&nbsp;(''n''&nbsp;+&nbsp;1)''m'') is in the graph of ''f''. Unlike the base case ''f''(0)&nbsp;=&nbsp;1, the recursive operator requires some information about ''f''(''n'') before it defines a value of ''f''(''n''&nbsp;+&nbsp;1).

The first recursion theorem (in particular, part 1) states that there is a set ''F'' such that &Phi;Φ(''F'') = F. 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:

Line 125:

=== Proof sketch for the first recursion theorem ===

The proof of part 1 of the first recursion theorem is obtained by iterating the enumeration operator &Phi;Φ beginning with the empty set. First, a sequence ''F''_''k'' is constructed, for <math>k = 0, 1, \ldots</math>. Let ''F''₀ be the empty set. Proceeding inductively, for each ''k'', let ''F''_{''k'' + 1} be <math>F_k \cup \Phi(F_k)</math>. Finally, ''F'' is taken to be <math>\bigcup F_k</math>. The remainder of the proof consists of a verification that ''F'' is recursively enumerable and is the least fixed point of &Phi;Φ. 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 &Phi;Φ is a recursive operator is used to show that the fixed point of &Phi;Φ 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.

=== Comparison to the second recursion theorem ===

Line 138:

== Generalized theorem ==

[[Anatoly Maltsev]] proved a generalized version of the recursion theorem for any set with a [[precomplete numbering]]{{Citation needed|date=October 2013}}. A G&ouml;delGö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 <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

Line 151:

* Cutland, N.J., 1980, ''Computability: An introduction to recursive function theory'', Cambridge University Press. {{isbn|0-521-29465-7}}

* [[Stephen Cole Kleene|Kleene, S.C.]], 1938, "[http://www.thatmarcusfamily.org/philosophy/Course_Websites/Readings/Kleene%20-%20Ordinals.pdf On Notation for Ordinal Numbers]", [[Journal of Symbolic Logic]] 3, 150–155.

* &mdash;Kleene, S.C., 1952, ''Introduction to Metamathematics'', North-Holland. {{isbn|0-7204-2103-9}}

* [[Carl Jockusch|Jockusch, C.G. Jr.]]; Lerman, M.; Soare, R.I.; and Solovay, R.M., 1989, "Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion", [[Journal of Symbolic Logic]], 4, 1288&ndash;1323.

* Jones, N.D.J., 1997, ''Computability and Complexity from a programming perspective'', MIT Press. {{isbn|0-262-10064-9}}