Distinct representative of the halting many-one degree Created 2026-09-24 Updated 2026-11-05
If , then
differs from , while the computable map proves .
The set is also a computably enumerable set, so the many-one completeness of the halting problem gives . Together the two many-one reductions place and in the same many-one degree.