Effective oracles (Q1191173)

Metarecursion and computation with Turing machines with oracles pertains to the theory of abstract decidability, which retains analogs of computation. Thus, in metarecursion and the theory of \(\mathcal F\)- computations (i.e., computations using the oracle \(\mathcal F\)), the foreground is occupied by such algorithmic notions as the constructive analogs of regular and inadmissible cardinals, which, in set theory, are problematic and appear in their constructive analogs as admissible and constructively inadmissible ordinals. The first is associated with computability of the functional \(E\) (the jump), and the second with computability of \(E_ 1\) (the hyperjump), which, in turn, occupy important positions in theories of computation with oracles. The properties of regularity and being weakly grounded, which are natural for an arbitrary oracle \(\mathcal F\), guarantee the admissibility of the ordinal \(| T({\mathcal F})| = \sup \{| z|: z \in T({\mathcal F})\}\) (where \(T({\mathcal F})\) is the set of codes for \(\mathcal F\)-constructive ordinals, or \(\mathcal F\)-computable trees with no closed circuits, and \(| z|\) is the height of the tree \(z\)), which raises the possibility of reproducing meta-recursion in the language of \(\mathcal F\)- computation. An attempt was made to do this [the author, Vychisl. Sist. 122, 145-156 (1987; Zbl 0681.03028)] with an arbitrary (regular and weakly grounded) oracle \(\mathcal F\) and a multivalued (\({\mathcal F}\)- computable) enumeration system \(T({\mathcal F})\). The role of ordinal functions is played by consistent \(\mathcal F\)-computable mappings onto \(T({\mathcal F})\). Consistency of a mapping \(\widetilde{f}\) defined on \(T({\mathcal F})\) means that the equation \(| y| = | z|\) implies \(| \widetilde{f} (y)| = | \widetilde{f} (z)|\). All of the elementary theory of metarecursion therefore proved to be reproducible. Particular interest is presented here by effective \((| T({\mathcal F})|\)-recursive) oracles \(\mathcal F\) whose heights \((| T({\mathcal F})|)\) prove to be admissible ordinals that are projectable into \(\omega\). On the other hand, for each ordinal \(\alpha\) that is projectable into \(\omega\), we can construct an effective oracle \(\mathcal F\) of height \(\alpha\). Metarecursion with an effective oracle \(\mathcal F\), while having all of the advantages of Kreisel-Sacks metarecursion, also generalizes it to arbitrary projectable countable ordinals. Here we consider certain properties of effective oracles as \(| T({\mathcal F})|\)-recursive functions defined on finite ordinals.