MASS PROBLEMS AND INITIAL SEGMENT COMPLEXITY

DOI10.1017/jsl.2013.7zbMath1337.03061OpenAlexW2076298969MaRDI QIDQ2921016

W. M. Phillip Hudelson

Publication date: 30 September 2014

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

Full work available at URL: https://doi.org/10.1017/jsl.2013.7

zbMATH Keywords

Kolmogorov complexityMartin-Löf randomnessalgorithmic randomnesseffective Hausdorff dimensionpartial randomness

Mathematics Subject Classification ID

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

Related Items

Degrees of Unsolvability: A Tutorial ⋮ Propagation of partial randomness ⋮ Turing Degrees and Muchnik Degrees of Recursively Bounded DNR Functions ⋮ Mass problems associated with effectively closed sets

Cites Work

• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• On partial randomness
• Kolmogorov complexity and the Recursion Theorem
• Algorithmic Randomness and Complexity
• Mass Problems and Randomness
• A fixed-point-free minimal degree
• Mass Problems and Measure-Theoretic Regularity
• Relations between varieties of kolmogorov complexities
• Diagonally non-recursive functions and effective Hausdorff dimension
• An extension of the recursively enumerable Turing degrees
• Comparing DNR and WWKL
• An introduction to Kolmogorov complexity and its applications