On the number of infinite sequences with trivial initial segment complexity

DOI10.1016/J.TCS.2011.09.020MaRDI QIDQ655422zbMATH OpenOpenAlexFDO

Authors 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

treesKolmogorov complexityarithmetical complexity\(K\)-trivial sets

Mathematics Subject Classification ID

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

Recommendations

• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Kolmogorov complexity and computably enumerable sets
• Kolmogorov complexity of initial segments of sequences and arithmetical definability
• 𝐾-trivial degrees and the jump-traceability hierarchy
• Exact pairs for the ideal of the \(K\)-trivial sequences in the Turing degrees

Cites work

• scientific article; zbMATH DE number 3827843 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 2063218 (Why is no real title available?)
• scientific article; zbMATH DE number 3342830 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• A formal theory of inductive inference. Part I
• A minimal pair of 𝐾-degrees
• Algorithmic randomness and complexity.
• Computability and randomness
• Information-theoretic characterizations of recursive infinite strings
• Kolmogorov complexity of initial segments of sequences and arithmetical definability
• Lowness for the class of random sets
• Lowness properties and randomness
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Working below a \(low_ 2\) recursively enumerable degree
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(6)

• Exact pairs for the ideal of the \(K\)-trivial sequences in the Turing degrees
• Resolute sequences in initial segment complexity
• scientific article; zbMATH DE number 3890728 (Why is no real title available?)
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Kolmogorov complexity of initial segments of sequences and arithmetical definability
• Solovay functions and their applications in algorithmic randomness

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q655422)