Turing Degrees and Muchnik Degrees of Recursively Bounded DNR Functions

DOI10.1007/978-3-319-50062-1_40zbMath1485.03148OpenAlexW2558186139MaRDI QIDQ2970986

Stephen G. Simpson

Publication date: 4 April 2017

Published in: Computability and Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-50062-1_40

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32)

Related Items

Highness properties close to PA completeness

Cites Work

• Unnamed Item
• Unnamed Item
• Propagation of partial randomness
• Mass problems associated with effectively closed sets
• Logic, methodology and philosophy of science VIII. Proceedings of the eighth international congress of logic, methodology and philosophy of science, Moscow, August 17-22, 1987
• Evolving computability. 11th conference on computability in Europe, CiE 2015, Bucharest, Romania, June 29 -- July 3, 2015. Proceedings
• MASS PROBLEMS AND INITIAL SEGMENT COMPLEXITY
• Difference randomness
• Kolmogorov complexity and the Recursion Theorem
• Degrees of Unsolvability: A Tutorial
• Mass Problems and Randomness
• Diagonally non-recursive functions and effective Hausdorff dimension
• An extension of the recursively enumerable Turing degrees
• Almost everywhere domination and superhighness
• Comparing DNR and WWKL
• DEEP CLASSES