8.3. Using Reduction to Show Completeness

Now that we have an m-complete problem, we don't need to do generic reductions. Other problems can be found by reducing a know m-complete problem to them.


Another m-complete problem

Define language Y1, a set of programs, as follows.

Y1 = {p | p accepts input 1}

Theorem. Y1 is m-complete

Proof. We have already shown that Y1 is partially computable.

To show that Y1 is complete, it suffices to show that HALT ≤m Y1. Then, since Xm HALT for every partially computable language X, and ≤m is transitive, we also know that Xm Y1 for every partially computable language X.

Define R(p, x) = qp, x where program qp, x is as follows.

  qp, x(y)
  1. Run program p on input x.
  2. Answer yes.

Notice that

(p, x) ∈ HALT
  ⇒ φp(x)↓ (by defn. of HALT)
  ⇒ qp, x accepts all inputs (by inspection of qp, x)
  ⇒ qp, x accepts 1
  ⇒ qp, x ∈ Y1
  ⇒ R(p, x) ∈ Y1 (since R(p, x) = qp, x)

In the other direction:

R(p, x) ∈ Y1
  ⇒ qp, x ∈ Y1 (since R(p, x) = qp, x)
  ⇒ qp, x accepts 1 (by defn. of Y1)
  ⇒ φp(x)↓ (by inspection of qp, x)
  ⇒ (p, x) ∈ HALT (by defn. of HALT)

To summarize,

(p, x) ∈ HALT ⇔ R(p, x) ∈ Y1

and R is a mapping reduction from HALT to Y1.