Mapping Reductions and the Halting Problem

Undecidability results are rarely proved directly from a diagonal argument. The standard method proves one language undecidable and then moves the result around: show that a decider for the new language would yield a decider for the old one, and the new language inherits the impossibility. The transfer mechanism is a mapping reduction, and its direction is the part that is most often inverted by mistake.

The definition and the direction that matters

A mapping reduction from A to B is a computable function f such that for every string w, w ∈ A if and only if f(w) ∈ B. Written A ≤_m B. The function is total — defined on every string, not only on members of A — and computable by a machine that halts on every input. The “if and only if” makes it an exact correspondence between membership questions, not an implication in one direction.

The consequence runs backwards from the notation’s appearance:

• If A ≤_m B and B is decidable, then A is decidable. Decide A on input w by computing f(w) and running B’s decider on the result.
• If A ≤_m B and A is undecidable, then B is undecidable. Otherwise the first bullet would decide A.

The second form is the working tool. To prove B undecidable, find an undecidable A and a reduction A ≤_m B. Note that this reduces from the known-hard problem to the problem under investigation. A common error is to build B ≤_m A, which shows only that B is no harder than A — a statement that is trivially satisfied when B is decidable.

Three properties of ≤_m are worth stating because they are used silently. It is transitive: compose the two computable maps, and composition of computable functions is computable. It is preserved under complement, in the reversed direction: if f reduces A to B then the same f reduces the complement of B to the complement of A, because the biconditional holds for every string and its two sides can be negated together. And it is not symmetric in general, which is why the notation is an order rather than an equivalence.

Why a reduction is more than a restatement

A reduction that merely re-encodes the input does no work. The content of a good reduction is that it constructs a new machine whose behaviour on all inputs is controlled by a property of the original input. The constructed machine must be well defined for every input, including inputs where the property fails, and its description must be produced by an algorithm that always halts.

This is the difference between proving a theorem and asserting one. “M halts on w” and “the machine that ignores its input and simulates M on w accepts everything” are related, but the relation is a claim that needs a construction: given ⟨M, w⟩, emit the description of a machine with a hardwired copy of M and w, which on any input runs the simulation and accepts. That construction is a few lines of a program that writes a program, and its correctness is checked by cases on whether M halts.

Halting from acceptance

Let HALT = {⟨M, w⟩ : M halts on w}, where halting includes both accepting and rejecting. The claim is that A_TM ≤_m HALT, which makes HALT undecidable given the result in Encoding Turing Machines and the Undecidability of Acceptance.

The reduction is nearly the identity, with one modification: it must convert “accepts” into “halts”. Given ⟨M, w⟩, construct M′ that runs M on w and, if M ever enters a rejecting state, enters an infinite loop that moves the head right forever; if M accepts, M′ halts immediately. Then M′ halts on w exactly when M accepts w, because the only way M halts without accepting is the rejecting branch, which M′ converts into divergence. So ⟨M, w⟩ ∈ A_TM iff ⟨M′, w⟩ ∈ HALT. The map is computable: it copies the description of M, rewires the reject state to the loop, and leaves everything else alone, which is a uniform syntactic edit across all M.

The direction HALT ≤_m A_TM is what makes the two problems equivalent in difficulty. Given ⟨M, w⟩, construct M″ that runs M on w and accepts if M halts at all — regardless of whether M accepted or rejected. Then M″ accepts w exactly when M halts on w, so membership transfers in both directions and neither problem is easier than the other.

That mutual reducibility is why the two problems are often treated as one. Both directions matter for different purposes: A_TM ≤_m HALT is the step that carries the impossibility across, and HALT ≤_m A_TM is what licenses any later argument that starts from halting and concludes something about acceptance. It also shows that a reduction can be almost trivial and still be the whole proof: the work is in constructing the wrapper machine correctly for every input, not in a clever encoding.

The diagonal form of the halting problem

There is a second, independent proof that halting is undecidable, and comparing the two is instructive. Suppose a machine H decides HALT. Build D that on input ⟨M, w⟩ runs H on ⟨M, w⟩ and then does the opposite: if H says M halts on w, D loops forever, and if H says M does not halt on w, D halts and accepts. Now run D on the pair ⟨D, ⟨D⟩⟩, so that the machine under discussion is D itself and the input under discussion is D’s own description. If D halts on ⟨D⟩, then H reported that D halts, so D’s looping branch was taken and it does not halt. If D does not halt, H reported that, so D’s accepting branch was taken and it halts. Neither outcome is consistent.

The structure is the same as the acceptance diagonal, with “loop” replacing “reject” as the negated outcome, and with the self-application shifted from one argument to two. This proof needs no separate result about acceptance, which makes it the more economical starting point. It also makes the role of the encoding explicit: D must be applicable to its own description, which requires the totality of the encoding established earlier.

Both proofs are valid, and the reduction chain A_TM ≤_m HALT is what makes the second one extend to other problems: the diagonal is done once, and each further result is then a local construction on top of HALT. A fresh diagonal argument has to be re-run and re-checked for every target language, which is why it is the rarer form.

A worked reduction onto the emptiness problem

Let E = {⟨M⟩ : L(M) = ∅}, the set of machines that accept nothing. The wrapper construction here is the smallest one in the subject, and it also shows how the polarity of the target set has to be tracked.

Given ⟨M, w⟩, construct M′ that on input x ignores x entirely, runs M on w, and accepts if and only if M accepts. The description of M′ is produced by copying ⟨M⟩ and ⟨w⟩ into a template, so the map is computable and total. Two cases follow. If M accepts w, then M′ accepts every input, so L(M′) = Σ*, which is non-empty and therefore not in E. If M does not accept w, then M′ accepts nothing, so L(M′) = ∅ and M′ is in E. So the reduction lands on the complement: A_TM ≤_m complement(E).

That is enough to conclude, and the reason is worth stating. Undecidability is preserved under complement, since a decider for a set yields a decider for its complement by swapping the accept and reject states. So if complement(E) is undecidable, E is undecidable as well. The reduction proves the theorem about E without ever mapping into E directly.

The polarity check is not pedantry. Choosing the wrapper the other way — accepting when M rejects, or running M’s simulation on the input x rather than on a hardwired w — changes which set the reduction lands on, and a reduction onto the wrong one proves a different theorem about a different set. The cases above must be enumerated for the specific wrapper, not assumed from the shape of the construction.

def halts_within(delta, start, accepting, tape, bound):
    """Bounded simulation of a single-tape machine. Decidable for every bound.

    delta: dict (state, symbol) -> (state, symbol, 'L'|'R')
    tape:  dict cell index -> symbol, mutated in place
    """
    head, state = 0, start
    for _ in range(bound):
        if state in accepting:
            return True
        move = delta.get((state, tape.get(head, 'B')))
        if move is None:
            return False
        state, write, direction = move
        tape[head] = write
        head += 1 if direction == 'R' else -1
    return False

The bounded simulation is the gadget that makes a step count into a decision. For a fixed bound it always halts, so the question “does this machine accept within n steps” has an algorithmic answer, and the bound is part of the input to the simulation rather than something the machine computes for itself. The unbounded question is the same loop with the counter removed.

Where reductions stop working

Mapping reductions are strong enough for the standard undecidability results but not for everything. Two limitations are worth naming.

First, ≤_m is sensitive to recognizability in a way that makes some natural questions awkward. A_TM is recognizable, because simulation settles the accepting case, while its complement is not, as the complement criterion shows. A_TM and HALT are both recognizable and mutually ≤_m-equivalent, and no mapping reduction distinguishes their difficulty. Revealing the asymmetry takes a different tool: a recognizability-preserving reduction in the reverse direction, or a change to Turing reducibility, where an oracle for one problem may be queried adaptively.

Second, reductions prove undecidability, never decidability. A reduction A ≤_m B with A undecidable rules out a decider for B, and nothing more. The order is also coarse: ≤_m records computability alone, so two problems that are mutually reducible may differ by any amount in the resources needed to decide their decidable restrictions. Quantitative statements need the resource-bounded analogue of the same idea, which belongs to a different subject. What stays inside this one is the semantic version: Rice’s Theorem and the Collapse of Semantic Properties shows that for whole classes of properties, no reduction is needed at all, because none of them is decidable.