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.

**The video for this talk should appear here if JavaScript is enabled.**

If it doesn't, something may have gone wrong with our embedded player.

We'll get it fixed as soon as possible.

If it doesn't, something may have gone wrong with our embedded player.

We'll get it fixed as soon as possible.