Every recursively enumerable set many-one reduces to the diagonal halting set. If a program halts exactly on , the S-m-n theorem produces from an index for a unary program that ignores its input and performs that computation on . Then
Conversely, a computable preimage of a recursively enumerable set is recursively enumerable.
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.

Articles by others on the same topic (0)

There are currently no matching articles.