Program Self-Reference in Constructive Scott Subdomains
Intuitively, a recursion theorem asserts the existence of self-referential programs . Two well-known recursion theorems are Kleenes Recursion Theorem(krt) and Rogers Fixpoint Recursion Theorem(fprt). Does one of these two theorems better capture the notion of program self-reference than the other? In the context of the partial computable functions over the natural numbers (\(\mathcal {PC}\)), fprt is strictly weaker than krt, in that fprt holds in any effective numbering of \(\mathcal {PC}\) in which krt holds, but not vice versa. It is shown that, in this context, the existence of self-reproducing programs (a.k.a. quines ) is assured by krt, but not by fprt. Most would surely agree that a self-reproducing program is self-referential. Thus, this result suggests that krt is better than fprt at capturing the notion of program self-reference in \(\mathcal {PC}\) .
self-reference recursion theorems numberings self-reproducing programs scott domains