[M35] A finite binary string x of length n is called -random if C(x|n) n. A Turing machine place-selection rule R is a Turing

[M35] A finite binary string x of length n is called δ-random if C(x|n) ≥ n−δ. A Turing machine place-selection rule R is a Turing machine that selects and outputs a (not necessarily consecutive) substring R(x) from its input x. If R is the kth Turing machine in the standard enumeration, then C(R) = C(k).

Show that for any  > 0, there exist numbers n0 and μ > 0 such that if l(x) = n, l(R(x)) = r ≥ n0,



Comments. δ-random sequences were introduced by A.N. Kolmogorov

[Lect. Notes Math., Vol. 1021, Springer-Verlag, 1983, 1–5]. He noted that

“sequences satisfying this condition have for sufficiently small δ the particular property of frequency stability in passing to subsequences.” In this exercise we supply some quantitative estimates of frequency stability. Source: [E.A. Asarin, SIAM Theory Probab. Appl., 32(1987), 507–

508]. This exercise is used by Asarin to show that δ-random elements of certain finite sets obey familiar probability-theoretic distribution laws, see also [E.A. Asarin, Soviet Math. Dokl., 36(1988), 109–112].