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 hierarchyTuring degreeErshov hierarchyfine hierarchy

Mathematics Subject Classification ID

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

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

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

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)