SAS

Abstract

Joseph Miller[1] and independently Andre Nies, Frank Stephan and Sebastian Terwijn[2] gave a complexity characterization of $2$-random sequences in terms of plain Kolmogorov complexity $C\,(\cdot)$: they are sequences that have infinitely many initial segments with $O(1)$-maximal plain complexity (among the strings of the same length).

Later Miller[3] (see also [4]) showed that prefix complexity $K\,(\cdot)$ can be also 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; we provide simple direct proofs for both of them.

In [1] Miller also gave a quantitative version of the first result: the $0'$-randomness deficiency of a sequence $\omega$ equals $\liminf_n [n - C\,(\omega_1\dots\omega_n)] + O(1)$. (Our simplified proof also can be used to prove this quantitative version.) We show (and this seems to be a new result) that a similar quantitative result is true also for prefix complexity: $0'$-randomness deficiency $d^{0'}(\omega)$ equals also $\liminf_n [n + K\,(n) - K\,(\omega_1\dots\omega_n)]+ O(1)$. This completes the picture: \begin{eqnarray*} d^{0'}(\omega) &=& \sup_n \, \left[ n - K\,^{0'}(\omega_1\dots\omega_n) \right] + O(1) \\ &=& \liminf_n \, \left[ n - C\,(\omega_1\dots\omega_n) \right] + O(1) \\ &=& \liminf_n \, \left[ n + K\,(n) - K\,(\omega_1\dots\omega_n) \right] + O(1) \,. \end{eqnarray*}

[1] J.S. Miller. "Every 2-random real is Kolmogorov random." Journal of Symbolic Logic, 69(3):907–913, 2004.

[2] A. Nies, F. Stephan, and S.A. Terwijn. "Randomness, relativization and turing degrees." The Journal of Symbolic Logic, 70(2), 2005.

[3] J.S. Miller. "The K-degrees, low for K-degrees, and weakly low for K sets." Notre Dame Journal of Formal Logic, 50(4):381–391, 2009.

[4] R.G. Downey and D.R. Hirschfeldt. "Algorithmic Randomness and Complexity." Theory and Applications of Computability. Springer, 2010.