Two sets have the same many-one degree when each many-one reduces to the other.
A many-one reduction can compile a source instance into a program whose domain of a function changes according to the successive finite stages of a simulation. The compiler must be a total computable function; the compiled program may diverge.
For example, let be the diagonal halting set. Compile into a program that, on input , uses a bounded simulation of a computation to test whether halts within steps. If no halt is seen, return zero; if a halt is seen, loop forever. The S-m-n theorem gives a total computable function producing the index of . ConsequentlyThe second set is a finite initial segment. Therefore if and only if belongs to the infinite-domain index set. This proves , and hence is not computably enumerable: preimages of computably enumerable sets under total computable functions are computably enumerable, whereas is not. The construction detects halting by finite evidence and never attempts to decide nonhalting.
Articles by others on the same topic
Many-one reduction, also known as **mapping reduction**, is a concept in computational complexity theory used to compare the difficulty of decision problems. It involves transforming instances of one decision problem into instances of another decision problem in such a way that the answer to the original problem can be easily derived from the answer to the transformed problem.