Content deleted Content added
Gricharduk (talk | contribs) →Comparison to Rogers's theorem: Correcting page typo in the reference |
Gricharduk (talk | contribs) m →Fixed-point free functions: Adding a full stop |
||
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′''', the degree of the [[halting problem]] {{harv|Soare|1987|p=88}}.
== Kleene's second recursion theorem ==
| |||