|
It turns out that our old friend the halting problem is among the hardest of the partially computable problems.
Theorem. HALT is m-complete.
Proof. This proof uses a generic reduction. We know that HALT is partially computable. So, to show that HALT is m-complete, we just need to show that every partially computable language X mapping-reduces to HALT.
Choose an arbitrary partially computable language X. Since X is partially computable, there must be a program U that partially computes X. That is,
Now define function R by
Notice that
| y ∈ X | ⇔ | φU(y)↓ | (by (1)) |
| ⇔ | (U, y) ∈ HALT | ||
| ⇔ | R(y) ∈ HALT | (by (2)) |
So R is a mapping reduction from X to HALT.
|