On the number of infinite sequences with trivial initial segment complexity

DOI10.1016/J.TCS.2011.09.020zbMATH Open1235.68086OpenAlexW2097553438MaRDI QIDQ655422FDOQ655422

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

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

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)

Cites Work

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

Cited In (6)

• Exact pairs for the ideal of the \(K\)-trivial sequences in the Turing degrees
• Resolute sequences in initial segment complexity
• Title not available (Why is that?)
• 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)