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

Stephen G. Simpson

Due Monday, September 24, 2007

In this set of exercises we explore the structure of the Turing degrees. Given two Turing degrees a and b, we know that the least upper bound sup(a, b) always exists. Exercises 2, 4, and 7 below show that the greatest lower bound inf(a, b) sometimes exists and sometimes does not exist.

For any Turing oracle f we have

f′ = H^{f} = {x | φ_{x}^{(1),f}(0) ↓} = the Halting Problem relative to f.

We know that f′ is a complete Σ_{1}^{0} set relative to the oracle f. For any Turing degree a = deg_{T} (f) we define

a′ = deg_{T} (f′) = the Turing jump of a.

Clearly a < a′ holds for all a. Thus, starting with any Turing degree a, we have an ascending sequence of Turing degrees

a < a′ < a′′ < ⋯ < a^{(n)} < a^{(n+1)} < ⋯

In particular, starting with the zero Turing degree 0, we have the ascending sequence

0 < 0′ < 0′′ < ⋯ < 0^{(n)} < 0^{(n+1)} < ⋯

corresponding to the arithmetical hierarchy.

1. Given Turing oracles f and g, prove that the following conditions are pairwise equivalent:

(a) f ≤_{T} g

(b) H^{f} ≤_{m} H^{g}

(c) all partial f-recursive functions are partial g-recursive

(d) all total f-recursive functions are g-recursive.

2. Use finite approximations to construct Turing degrees a, b such that a > 0 and b > 0 and inf(a, b) = 0.

3. Use finite approximations to construct Turing degrees a, b such that a < 0′ and b < 0′ and sup(a, b) = 0′.

4. Combine and generalize Exercises 2 and 3 to prove the following:

Given two Turing degrees c, d such that c′ ≤ d, we can find two Turing degrees a, b such that inf(a, b) = c and sup(a, b) = d.

5. Prove the following result.

Given an ascending sequence of Turing degrees

d_{0} < d_{1} < ⋯ < d_{n} < d_{n+1} < ⋯

we can find a pair of Turing degrees a, b such that for all Turing degrees c

∃n (c ≤ d_{n}) if and only if c ≤ a and c ≤ b .

6. Use the result of Exercise 5 to prove that no ascending sequence of Turing degrees has a least upper bound.

7. For any pair of Turing degrees a, b as in Exercise 5, prove that the greatest lower bound inf(a, b) does not exist.