Computable Reductions and Rice's Theorem: Examples and Counterexamples

From $⟨<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>,\widehat{w}⟩$, build a machine $N_{M,w}$ that ignores its own input, simulates $M$ on $w$, and accepts exactly when that simulation accepts. Then $L(N_{M,w})\mathrm{\ne }\mathrm{\varnothing }$ exactly when $M$ accepts $w$. So this construction gives a many-one reduction from $A_{TM}$ to ${\mathrm{N}\mathrm{O}\mathrm{N}\mathrm{E}\mathrm{M}\mathrm{P}\mathrm{T}\mathrm{Y}}_{TM}$.

If ${\mathrm{N}\mathrm{O}\mathrm{N}\mathrm{E}\mathrm{M}\mathrm{P}\mathrm{T}\mathrm{Y}}_{TM}$ were decidable, [L1] would make $A_{TM}$ decidable, contradicting [L2]. Thus the nonemptiness problem is undecidable. More generally, recognizability of a target pulls backward along a many-one reduction, while the contrapositive pushes nonrecognizability of the source forward to the target.

Because no transition ever enters $q_{dead}$, the computation of $M^{\mathrm{\prime }}$ on every input follows exactly the same states, tape symbols, and head moves as the computation of $M$. Hence $L(M^{\mathrm{\prime }})=L(M)$.

Even so, $M^{\mathrm{\prime }}$ has a different state count and visibly has an unreachable state. Step 1.1 therefore gives a concrete instance of [L1]: the code-level property changes while the language does not.

The map $r$ reverses membership relative to $B$: the yes-instance $0\in A$ is sent to $0\mathrm{\notin }B$, while every no-instance $x\mathrm{\notin }A$ is sent to $1\in B$. In particular, already at $x=0$ the biconditional required by [L1] fails, so $r$ is not a many-one reduction from $A$ to $B$.

The same map does satisfy $x\in A⟺r(x)\in \bar{B}$, so it is a reduction from $A$ to $\bar{B}$. Thus an answer-reversing transformation changes the target to its complement and is not a valid reduction to $B$; this refutes [L2].