[40] (a) Show that there exists an infinite binary sequence that is -random (with the uniform measure), and is 0 -computable, and there

• [40]

(a) Show that there exists an infinite binary sequence ω

that is λ-random (with λ the uniform measure), and is 0

-computable, and there exists a universal semimeasure M (that is, a universal monotone Turing machine yielding this measure) such that M(ωn+1|ω1:n) →

λ(ωn+1|ω1:n) for n → ∞ (here λ(x|l(x) = n)=1/2l(x)

).

(b) Show that for every universal semimeasure M there exist computable measures μ and non-μ-random sequences ω such that M(ωn+1|

ω1:n)/λ(ωn+1|ω1:n) → 1 for n → ∞.

Comments. Item

(a) states that for some reference universal monotonic machine with induced universal measure M and some random sequence

(with respect to the uniform measure) the convergence does not hold.

Hence, Theorem 5.2.2 on page 366 does not always hold for y fixed, and xy is an increasing initial segment of a random sequences ω—in contrast to what was claimed, without proof, in earlier editions of this book. In fact, these random sequences for which convergence fails are 0

-computable (computable by Turing machines with an oracle for the halting problem). An.A. Muchnik supposed, though he did not know a proof, that for some other M the convergence is true for every random sequence. If so, then strengthening of the convergence in Theorem 5.2.2 on page 366 with μ-probability one to convergence for all individual random sequences is a matter of choice of reference universal monotonic machine. This is a deviation from the usual laws in Kolmogorov complexity that are invariant under change of reference universal machine. Hint for Item (a): Define ω = ω1ω2 ... by ωn = 0 if M(ω1:n−10|n) ≤ 1/2n, and ωn = 1 otherwise. Prove that ω is λ-random. Construct a lower semicomputable semimeasure ν such that ν dominates M on ω, but ν(ωn+1|ω1:n) → λ(ωn+1|ω1:n). Then mix ν with M to make the mixture universal, but with a larger contribution of ν to preserve nonconvergence. Item

(b) is a converse to Item (a). Source: [An.A. Muchnik, Ibid.;
M. Hutter and An.A. Muchnik, Ibid.].