Turing reducibility in the fine hierarchy

DOI10.1016/J.APAL.2019.102766MaRDI QIDQ2187259zbMATH OpenOpenAlexWikidataFDO

Authors Alexander Melnikov, M. M. Yamaleev, Victor Selivanov

Publication date 2 June 2020

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2019.102766

zbMATH Keywords

arithmetical hierarchyErshov hierarchyfine hierarchyTuring degree

Mathematics Subject Classification ID

Other Turing degree structures (03D28) Other degrees and reducibilities in computability and recursion theory (03D30) Hierarchies of computability and definability (03D55)

Review text

In the 1980s, the second author introduced the fine hierarchy, a generalization of the Ershov hierarchy. Recently, the second and the third author [Algebra Logic 57, No. 3, 222--236 (2018; Zbl 1485.03155); translation from Algebra Logika 57, No. 3, 338--361 (2018)] showed that the Turing degrees of the sets at level \(\omega^\omega\) of this hierarchy are precisely the Turing degrees of the \(\Sigma^0_3\) sets, and that the same holds true at level \(\omega^\omega+1\). The present paper contrastingly proves, via a \(0\) priority argument, that level \(\omega^\omega+2\) contains additional Turing degrees.

Recommendations

• Turing degrees in refinements of the arithmetical hierarchy
• Turing degrees and the Ershov hierarchy
• Extending Cooper's theorem to \(\Delta_3^0\) Turing degrees
• Turing jumps in the Ershov hierarchy
• scientific article; zbMATH DE number 28544

Cites work

• A Hierarchy of Turing Degrees
• A survey of results on the d-c.e. and n-c.e. degrees
• A survey of results on the d.c.e. and \(n\)-c.e. degrees
• Computable structures and the hyperarithmetical hierarchy
• Ershov hierarchy
• Extending Cooper's theorem to \(\Delta_3^0\) Turing degrees
• Fine hierarchies and Boolean terms
• Fine hierarchies and m-reducibilities in theoretical computer science
• scientific article; zbMATH DE number 3851066 (Why is no real title available?)
• scientific article; zbMATH DE number 3732038 (Why is no real title available?)
• scientific article; zbMATH DE number 194101 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 545277 (Why is no real title available?)
• scientific article; zbMATH DE number 6318 (Why is no real title available?)
• scientific article; zbMATH DE number 3342830 (Why is no real title available?)
• scientific article; zbMATH DE number 3342831 (Why is no real title available?)
• Invariant descriptive set theory
• Iterated trees of strategies and priority arguments
• Notes on computable analysis
• On ω-regular sets
• PRIORITY ARGUMENTS VIA TRUE STAGES
• Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers
• Recursive Labelling Systems and Stability of Recursive Structures in Hyperarithmetical Degrees
• The Veblen functions for computability theorists
• Turing degrees in refinements of the arithmetical hierarchy

Cited in

(11)

• Turing degrees in refinements of the arithmetical hierarchy
• Query-monotonic Turing reductions
• Turing Tumble is Turing-complete
• Turing-Completeness Totally Free
• Turing degrees and the Ershov hierarchy
• Extending Cooper's theorem to \(\Delta_3^0\) Turing degrees
• Effectivity and reducibility with ordinal Turing machines
• Non-collapse of the effective Wadge hierarchy
• Turing-Complete Subclasses of CHR
• On the main scientific achievements of Victor Selivanov
• Fine hierarchies and m-reducibilities in theoretical computer science

This page was built for publication: Turing reducibility in the fine hierarchy

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