A Simple Proof of Miller-Yu Theorem
Laurent Bienvenu, Wolfgang Merkle, Alexander Shen · 2008
A few years ago a nice criterion of Martin-Löf randomness in terms of plain (neither prefix nor monotone) Kolmogorov complexity was found (among many other results, it is published in [1]). In fact Martin-Löf came rather close to the formulation of this criterion around 1970 (see [2] and [3], p. 98). We provide a simple proof of this criterion that uses only elementary arguments very close to the original proof of Levin–Schnorr criterion of randomness (1973) in terms of monotone complexity ([4, 5]). Theorem. A. Let f: N → N be a total computable function such that ∑2 − f (n) < ∞. Then for every random sequence ω there exists a constant c such that C(ω1...ωn|n) ≥ n − f (n) − c for all n. B. There exists a total computable function f: N → N such that ∑2 − f (n) < ∞ and for every non-random sequence ω and for every c there exists n such that C(ω1...ωn|n) < n − f (n) − c (We consider binary sequences ω1ω2...; the randomness means Martin-Löf randomness with respect to the