Computability, Unsolvability, Randomness Math 497A: Homework #10

Stephen G. Simpson

Due Monday, November 5, 2007

1. Let f and g be Turing oracles. Define f ≤_{LK} g to mean that

K^{g}(τ) ≤ K^{f}(τ) + O(1)

for all bitstrings τ. Define f ≤_{LR} g to mean that

(∀X ∈ 2^{ℕ}) (if X is g-random then X is f-random).

(a) Show that f ≤_{T} g implies both f ≤_{LK} g and f ≤_{LR} g.

(b) Let X ∈ 2^{ℕ} be such that X ≤_{LK} 0. Show that X is K-trivial, i.e., K(X ↾ n) ≤ K(n) + O(1) for all n.

Note: It can be shown that the properties f ≤_{LK} g and f ≤_{LR} g are equivalent to each other. However, they are not equivalent to f ≤_{T} g. In fact, we can find a nonrecursive X ∈ 2^{ℕ} such that X ≤_{LK} 0. It can be shown that X ≤_{LK} 0 if and only if X is K-trivial.

2. For convenience in stating this problem, let us identify subsets of ℕ with their characteristic functions. In other words, we identify A ⊆ ℕ with χ_{A} ∈ 2^{ℕ}. Thus 2^{ℕ} is the set of all subsets of ℕ.

Let J : 2^{ℕ} → 2^{ℕ} be the Turing jump operator:

J(X) = X′ = H^{X} = the Halting Problem relative to X.

Recall that 0^{(1)} = 0′ = J(0) and in general 0^{(n+1)} = (0^{(n)})′ = J(0^{(n)}) for all n. By Post’s Theorem we know that for each n ≥ 1 the set 0^{(n)} is Σ_{n}^{0} and not Δ_{n}^{0}. Define

0^{(ω)} = ⨁_{n=1}^{∞} 0^{(n)} = {3^{m}5^{n} | m ∈ 0^{(n)}} .

Note that the set 0^{(ω)} is not arithmetical, i.e., it is not Δ_{n}^{0} for any n.

(a) Show that the 2-place predicate P ⊆ 2^{ℕ} × 2^{ℕ} given by

P (X, Y) ≡ J(X) = Y

is Π_{2}^{0}.

(b) Show that for each n ≥ 1 the singleton set {0^{(n)}} is Π_{2}^{0}.

(c) Show that the singleton set {0^{(ω)}} is Π_{2}^{0}. Note: These singleton sets are subsets of 2^{ℕ}.

3. (a) Show that every nonempty Π_{1}^{0} subset of 2^{ℕ} contains a member

which is Δ_{n}^{0} for some n.

(b) In part (a), what is the optimal value of n?

(c) In parts (a) and (b), what if we replace Π_{1}^{0} sets by Π_{2}^{0} sets?

(d) Is every Π_{2}^{0} subset of 2^{ℕ} Turing isomorphic to a Π_{1}^{0} subset of 2^{ℕ}?

4. Let X ∈ 2^{ℕ}. We say that X is 2-random if X is random relative to 0′. Recall also that X is weakly 2-random if X ∉ any Π_{2}^{0} set of measure 0. Let a = deg_{T} (X) = the Turing degree of X.

(a) Show that if X is 2-random then X is weakly 2-random.

(b) Show that if X is weakly 2-random then inf(a, 0′) = 0.

(c) In part (b) what if we assume only that X is random?

(d) Show that if X is 2-random then sup(a, 0′) = a′.

(e) In part (d) what if we assume only that X is weakly 2-random?

5. Show that every Π_{2}^{0} subset of 2^{ℕ} includes a Σ_{2}^{0,0′} set of the same measure.