[40] Uniform complexity was defined in Exercise 2.3.2, page 130. Here we define the time-bounded uniform complexity. For an infinite string and the reference

[40] Uniform complexity was defined in Exercise 2.3.2, page 130.

Here we define the time-bounded uniform complexity. For an infinite string ω and the reference universal Turing machine U, Ct

(ω1:n; n) = min{l(p) : ∀i ≤ n[Ut

(p, i) = ω1:i]}.

Define CU [f, t, ∞] = {ω : ∀∞n[Ct

(ω1:n; n) ≤ f(n)]}.

Let ω be a Mises–Wald–Church random sequence, with total computable admissible place-selection rules instead of the standard definition with partial computable admissible place-selection rules. Show that for every unbounded, nondecreasing, total computable time bound t we have ω ∈
CU [
1 2n, t, ∞]. This holds a fortiori for the set of Mises–Wald–Church random sequences using partial computable place-selection rules.
Comments. This exercise shows that there is a Mises–Wald–Church random sequence, as defined in Definition 1.9 on page 53, with limiting frequency 1 2 , that has very low uniform Kolmogorov complexity, but high time-bounded uniform Kolmogorov complexity. In Exercise 2.5.16, Item (a), on page 164, we have proved that there is a Mises–Wald–Church random sequence ω, with partial computable placeselection rules as in Definition 1.9 and limiting frequency 1 2 , such that C(ω1:n; n) ≤ f(n) log n + O(1) for every unbounded, nondecreasing, total computable function

f. In Exercise 2.5.16, Item (c), on page 164, we have proved that there is a Mises–Wald–Church random sequence ω, with total computable place-selection rules and limiting frequency 1 2 , such that C(ω1:n; n) ≤ f(n) + O(1) for every unbounded, nondecreasing, total computable function

f. Now we have shown that if there is a computable time bound, then all Mises–Wald–Church random sequences (even with respect to only total computable place-selection rules) indeed look quite random. One should be able to prove similar theorems for C and K versions of this exercise and Exercise