11. Relative Computability and Turing Reduction

Kevin T. Kelly
Department of Philosophy
Carnegie Mellon University

Many-one reducibility is an interesting relation because it preserves recursiveness, r.e.-ness and co-r.e.-ness. These features are bought at a price. For example, the following properties are strange:

Exercise 1: Prove that

there are exactly 3 recursive m-degrees.
K does not m-reduce ØK.

These curiosities reflect the fact that m-reduction amounts to a very restrictive way to use a given decision procedure as a subroutine; namely, one may only compose another routine inside of it:

Q(x) = P(f(x)).

Thus, m-reduction does not allow for composition outside:

ØK(x) = -sg(K(x)).

Relative Computability

Such considerations suggest a notion of reducibility based on an unrestricted notion of subroutine. This is usually done with Turing machines that are allowed to ask arbitrary questions about a given set A and to use the results in their computations as they please. We can do essentially the same thing in Kleene's klean formulation of the theory by simply adding the characteristic function of A to the stock of basic functions and assigning it all indices of length 6.

k = 0 Þ f[A, n, k] = n;
k > 0 Þ

lh(n) = 0 Þ f[A, n, k] = C(o, p_1,k);
lh(n) = 1 Þ f[A, n, k] = C(s, p_1,k);
lh(n) = 2 Þ f[A, n, k] = p_{min(d(n,
0),
k),
k};
lh(n) = 3 Þ f[A, n, k] = C(f[d(n, 0), lh(d(n,1))], f[d(d(n, 1), 0), k], ..., f[d(d(n, 1), lh(d(n, 1)) -.1), k]);
lh(n) = 4 Þ f[A, n, k] = R(f[d(n, 0), k -. 1], f[d(n, 1), k + 1]);
lh(n) = 5 Þ f[A, n, k] = M(f[d(n, 0), k + 1]);
lh(n) = 6 Þ f[A, n, k] = C(c_A, p_1,k);
lh(n) > 6 Þ f[A, n, k] = C(o, p_1,k).

Now define

y is partial recursive in A Û $n, k, y = f[A, n, k];
W[A, n] = dom(f[A, n, 1]);
E[A, n] = rng(f[A, n, 1]).
B is recursive in A Û the characteristic function of B is partial recursive in A.
B is r.e. in A Û B = Æ Ú $ total f partialrecursive in A such that B = rng(f).

Proposition 1: All our earlier results relativize to A in the natural way.

Exercise 2: Convince yourself of this by stating and sketching the proof of the A-relativized universal theorem.
Let U[A] denote the A-relativized Kleene universal predicate.
Important: we will need the property that the "resource bound" also bounds all the inputs for which values are queried in the computation.

Turing Reduction

We may now define a more powerful kind of reduction relation called Turing reducibility (because it is usually defined using Turing machines as described above). Turing equivalence and degrees can be defined as before.

A £ B Û A is recursive in B;

Proposition 2:

£ is a pre-order;
£_m Ì £;
A £ ØA;
B is recursive, then B £ A;
recursiveness in A is preserved downward under £;
r.e.-ness and co-r.e.-ness in A are not preserved downward under £.

Exercise 3: Prove it. Note that the inclusion in 2 is proper!
-|

The last clause of the proposition shows that Turing reduction is also somewhat strange, for we can no longer rely on Turing computability to preserve one-sided notions of success. Can you think of a notion of reduction that does not restrict the use of subroutines but that would preserve r.e.?

By proposition 2.1, the usual mathematical habits yield Turing-equivalence and Turing-degrees:

A º B Û A £BÙ B £ A;
[A] = {B Í N: AºB}:
[A] £ [B] Û A £ B;

Turing degrees (or simply "degrees") are conventionally denoted by bold-faced letters: a, b, c, ...
Now define:

a is a G-degree Û a Ç G ¹ Æ
a is G-hard Û"b, b £ a.
a is G-complete Û a Ç G ¹ Æ Ù "b, b £ a.

Important: an r.e. degree is also a co-r.e. degree and not every element of an r.e. degree is r.e.

Corollary 3:

There is a unique recursive degree. Call it 0;
[A]_m Í [A];
[K] is r.e.-complete.

Proof: 1 comes from proposition 2.4. 2 and 3 come from proposition 2.2.
-|

The Jump Operation

The co-halting problem is just the counter-diagonal of the table

T[x, y] = W[x](y).

That is,

ØK(x) = -sg(T[x, x]) = -sg(W[x](x)).

We could do the same thing for the table of sets r.e. in A:

ØK[A](x) = -sg(W[A, x](x)).

Then we know (by exactly the same argument) that ØK[A](x) is not r.e. in A, so K is not recursive in A. The usual notation is:

A' = K[A] = {x: f[A, x](x)¯}.
a' = [A'], for some A Î a.

In our new notation, we have:

0' = [K].

The following records that jumps are essentially like the halting problem.
Proposition 4:

ØA' is not r.e. in A.
A' is not recursive in A.
A' is r.e. in A.
A' is A-r.e. m-complete.
A is recursive Þ A' º K.
A £ B ÞA' £ B'.

Proof:
1, 2. Already shown.
3. Using the A-universal construction, define A-partial recursive

f[A, z, 1](x) » myU[A](x, d(y, 0), d(y, 1), <x>).

Then A' = W[A, z].
4. Relativize the proof that K is r.e.-complete (with respect to m-reduction) and apply proposition 2.2.
5. Replace each occurrence of the characteristic function of A in the derivation tree with a program that computes it.
6. Suppose A £ B.
So let f[B, z] = c_A.
By the argument for part 3, A' is r.e. in A invirtue of

y(x) » my U[A](x, d(y, 0), d(y, 1), <x>).

In the derivation tree for y, we may replace each occurrence of c_Awith f[B, z].
Hence, A' is B-r.e.
By part 4, B' is B-r.e. complete.
So A' £ B'.
-|

Incomplete Degrees (Post's Problem)

Say that a is an incomplete r.e. degree Û

a is r.e.,
a is not r.e. complete.
a is not recursive.

Simple sets determine incomplete r.e. m-degrees as we have seen, but Turing degrees are coarser (since Turing reducibility is more lenient) so it doesn't follow that simple sets determine incomplete r.e. degrees. The worry is justified.

Proposition 5: Every r.e. degree (e.g., the complete one) contains a simple set.

Exercise 4: Prove it. Big hint:
Suppose B is r.e. but not recursive.
Construct a total recursive, bijective f such that B = rng(f).
Define

A(x) Û $y>x (f(y) < f(x)).

A is r.e. by the projection theorem.
Show:

A º B;
A is simple;
A º B;

More hints: To establish simplicity, assume that the required properties are false and then use f to decide A.
-|

Thus, a new technique is required to construct an incomplete r.e. Turing degree.

It suffices to find two non-recursive r.e. degrees such that neither is Turing reducible to the other, for an r.e.-complete degree is comparable with every r.e. degree.

The construction of such a degree was called Post's problem. The solution was discovered independently by Friedburg and Muchnik. The proof is called a "priority argument". The priority technique was applied to a number of problems in degree theory, leading to a renaissance in recursion theory in the 1960s and 1970s.

Proposition 6 (Friedburg-Muchnik 1956): There exist r.e. degrees a, b such that neither a£b nor b£ a.

Idea(following Soare's theorem 2.1): Here's the intuitive idea. An even requirement is a statement of form:

even(z) Ù c_A¹ f[B, z/2].

An odd requirement is a statement of form:

odd(z) Ù c_B¹ f[A, (z - 1)/2].

Clearly, satisfying all the requirements would make A and B Turing irreducible to one another.

Even requirement z can be satisfied by adding to A a witness x on which f[B, z/2] halts with 0 or never adding x to A if f[B, z/2] halts with 0.
Odd requirement z can be satisfied by adding to B a witness x on which f[A, (z - 1)/2] halts with 0 or never adding x to A if f[B, z/2] halts with 0. .

We can therefore use halting with 0 as an effective sign to add the witness to the appropriate set and rest smugly until the condition arises.

The trouble is that requirements we thought were "passively" satisfied may halt with 0 later. Such a requirement is said to require attention. Then we have to add the witness to the appropriate set to keep the requirement satisfied.

But this may screw up other computations witnessing other requirements, since these computations depend on the sets in question. We say that these requirements are injured.

To make progress, we have to protect more and more witnessing computations from injury. We do this by enumerating the requirements (a priori ranking) and protect higher priority witnessing computations from lower priority requirements by requiring that witnesses for fresh requirements be selected beyond a protective wall we build around the members of the sets queried in computations of higher priority.

Each requirement is injured only by requirements of higher prioriy. There are only finitely many of these. So each requirement is injured only finitely often. In the limit, every requirement is satisfied.

Since we never had to decide which way the requirements are satisfied, the sets constructed by adding witnesses are r.e.

This is called a priority or finite injury argument.

Proof: We need to construct r.e. sets A, B such that both are r.e. and neither is Turing-reducible to the other. We construct A, B in stages:

A(x) Û $nA[n](x).
B(x) Û $nB[n](x).

Each stage results from possibly adding something new.

A[n](x) Û$m£ n, add-to-A(m, x);
B[n](x) Û $m£ n, add-to-B(m, x).

We begin the construction by searching for the highest priority requirement that needs attention, if any.

attend-to(n) =

mz £ n
(even(z)Ù wall(n, z/2) = 0 Ù U[A[n]]( z/2, n, 0, <try( z/2, n)>)) Ú
(odd(z)Ù wall(n, (z - 1)/2) = 0 Ù U[A[n]]((z - 1)/2, n, 0, <try((z - 1)/2, n)>))
Seek the highest priority requirement whose protective wall is retracted and whose program has halted in the required number of steps with output 0.
if there is one;
n + 1 otherwise.

wall(0, z) = 0;
wall(n + 1, z) =

wall(n, z) if z <attend-to(n) Ú attend-to(n) > n;
(keep protecting higher-priority witnesses; do nothing if nothing is attended to)
n + 1 if z = attend-to(n);
(establish wall protecting currently attended to requirement)
0 if z > attend-to(n).
(drop protection on injured requirements indicating that they may again require attention)

Keep old witnesses unless a higher priority requirement gets attention. Then increment lower priority witnesses to a safe place.

try(0, z) = <0, z>;
try(n + 1, z) =

try(n, z) if z £attend-to(n) Ú attend-to(n) > n; (keep high priority witnesses).
mw d(w, 1) = z ÙØA[n](w) ÙØB[n](w) Ù"k< z, wall(n, z) < z otherwise. (injured witnesses should be selected so as not to disturb higher priority requirements).

add-to-A(n, x) Ûeven(attend-to(n)) Ù attend-to(n) £ n Ùx = try(n, attend-to(n)).
add-to-B(n, x) Ûodd(attend-to(n)) Ù attend-to(n) £ n Ù x = try(n, attend-to(n)).

Fact a: all the component functions are total recursive, so by the projection theorem A and B are r.e.
Fact b: every requirement is injured only finitely often.
Fact c: after it stops being injured, each requirement is eventually satisfied.
Hence, A and B are Turing-incomparable.
-|

A Taste of Degree Theory

Define:

A is low Û A' º K.

Proposition 7: A is low Þ A is not r.e.-complete.

Proof: Suppose A is r.e. complete.
So A ºK.
So A' ºK'.
K' is not reducible to K by proposition 4.2 above.
So A' is not reducible to K.
So A is not low.
-|

Define the join operation on sets and degrees as follows

(A + B)(x) = (A(d(x, 0)) Ù d(x, 1) = 0) Ú (B(d(x, 0)) Ù d(x, 1) = 1).
a È b = [A + B], for a(A), b(B).

Proposition 8: The meet operation is the greatest lower bound operation corresponding to the Turing reducibility order.
Thus, Turing degrees form an upper-semilattice under join.

Proof: In fact, A, B are both m-reducible to A + B, by means of the m-reductions d(x, 0) and d(x, 1).
For minimality, suppose that S also Turing-reduces both A and B.
Then A + B is reducible to S as well:
for a given x, d(x, 1) tells you whether to feed d(x, 0) through the reduction of A or the reduction of B.
-|

The importance of the low degrees is that they generate all the r.e. degrees when we close under join.

Proposition 8 (Sacks' splitting theorem 1963):
For each r.e. a > 0, there are incomparable, low r.e. degrees b, c such that a = bÈc.
-|

The r.e. degrees have many entertaining properties including the following:

(Lachlan 66) There is a minimal pair of r.e. degree above 0.
(Sacks 1964) The r.e. degrees are densely ordered.
(Shoenfield) Every countable partial order can be embedded in the r.e. degrees in a manner that preserves sups. E.g., each countable ordinal is embeddable.
(Yates 1966) Every incomplete r.e. degree is incomparable with some other r.e. degree.