DEEP CLASSES

DOI10.1017/bsl.2016.9zbMath1401.03077arXiv1403.0450OpenAlexW4246515245MaRDI QIDQ5346696

Christopher P. Porter, Laurent Bienvenu

Publication date: 26 May 2017

Published in: The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1403.0450

zbMATH Keywords

computability theoryalgorithmic randomness\(\Pi_1^0\) classesprobabilistic computation

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Algorithmic randomness and dimension (03D32)

Related Items

Growth and irreducibility in path-incompressible trees ⋮ Turing Degrees and Muchnik Degrees of Recursively Bounded DNR Functions ⋮ Diagonally non-computable functions and fireworks ⋮ The random members of a \({\Pi }_{1}^{0}\) class ⋮ Highness properties close to PA completeness ⋮ A computable analysis of majorizing martingales

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algebra of invariant properties of binary sequences
• Randomness and lowness notions via open covers
• Mass problems associated with effectively closed sets
• The upward closure of a perfect thin class
• Strong reductions in effective randomness
• The universal Turing machine. A half-century survey.
• Density, forcing, and the covering problem
• Difference randomness
• Everywhere complex sequences and probabilistic method
• Algorithmic Randomness and Complexity
• Traceable Sets
• Mass Problems and Randomness
• Complex tilings
• Lowness for Kurtz randomness
• Randomness conservation inequalities; information and independence in mathematical theories
• Exact Expressions for Some Randomness Tests
• Diagonally non-recursive functions and effective Hausdorff dimension
• An extension of the recursively enumerable Turing degrees
• Shift-complex sequences
• Forbidden information
• Degrees of Unsolvability. (AM-55)
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• ∏ 0 1 Classes and Degrees of Theories
• Randomness, relativization and Turing degrees