On the number of infinite sequences with trivial initial segment complexity

DOI10.1016/J.TCS.2011.09.020zbMath1235.68086OpenAlexW2097553438MaRDI 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 complexitytreesarithmetical complexity\(K\)-trivial sets

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

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

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

This page was built for publication: On the number of infinite sequences with trivial initial segment complexity