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.

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.