Reductions, degrees, and undecidability

For subsets A and B of the natural numbers, a many-one reduction is a total computable function f with x in A exactly when f(x) is in B. Totality is essential: a translator that waits for an undecidable positive event before returning a target instance is not a valid reduction on all inputs. If B has a decider, applying f and then that decider decides A. Therefore undecidability of A proves undecidability of B, not the other way around.

The reductions here concern computability and need not run in polynomial time. They resemble reductions in complexity theory, but the resource restriction has changed. A computable transformation of program descriptions can embed an input as a constant and add a fixed simulation wrapper. With a standard acceptable numbering, the resulting index depends totally computably on the embedded input. This is the effective parameterization property, often formalized by the s-m-n theorem.

Let W sub e denote the domain of the partial function computed by program e. To test whether that domain contains at least three inputs sounds like a finite threshold question, but there is no bound on the time needed to discover the third input. A wrapper can make its whole domain depend on whether one selected simulation ever halts. The wrapper's source is easy to write even when predicting its eventual behavior is impossible.

Rice's theorem generalizes this pattern: every nontrivial property depending only on the computed partial function has an undecidable index set, under the standard effective numbering. Nontrivial means some partial computable function has the property and another does not. A property of source spelling, such as whether an instruction occurs, is not necessarily semantic and is outside this statement. We prove the particular domain-threshold case directly below rather than relying on the general theorem as an unexplained slogan.

A Turing reduction of A to B is an oracle program that decides membership in A using membership answers for B, with finitely many queries on each completed input computation. Many-one reducibility implies Turing reducibility through one query, but an oracle program may negate answers or choose later queries from earlier results. Mutual Turing reducibility defines a Turing degree. That equivalence does not identify all the finer many-one distinctions.

For example K and its complement have the same Turing degree: one oracle query followed by Boolean negation decides the other. Yet the complement cannot many-one reduce to K, because a computable preimage of a c.e. set is c.e., while the complement of K is not c.e. Conversely, K cannot many-one reduce to its complement, since the preimage would be co-c.e., making K both c.e. and co-c.e. Thus the distinction is witnessed by these concrete sets, not merely by notation.