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 . ThenConversely, a computable preimage of a recursively enumerable set is recursively enumerable.
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
There are currently no matching articles.