Every 2-random real is Kolmogorov random.(English)Zbl 1090.03012

A binary sequence $$\omega$$ is Martin-Löf random if all effectively checkable probability laws (such as the law of large numbers) hold for this sequence, i.e., if $$\omega$$ does not belong to any effective set of measure 0. Another reasonable definition of randomness, called Kolmogorov randomness, generalizes Kolmogorov’s idea that a finite sequence $$\omega$$ of length $$n$$ can be called random if it cannot be algorithmically compressed, i.e., if its Kolmogorov complexity $$K(\omega)$$ (the shortest length of a program that computes $$\omega$$) is $$\geq n-C$$ for some small constant $$C$$. It is therefore natural to describe an infinite sequence $$\omega=\omega_1\omega_2\ldots$$ as Kolmogorov random if, for infinitely many $$n$$, we have $$K(\omega_1\ldots\omega_n)\geq n-O(1)$$. It is known that every Kolmogorov random sequence is Martin-Löf random but there are Martin-Löf random sequences which are not Kolmogorov random.
The author provides a new equivalent characterization of Kolmogorov randomness in Martin-Löf-type terms. Specifically, in Martin-Löf’s definition, we limit ourselves to effectively checkable probability laws – i.e., laws of of the type $$\forall n P$$. For such laws, the measure 0 set of all the sequences that do not satisfy this law has the form $$\exists n \neg P$$, i.e., the form $$\Sigma_1^0$$. Since the fact that a sequence $$\omega$$ satisfies all effective laws is not sufficient to imply its non-compressibility, it is reasonable to require that $$\omega$$ should satisfy more general probability laws as well – e.g., laws for which the measure 0 set is described by $$\Sigma^0_2$$ formulas $$\exists n\forall m P$$. It turns out that the resulting “2-randomness” is indeed equivalent to Kolmogorov randomness.

MSC:

 03D80 Applications of computability and recursion theory 68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
Full Text:

References:

 [1] Problemy Peredači Informacii 1 pp 3– (1965) [2] Algorithmic randomness and complexity · Zbl 0815.60003 [3] Computational complexity (Courant Computer Science Symposium 7, New York University, New York, 1971) pp 113– (1973) [4] DOI: 10.1145/321892.321894 · Zbl 0309.68045 [5] DOI: 10.1016/S0019-9958(64)90131-7 · Zbl 0259.68038 [6] Doklady Akademii Nauk SSSR 212 pp 548– (1973) [7] DOI: 10.1007/BF00534110 · Zbl 0212.23103 [8] DOI: 10.1016/S0019-9958(66)80018-9 · Zbl 0244.62008 [9] ACM Symposium on the Theory of Computing (STOC) pp 61– (1969) [10] An introduction to Kolmogorov complexity and its applications (1993) · Zbl 0805.68063 [11] DOI: 10.1007/BF01694181 · Zbl 0227.62005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.