6.1. Turing Reductions

The concept of a reduction

---

Software designers use top-down design. The idea is, if you need a particular tool, assume that you have it. Later, create it.

The first part of top-down design is called reduction. To reduce problem A to problem B, just show that you can solve A provided that a solution to B is available.

For example, suppose that A is functional problem

A(n) = the smallest prime number that is greater than n

B = {n | n is prime}

  nextprime(n)
  k = n + 1
  while k ∉ B do
    k = k + 1
  end while
  return k

Oracle machines

---

Suppose that B is a computational problem (either a functional problem or a decision problem).

A B-machine is also called an oracle machine with oracle B.

It is not our concern how the oracle machine solves B. An oracle machine is just a mathematical concept.

Relative computability

---

Now suppose that A is another computational problem.

Turing reductions and reducibility

---

Suppose that A and B are two computational problems. For our purposes here, an algorithm must never go into an infinite loop. It must always give an answer.

Equivalently, A ≤_t B if there exists a Turing reduction from A to B.

The fundamental theorem of Turing reductions

---

What makes reductions useful is that they allow us to show that one problem is computable provided another is.

Proof. If B is computable, then we can take any program for a B-machine and turn it into a standard (non-oracle) machine by replacing uses of the extra instruction for B by a call to a function that solves B.

So the algorithm for A on a B-machine becomes just an algorithm for A.

Since there is an algorithm to solve A, A is computable. ◊

A sample Turing reduction

---

The halting problem for Turing machines is as follows.

HALT_TM = {(p, x) | p is a Turing machine and φ_p(x) ≠ ⊥}

We can reduce ACCEPT_TM to HALT_TM as follows.

  accept(p, x) (does p accept input x?)
  if (p, x) ∈ HALTTM then
    Run p on input x
    If p answers yes on x then
      answer yes
    else
      answer no
    end if
  else
    answer no
  end if       

So ACCEPT_TM ≤_t HALT_TM. By the fundamental theorem of Turing reductions,

if HALT_TM is computable then ACCEPT_TM is also computable.

Flipping Turing reducibility around

---

There is an important law of propositional logic called the Law of the Contrapositive.

P ⇒ Q  ⇔  ¬Q ⇒ ¬ P

The fundamental theorem of Turing reducibility can be expressed as follows.

Suppose that A ≤_t B. If B is computable then A is computable.

The second sentence is an implication. Let's replace it by its contrapositive.

Looked at this way, a Turing reduction is a way of showing that one problem is uncomputable based on the knowledge that another problem is uncomputable.

Proof. We have shown above that ACCEPT_TM ≤_t HALT_TM. On a previous page we showed that ACCEPT_TM is not computable. By the above corollary, HALT_TM is not computable. ◊

Turing reducibility is transitive

---

You can chain Turing reductions together. For example, if you find a Turing reduction from A to B, and you find another Turing reduction from B to C, then you can be assured that there is a Turing reduction from A to C.

Proof. Suppose that A ≤_t B and B ≤_t C. That is,

(1) A is computable relative to B.
(2) B is computable relative to C.

By (2), there must exist a C-algorithm R that solves B. So you can take any B-algorithm and turn it into a C-algorithm by replacing all uses of the instruction that solves B by a call to R.

By (1), there must be a B-algorithm that solves A. Turn that B-algorithm into a C-algorithm. Now we have a C-algorithm for A.

So A ≤_t C. ◊