Isomorphism types of index sets of partial recursive functions
Louise Hay · Proceedings of the American Mathematical Society · 1966
1. Let {qo, ql, q2, } be a Kleene enumeration of partial recursive functions. If f is such a function, denote by Of its index set, Of= {InI qnf}. Insofar as the indices of a partial recursive function correspond to the different sets of instructions for computing its values, it is natural to ask how much of the complexity of the function is reflected by its index set; for example, one might expect the index set of a constant total function to differ in a fundamental way from that of a function whose domain and range are nonrecursive sets. More precisely, since the basic equivalence relation of recursion theory is recursive isomorphism (i.e., equivalence under a recursive permutation of the nonnegative integers) the following question arises: How many distinct recursive isomorphism types of index sets are there, and which properties of the corresponding functions can be used to characterize these types? This is answered in the theorem below. That the answer is independent of any particular enumeration follows from the fact, proved by Rogers in [5], that different standard-type enumerations are related by means of recursive permutations. In the following, function will mean partial recursive function and degree will mean Turing degree of unsolvability. We write aRif for a is 1-1 reducible to : and a-_ for a is recursively isomorphic to d. The notation is that of [3 ], but the technique will be informal in character.