# SAS

## Seminar

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

Seminar Room 1, Newton Institute

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

## Comments

Start the discussion!