Many-one completeness of the halting problem
ID: many-one-completeness-of-the-halting-problem
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.
New to topics? Read the docs here!