Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs

DOI10.1007/S00153-015-0430-2zbMATH Open1362.03037arXiv1310.5230OpenAlexW1993613819WikidataQ113906150 ScholiaQ113906150MaRDI QIDQ494650FDOQ494650

Authors: B. Bauwens 

Publication date: 1 September 2015

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Abstract: Joseph Miller [16] and independently Andre Nies, Frank Stephan and Sebastiaan Terwijn [18] gave a complexity characterization of 2-random sequences in terms of plain Kolmogorov complexity C: they are sequences that have infinitely many initial segments with O(1)-maximal plain complexity (among the strings of the same length). Later Miller [17] showed that prefix complexity K can also be used in a similar way: a sequence is 2-random if and only if it has infinitely many initial segments with O(1)-maximal prefix complexity (which is n + K (n) for strings of length n). The known proofs of these results are quite involved; in this paper we provide simple direct proofs for both of them. In [16] Miller also gave a quantitative version of the first result: the 0'-randomness deficiency of a sequence {omega} equals lim inf [n - C ({omega}1 . . . {omega}n)] + O(1). (Our simplified proof can also be used to prove this.) We show (and this seems to be a new result) that a similar quantitative result is also true for prefix complexity: 0'-randomness deficiency equals lim inf [n + K (n) -- K ({omega}1 . . . {omega}n)] + O(1).

Full work available at URL: https://arxiv.org/abs/1310.5230

Recommendations

• Limit complexities revisited
• Limit complexities revisited
• Every 2-random real is Kolmogorov random
• Kolmogorov-Loveland randomness and stochasticity
• Randomness, relativization and Turing degrees

zbMATH Keywords

incompressibility[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Martin-L%EF%BF%BD%EF%BF%BDf+randomness&go=Go Martin-L��f randomness]2-randomnessalgorithmic randomnessrandomness deficiencyplain compexityprefix-free complexity

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) 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
• Process complexity and effective random tests
• A Theory of Program Size Formally Identical to Information Theory
• The definition of random sequences
• Algorithmic tests and randomness with respect to a class of measures
• Exact Expressions for Some Randomness Tests
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Every 2-random real is Kolmogorov random
• Randomness, relativization and Turing degrees
• An introduction to Kolmogorov complexity and its applications
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Limit complexities revisited
• Effectively approximating measurable sets by open sets
• An additivity theorem for plain Kolmogorov complexity

Cited In (9)

• Relating and contrasting plain and prefix Kolmogorov complexity
• Every 2-random real is Kolmogorov random
• Title not available (Why is that?)
• Randomness notions and reverse mathematics
• A simple proof of Miller-Yu theorem
• Coherence of reducibilities with randomness notions
• Separations of non-monotonic randomness notions
• Limit complexities revisited
• Non-approximability of the Randomness Deficiency Function

This page was built for publication: Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs

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