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
There are currently no matching articles.