| The interest is in understanding and insightfully characterizing the power of program self-reference (synonyms: self-knowledge, self-reflection). Kleene's Recursion Theorem (krt) formalizes this notion in the context of effective programming systems (epses), the computability theoretic analogs of programming languages for the partial computable functions. krt holds in some epses, but not in others. Thus, to characterize the power of program self-reference is, at least in part, to characterize the epses in which krt holds. This dissertation presents three such characterizations. It also presents several interesting results concerning krt that were obtained along the way.;A comparison is given between krt and some other forms of the recursion theorem, including Rogers' Fixpoint Recursion Theorem ( fprt). fprt is strictly weaker than krt, in that fprt holds in any eps in which krt holds, but not vice versa. Thus, one could ask: are there programs that one would reasonably call self-referential, and whose existence is assured by krt, but not by fprt? It is shown that self-reproducing programs (a.k.a. quines) satisfy these technical conditions. Since most would surely agree that a self-reproducing program is self-referential, this result suggests that krt is better than fprt at capturing the notion of program self-reference.;It is shown that there exist epses in which an extremely non-constructive form of krt holds. Roughly, in such epses, self-referential programs exist, but cannot be found algorithmically---not even with access to an oracle for K (the diagonal halting problem).;Several results are presented concerning the relationship between krt and various kinds of control structures. For example, it is shown that there is no class of recursive denotational control structures whose implementation characterizes krt . It is also shown that there is no class of recursive denotational control structures whose implementation is complementary to krt. This latter result is in contrast to a result of Royer, which showed that implementation of if-then-else---a denotational control structure---is complementary to the constructive form of Kleene's Recursion Theorem.;On the other hand, it is shown that there exist non-denotational control structures whose implementation is complementary to krt. Examples of such control structures are given herein.;The proofs of several of these results involve priority methods. |
