Kleene's recursion theorem: Difference between revisions

Revision as of 13:30, 6 May 2020

Revision as of 13:49, 6 May 2020

Line 39:

=== Comparison to Rogers's theorem ===

Kleene's second recursion theorem and Rogers's theorem can both be proved, rather simply, from each other {{harv|Jones|1997|pp=229{{ndash}}230}}. However, a direct proof of Kleene's theorem {{harv|Kleene|1952|pp=352{{ndash}}3530353}} does not make use of a universal program, which means that the theorem holds for certain subrecursive programming systems that do not have a universal program.

=== Application to quines ===