About Segment Complexity of Turing Reductions

DOI10.1002/malq.19990450413zbMath0940.03054OpenAlexW2043304210MaRDI QIDQ4704660

V. K. Bulitko

Publication date: 13 July 2000

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.19990450413

zbMATH Keywords

Kolmogorov complexityjump inversionoracle Turing machineshierarchy of relationsuse restrictions on Turing reducibility

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Other Turing degree structures (03D28) Hierarchies of computability and definability (03D55)

Related Items (2)

2000 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium 2000 ⋮ Unnamed Item

Cites Work

• A criterion for completeness of degrees of unsolvability

This page was built for publication: About Segment Complexity of Turing Reductions