A few results on the complexity of classes of identifiable recursive function sets

TL;DRAbstract

Recently there have been several studies of special classes of identifiable recursive function sets. The complexity of such classes is generally characterized in the literature in the theory of complexity classes of recursive functions. With respect to this question the present paper uses two additional view-points: (A) The sorting of index sets of identifiable recursive function sets in the arithmetical hierarchy, and (B) The sorting of the required functionals, to identify recursive function sets of a special type, in the arithmetical hierarchy of function sets. In this way the paper contributes to the subject of the limiting decision procedures (cf. Gold [2], Barzdin' [1]).

Chat with Paper

AI Agents for this Paper