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.
Codex Wiki