Kleene's recursion theorem: Difference between revisions

Revision as of 08:25, 15 July 2018

Revision as of 20:08, 17 January 2020

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 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]] (Soare 1987, p.&nbsp;88)

== Kleene's second recursion theorem ==