DEGREES OF RANDOMIZED COMPUTABILITY

DOI10.1017/bsl.2021.46zbMath1497.03056arXiv1907.07815OpenAlexW3203125917MaRDI QIDQ5067871

Christopher P. Porter, Rupert Hölzl

Publication date: 4 April 2022

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

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

zbMATH Keywords

probabilistic algorithmcomputabilityrandomnessalgebraDNCnegligibilityLevinsemimeasurediagonally noncomputableLV-degreeV'yugin

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Other degrees and reducibilities in computability and recursion theory (03D30) Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Propagation of partial randomness
• Diagonally non-computable functions and fireworks
• Algebra of invariant properties of binary sequences
• On empirical meaning of randomness with respect to parametric families of probability distributions
• On calibration error of randomized forecasting algorithms
• Classical recursion theory. The theory of functions and sets of natural numbers
• Lattices and ordered algebraic structures
• Randomness and semimeasures
• Cone avoidance and randomness preservation
• Turing Computability
• The typical Turing degree
• Separations of non-monotonic randomness notions
• Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma
• Difference randomness
• Kolmogorov complexity and the Recursion Theorem
• Algorithmic Randomness and Complexity
• Retraceable Sets
• Notions of weak genericity
• On Sequences with Non-learnable Subsequences
• On initial segment complexity and degrees of randomness
• Randomness conservation inequalities; information and independence in mathematical theories
• A Theory of Program Size Formally Identical to Information Theory
• 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
• A formal theory of inductive inference. Part I
• A formal theory of inductive inference. Part II
• Randomness, relativization and Turing degrees