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

Stephen G. Simpson

Due Monday, October 22, 2007

1. Let K(τ) denote the prefix-free complexity of a bitstring τ. Prove that

K(τ_{1}^{⌢}τ_{2}) ≤ K(τ_{1}) + K(τ_{2}) + O(1) .

2. (a) Give an example of a subset of ℕ^{ℕ} which is Σ_{2}^{0} but not Σ_{1}^{0,0′}.

(b) Can you replace ℕ^{ℕ} by 2^{ℕ} here?

Note: Recall Post’s Theorem, which says (among other things) that a subset of ℕ is Σ_{2}^{0} if and only if it is Σ_{1}^{0,0′}. The point of (a) is to show that Post’s Theorem does not hold for subsets of ℕ^{ℕ}.

Hint: Recall that a set is open if and only if it is Σ_{1}^{0} relative to an oracle. Therefore, it suffices to find a set which is Σ_{2}^{0} and not open.

3. A real number is said to be left recursively enumerable (respectively right recursively enumerable) if it is the limit of an increasing (respectively decreasing) recursive sequence of rational numbers.

(a) If A is a recursively enumerable subset of ℕ, show that the real number ∑_{n∈A} 1/2^{n} is left recursively enumerable.

(b) Show that there exist real numbers which are left recursively enumerable but not recursive.

(c) Show that a real number is recursive if and only if it is both left recursively enumerable and right recursively enumerable.

4. Let P be a Π_{1}^{0} subset of 2^{ℕ}. We have seen how to construct a recursive tree T ⊆ 2^{<ℕ} such that P = {paths through T }. For each n = 0, 1, 2, … let T_{n} be the set of strings in T of length n.

(a) Show that T_{n} is prefix-free.

(b) Show that the set

V_{n} = ⋃_{τ∈T_{n}} N_{τ}

is Δ_{1}^{0}. (Note that V_{n} is a subset of 2^{ℕ}.)

(c) Show that P is the intersection of the V_{n}’s. In other words,

P = ⋂_{n=0}^{∞} V_{n} .

(d) Show that the measure of P is given by

μ(P) = lim_{n→∞} \frac{|T_{n}|}{2^{n}} .

Here |T_{n}| denotes the number of strings in T_{n}.

(e) Show that the real number μ(P) is right recursively enumerable.

(f) Show that μ(P) is not necessarily a recursive real number.

5. Given a nonempty Π_{1}^{0} set P ⊆ 2^{ℕ}, can we always find a member of P which is recursive?

Hint: Consider a recursively inseparable pair of r.e. sets.

6. Two sets P, Q ⊆ ℕ^{ℕ} are said to be Turing isomorphic if the members of P and Q have the same Turing degrees, i.e.,

{deg_{T} (f) | f ∈ P } = {deg_{T} (g) | g ∈ Q} .

(a) Prove that every Π_{2}^{0} subset of ℕ^{ℕ} is Turing isomorphic to a Π_{1}^{0} subset of ℕ^{ℕ}.

(b) Prove that every Π_{2}^{0} subset of ℕ^{ℕ} is Turing isomorphic to a Π_{2}^{0} subset of 2^{ℕ}.

(c) Is every Π_{2}^{0} subset of 2^{ℕ} Turing isomorphic to a Π_{1}^{0} subset of 2^{ℕ}? Justify your answer.

Hints: (a) If ∀x ∃y R(f, x, y) holds, map f to f ⊕ g where g(x) = μy R(f, x, y). (b) Map f to the characteristic function of the set G_{f} = {3^{x}5^{y} | f(x) = y} = the “graph” of f.