
Now that we have an mcomplete problem, we don't need to do generic reductions. Other problems can be found by reducing a know mcomplete problem to them.
Define language Y1, a set of programs, as follows.
Theorem. Y1 is mcomplete
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) = q_{p, x} where program q_{p, x} is as follows.
q_{p, x}(y) 1. Run program p on input x. 2. Answer yes.
Notice that
(p, x) ∈ HALT  
⇒ φ_{p}(x)↓  (by defn. of HALT) 
⇒ q_{p, x} accepts all inputs  (by inspection of q_{p, x}) 
⇒ q_{p, x} accepts 1  
⇒ q_{p, x} ∈ Y1  
⇒ R(p, x) ∈ Y1  (since R(p, x) = q_{p, x}) 
In the other direction:
R(p, x) ∈ Y1  
⇒ q_{p, x} ∈ Y1  (since R(p, x) = q_{p, x}) 
⇒ q_{p, x} accepts 1  (by defn. of Y1) 
⇒ φ_{p}(x)↓  (by inspection of q_{p, x}) 
⇒ (p, x) ∈ HALT  (by defn. of HALT) 
To summarize,
and R is a mapping reduction from HALT to Y1.
