Math 597B – Homework #4

March 21, 2007

1. Assume that A ∈ 2^{ℕ} is random (in the sense of Martin-Löf). Let f(n) be a total recursive function such that

lim sup_{n→∞} f(n) = ∞ .

Let U_{n}, n = 1, 2, …, be a uniformly Σ_{1}^{0} sequence of subsets of 2^{ℕ} such that μ(U_{n}) ≤ 1/f(n) for all n. Prove that A ∉ ⋂_{n=1}^{∞} U_{n}.

2. Assume that A ∈ 2^{ℕ} is random. Prove that

lim_{n→∞} \frac{|\{m < n | A(m) = 1\}|}{n} = \frac{1}{2} .

3. In Problem 2, does your proof yield an estimate on the rate of convergence to 1/2?

4. In Problem 2, what if we assume only that A is weakly random?

5. Assume that A ⊕ B ∈ 2^{ℕ} is random. Prove that the Turing degrees a = deg_{T} (A) and b = deg_{T} (B) are incomparable.

6. In Problem 5, what if we assume only that A ⊕ B is weakly random?

7. Let a = deg_{T} (A) where A is strongly random. Prove that a ∧ 0′ = 0.

Note: It can be shown that this does not hold if we assume only that A is random. In fact, we can find a random A such that A ≤_{T} 0′.