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

Stephen G. Simpson

Due Monday, November 26, 2007

1. (a) Let P be a Π_{1}^{0} subset of 2^{ℕ}. If P has only finitely many elements, prove that all of the elements of P are recursive. Hint: Use Lemma 48.3, a.k.a., the Magic Lemma.

(b) Does this hold with ℕ^{ℕ} instead of 2^{ℕ}?

2. (a) Let P ⊆ 2^{ℕ} be nonempty Π_{1}^{0} with no recursive elements. Prove that for all Y we can find X ∈ P such that X′ ≡_{T} X⊕0′ ≡_{T} Y ⊕0′. Note: This result is a combination of the Low Basis Theorem and the Friedberg Jump Inversion Theorem. The proof is basically a combination of the two proofs.

(b) Deduce that for all Y we can find a random X such that X′ ≡_{T} X ⊕ 0′ ≡_{T} Y ⊕ 0′.

3. Recall that we have defined

K(n) = K(⟨\underbrace{1, …, 1}_{n}⟩)

for all n ∈ ℕ.

Prove that

K(τ) ≤ C(τ) + K(C(τ)) + O(1)

for all bitstrings τ.

4. Assume that f(n) is a recursive function such that

∑_{n=0}^{∞} \frac{1}{2^{f(n)}} < ∞ .

Prove that K(n) ≤ f(n) + O(1) for all n.