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

DOI10.1007/S00153-015-0430-2MaRDI QIDQ494650zbMATH OpenOpenAlexWikidataFDO

Authors B. Bauwens

Publication date 1 September 2015

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

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

zbMATH Keywords

incompressibility2-randomnessalgorithmic randomnessrandomness deficiencyplain compexityprefix-free complexityMartin-Löf randomness

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

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).

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 3489016 (Why is no real title available?)
• scientific article; zbMATH DE number 3489017 (Why is no real title available?)
• scientific article; zbMATH DE number 3492569 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• A formal theory of inductive inference. Part I
• Algorithmic randomness and complexity.
• Algorithmic tests and randomness with respect to a class of measures
• An additivity theorem for plain Kolmogorov complexity
• An introduction to Kolmogorov complexity and its applications
• Effectively approximating measurable sets by open sets
• Every 2-random real is Kolmogorov random
• Exact Expressions for Some Randomness Tests
• Limit complexities revisited
• Process complexity and effective random tests
• Randomness, relativization and Turing degrees
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• The definition of random sequences

Cited in

(9)

• Relating and contrasting plain and prefix Kolmogorov complexity
• Every 2-random real is Kolmogorov random
• scientific article; zbMATH DE number 2019634 (Why is no real title available?)
• 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)