Kleene's recursion theorem: Difference between revisions

Revision as of 03:37, 4 January 2023

Revision as of 17:35, 29 April 2023

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>. Note that the comparison of in- and outputs here is not in terms of numerical values, but in terms of their associated functions.

Rogers describes the following result as "a simpler version" of Kleene's (second) recursion theorem.{{sfn|Rogers|1967|loc=§11.2}}

{{math theorem | name = Rogers's fixed-point theorem | math_statement = If <math>F</math> is a total computable function, it has a fixed point in the above sense.}}

=== Proof of the fixed-point theorem ===