On the number of infinite sequences with trivial initial segment complexity

DOI10.1016/j.tcs.2011.09.020zbMath1235.68086MaRDI QIDQ655422

George Barmpalias, Tom F. Sterkenburg

Publication date: 4 January 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.09.020

zbMATH Keywords

Kolmogorov complexity; trees; arithmetical complexity; \(K\)-trivial sets

Mathematics Subject Classification ID

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

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Solovay functions and their applications in algorithmic randomness, Kolmogorov complexity of initial segments of sequences and arithmetical definability, On the gap between trivial and nontrivial initial segment prefix-free complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Working below a \(low_ 2\) recursively enumerable degree
• Kolmogorov complexity of initial segments of sequences and arithmetical definability
• Information-theoretic characterizations of recursive infinite strings
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Lowness properties and randomness
• Kolmogorov complexity and the Recursion Theorem
• Algorithmic Randomness and Complexity
• A minimal pair of 𝐾-degrees
• A Theory of Program Size Formally Identical to Information Theory
• Lowness for the class of random sets
• A formal theory of inductive inference. Part I
• ∏ 0 1 Classes and Degrees of Theories