Independence Results for n-ary Recursion Theorems
John Case and Samuel E. Moelius III
Abstract
The n-ary first and second recursion theorems formalize two distinct,
yet similar, notions of self-reference. Roughly, the n-ary first
recursion theorem says that, for any n algorithmic tasks (of an
appropriate type), there exist n partial computable functions that use
their own graphs in the manner prescribed by those tasks; the n-ary
second recursion theorem says that, for any n algorithmic tasks (of an
appropriate type), there exist n programs that use their own source code
in the manner prescribed by those tasks.
Results include the following. The constructive 1-ary form of the first
recursion theorem is independent of either 1-ary form of the second
recursion theorem. The constructive 1-ary form of the first recursion
theorem does not imply the constructive 2-ary form; however, the
constructive 2-ary form does imply the constructive n-ary form, for each
n>0. For each n>0, the not-necessarily-constructive n-ary form of the
second recursion theorem does not imply the presence of the (n + 1)-ary
form.