Universal computably enumerable sets and initial segment prefix-free complexity

DOI10.1016/J.IC.2013.12.001MaRDI QIDQ391648zbMATH OpenOpenAlexFDO

Authors 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 complexityuniversal setscomputably enumerableinitial segment complexity

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25)

Abstract: We show that there are Turing complete computably enumerable sets of arbitrarily low non-trivial initial segment prefix-free complexity. In particular, given any computably enumerable set $A$ with non-trivial prefix-free initial segment complexity, there exists a Turing complete computably enumerable set $B$ with complexity strictly less than the complexity of $A$. On the other hand it is known that sets with trivial initial segment prefix-free complexity are not Turing complete. Moreover we give a generalization of this result for any finite collection of computably enumerable sets $A_i,i<k$ with non-trivial initial segment prefix-free complexity. An application of this gives a negative answer to a question from cite[Section 11.12]{rodenisbook} and cite{MRmerstcdhdtd} which asked for minimal pairs in the structure of the c.e. reals ordered by their initial segment prefix-free complexity. Further consequences concern various notions of degrees of randomness. For example, the Solovay degrees and the $K$-degrees of computably enumerable reals and computably enumerable sets are not elementarily equivalent. Also, the degrees of randomness based on plain and prefix-free complexity are not elementarily equivalent; the same holds for their $Delt{a}_2^0$ and $Sigm{a}_1^0$ substructures.

Recommendations

• Kolmogorov complexity and computably enumerable sets
• Analogues of Chaitin's Omega in the computably enumerable sets
• Random strings and truth-table degrees of Turing complete c.e. sets
• There is no SW-complete c.e. real
• scientific article; zbMATH DE number 1796998

Cites work

• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 2063218 (Why is no real title available?)
• scientific article; zbMATH DE number 3307567 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• A minimal pair of 𝐾-degrees
• Algorithmic randomness and complexity.
• Analogues of Chaitin's Omega in the computably enumerable sets
• Chaitin's halting probability and the compression of strings using oracles
• Computability and randomness
• Elementary differences between the degrees of unsolvability and degrees of compressibility
• Kolmogorov complexity and computably enumerable sets
• Kolmogorov complexity of initial segments of sequences and arithmetical definability
• Lowness notions, measure and domination
• Lowness properties and randomness
• Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
• New Computational Paradigms
• Non-cupping, measure and computably enumerable splittings
• On initial segment complexity and degrees of randomness
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Oscillation in the initial segment complexity of random reals
• Randomness and reducibility
• Randomness, computability, and density
• Relative randomness and cardinality
• Solovay functions and \(K\)-triviality
• The Kolmogorov complexity of random reals
• The definition of random sequences
• Undecidability of the structure of the Solovay degrees of c.e. reals

Cited in

(8)

• scientific article; zbMATH DE number 1796998 (Why is no real title available?)
• Closed left-r.e. sets
• Effective bounds for convergence, descriptive complexity, and natural examples of simple and hypersimple sets
• Analogues of Chaitin's Omega in the computably enumerable sets
• Logical Approaches to Computational Barriers
• Kolmogorov entropy in the context of computability theory
• Elementary differences between the degrees of unsolvability and degrees of compressibility
• Kolmogorov complexity and computably enumerable sets

This page was built for publication: Universal computably enumerable sets and initial segment prefix-free complexity

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