Universal computably enumerable sets and initial segment prefix-free complexity

DOI10.1016/j.ic.2013.12.001zbMath1402.03059arXiv1110.1864MaRDI QIDQ391648

George Barmpalias

Publication date: 10 January 2014

Published in: Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

Kolmogorov complexity; universal sets; computably enumerable; initial segment complexity

Mathematics Subject Classification ID

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

03D25: Recursively (computably) enumerable sets and degrees

03D32: Algorithmic randomness and dimension

Cites Work

• Kolmogorov complexity and computably enumerable sets
• Oscillation in the initial segment complexity of random reals
• Elementary differences between the degrees of unsolvability and degrees of compressibility
• Kolmogorov complexity of initial segments of sequences and arithmetical definability
• Undecidability of the structure of the Solovay degrees of c.e. reals
• Relative randomness and cardinality
• Randomness and reducibility
• The Kolmogorov complexity of random reals
• Analogues of Chaitin's Omega in the computably enumerable sets
• Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Lowness properties and randomness
• Randomness, Computability, and Density
• Lowness notions, measure and domination
• Chaitin's halting probability and the compression of strings using oracles
• Algorithmic Randomness and Complexity
• A minimal pair of 𝐾-degrees
• On initial segment complexity and degrees of randomness
• Non-cupping, measure and computably enumerable splittings
• A Theory of Program Size Formally Identical to Information Theory
• The definition of random sequences
• New Computational Paradigms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item