Effective oracles

DOI10.1007/BF01978553MaRDI QIDQ1191173zbMATH OpenOpenAlexFDO

Publication date 27 September 1992

Published in Algebra and Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01978553

admissible ordinals computation with oracles effective oracle metarecursion

Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Higher-type and set recursion theory (03D65)

Review text

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.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Effective oracles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1191173)