III Logic - Computability theory

3Computability theory

III Logic

3.6 Reducibility

We’ve alluded to the notion of reducibility several times previously. For example,

we had two versions of the halting set, and said that if we could decide membership

of one of them, then we can decide membership of the other. When we proved that

there is a decidable partition of

(3)

with no infinite decidable monochromatic

set, we said if we had such a thing, then we could use it to solve the halting

problem.

The general idea is that we can often “reduce” one problem to another one.

The most basic way of expressing this is via many-to-one reducibility.

Definition

(Many-to-one reducibility)

Let

A, B ∈ N

. We write

B ≤

there exists a total computable functions

N → N

such that for all

n ∈ N

, we

have n ∈ B ↔ f(n) ∈ A.

Thus, if we have such a set, then whenever we can correctly answer questions

about membership in

, then we can answer questions about membership in

It is easy to see that this is a quasi-order. If we take the intersection

≤

∩ ≥

of the relations, then we get an equivalence relation. The equivalence classes are

called many-one degrees. We think of these as “degree of unsolvability”.

Proposition. Let A ⊆ N. Then A ≤

K iff A is semi-decidable.

This is a technical exercise. Another useful fact is the following:

Proposition. (N \ K) ≤

A iff A is productive.

But it turns out this is a rather awkward definition of “relative computability”.

In our definition of many-one reducibility, we are only allowed to run

once,

and see if the answer is in A. But why once?

The idea is define reducibility semantically. We assume that when writing

programs, we can do all the usual stuff, but also have access to a magic function

, and we are allowed to call

as many times as we wish and use the results.

We call

an oracle. For our purposes,

is the (total) characteristic function of

For technical reasons, we will suppose we have a fixed programming language

that just refers to an opaque function

, and then we can later plug different

things as

. This allows us to compare G¨odel numberings for functions with

different oracles.

Definition

(Turing reducibility)

We say

B ≤

, or simply

B ≤ A

, if it is

possible to determine membership of

whenever we have access to an oracle

that computes χ

Again

≤

is a quasi-order, and intersecting with the reverse, we get an

equivalence relation, which we call Turing degree, or just degree.

Now the quasi-order gives us a relation on Turing degrees. A natural question

to ask is if this is actually a total order.

To begin with, Turing degrees certainly form an upper semi-lattice, as given

and

, we can form the disjoint union of

and

, and knowing about

membership of

means we know membership of

and

, and vice versa.

But are they linearly ordered by ≤? The answer is no!

Theorem

(Friedberg–Muchnik)

There exists two

A, B ⊆ N

such that

A 6≤ B 6≤

A. Moreover, A and B are both semi-decidable.

Proof. We will obtain the sets A and B as

A =

[

n<ω

, B =

[

n<ω

where

and

are finite (and in particular decidable) and nested, i.e.

i < j

implies A

⊆ A

and B

⊆ B

We introduce a bit of notation. As mentioned, if we allow our programs to

access the oracle

, then our “programming language” will allow consultation of

. Then in this new language, we can again assign G¨odel numbers to programs,

and we write

{e}

for the program whose G¨odel number is

. Instead of inventing

a new language for each

, we invent a language that allows calling an “oracle”,

without specifying what it is. We can then plug in different sets and run.

Our objective is to pick A, B such that

6= {e}

for all e. Here we are taking χ

to be the total version, i.e.

(x) =

(

1 x ∈ A

0 x 6∈ A

The idea is, of course, to choose

such that it prevents

from being

{m}

and vice versa. But this is tricky, because when we try to pick

, we don’t

know the whole of B yet.

It helps to spell out more explicitly what we want to achieve. We want to

find some n

, m

∈ N such that for each i, we have

(i)

) 6= {i}

(i)

)

(i)

) 6= {i}

(i)

)

These n

and m

are the witness to the functions being not equal.

We now begin by producing infinite lists

= {n

(i)

, n

(i)

, · · · }

= {m

(i)

, m

(i)

, · · · }

of “candidate witnesses”. We will assume all of these are disjoint. For reasons

that will become clear later, we assign some “priorities” to these sets, say

> M

> N

> M

> N

> · · · .

We begin by picking

= B

= ∅.

Suppose at the

th iteration of the process, we have managed to produce

t−1

and

t−1

. We now look at

, . . . , N

and

, · · · , M

. If they have managed to

found a witness, then we leave them alone. Otherwise, suppose

hasn’t found

a witness yet. Then we run

{i}

t−1

(

(i)

) for

many time steps. We consider

the various possibilities:

–

Let

be the first remaining element of

. If

{i}

t−1

(

) halts within

steps and returns 0, then we put

into

, and then pick this as the

desired witness. We now look at all members of

t−1

our computation of

{i}

t−1

has queried. We remove all of these from all sets of lower priority

than N

– Otherwise, do nothing, and move on with life.

Now the problem, of course, is that whenever we add things into

, it

might have changed the results of some previous computations. Suppose we

originally found that

{

}

(32) = 0, and therefore put 32 into

as a witness.

But later, we found that

{

}

(70) = 0, and so we put 70 into

. But if the

computation of

{

}

(32) relied on the fact that 70

6∈ B

, then we might have

{10}

(32) 6= 0,

and now our witness is “injured”. When this happens, we forget the fact that we

picked 32 as a witness, and then pretend

hasn’t managed to find a witness

after all.

Fortunately, this can only happen because

is of higher priority than

and thus 70 was not forbidden from being a witness of

. Since there are only

finitely many things of higher priorities, our witness can be injured only finitely

many times, and we will eventually be stabilized.

We are almost done. After all this process, we take the union and get

and

. If, say,

{i}

has a witness, then we are happy. What if it does not?

Suppose

{i}

is some characteristic function, and

is the first element in the

list of witnesses. Then since the lists of candidate witnesses are disjoint, we

know

m 6∈ B

. So it suffices to show that

{i}

(

)

= 0. But if

{i}

(

) = 0,

then since this computation only involves finitely many values of

, eventually,

the membership of these things in

would have stabilized. So we would have

{i}

(m) = 0 long ago, and made m a witness.