|
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.
Define language Y1, a set of programs, as follows.
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 X ≤m HALT for every partially computable language X, and ≤m is transitive, we also know that X ≤m 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,
and R is a mapping reduction from HALT to Y1.
|