Propagation of partial randomness

DOI10.1016/J.APAL.2013.10.006zbMath1329.03078arXiv1311.0724OpenAlexW2131763648MaRDI QIDQ386647

Keita Yokoyama, Kojiro Higuchi, W. M. Phillip Hudelson, Stephen G. Simpson

Publication date: 10 December 2013

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

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

zbMATH Keywords

Kolmogorov complexitymodels of arithmeticMartin-Löf randomnesseffective Hausdorff dimensionpartial randomness

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)

Related Items (10)

Energy randomness ⋮ DEGREES OF RANDOMIZED COMPUTABILITY ⋮ Turing Degrees and Muchnik Degrees of Recursively Bounded DNR Functions ⋮ The axiomatic power of Kolmogorov complexity ⋮ On effectively closed sets of effective strong measure zero ⋮ Solovay reducibility and continuity ⋮ Randomness for computable measures and initial segment complexity ⋮ Highness properties close to PA completeness ⋮ A computable analysis of majorizing martingales ⋮ Cone avoidance and randomness preservation

Cites Work

• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
• A nonstandard counterpart of WWKL
• Mass problems associated with effectively closed sets
• Effectively closed sets of measures and randomness
• On interpreting Chaitin's incompleteness theorem
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• On partial randomness
• Lowness notions, measure and domination
• Effective Strong Nullness and Effectively Closed Sets
• MASS PROBLEMS AND INITIAL SEGMENT COMPLEXITY
• Kolmogorov complexity and the Recursion Theorem
• Algorithmic Randomness and Complexity
• Mass Problems and Randomness
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• On initial segment complexity and degrees of randomness
• Mass Problems and Measure-Theoretic Regularity
• Information-Theoretic Limitations of Formal Systems
• Relations between varieties of kolmogorov complexities
• The importance of Π₁⁰ classes in effective randomness
• Almost everywhere domination and superhighness
• Comparing DNR and WWKL
• Π₁⁰ classes with complex elements
• ∏ 0 1 Classes and Degrees of Theories
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Propagation of partial randomness