The halting contradiction and computable reductions

Prerequisites: Deciders, recognizers, program encodings, and proof by contradiction.

Learning objectives

• Reconstruct the halting diagonal argument.
• State the direction and correctness of a reduction.
• Distinguish an impossible general solver from useful restricted analyses.

Assume a solver and force a contradiction

Suppose H(program,input) always halts and correctly reports whether the given program halts on that input. Programs can be represented as finite strings, so a program can receive its own description as ordinary input. Construct another program D that behaves oppositely to H's prediction about self-application.

Pseudocode:
D(p):
    if H(p, p) says "halts":
        loop forever
    else:
        halt

Ask what happens when D receives its own description. If H predicts that D(D) halts, D deliberately loops. If H predicts it does not halt, D halts. Both possible answers contradict H's promised correctness. Therefore no total, always-correct H exists for all programs and inputs under this computation model. This is a proof about a universal specification, not a claim that no individual program's termination can be established.

Reductions carry impossibility to another problem

To show a target problem B is undecidable, start from a known undecidable problem A and computably transform each A instance x into a B instance f(x). Prove x belongs to A exactly when f(x) belongs to B. A hypothetical decider for B, composed with f, would then decide A, contradicting its undecidability. The direction matters: the unknown target must be the solver you could use to solve the already impossible problem.

For example, consider deciding whether a program ever prints the exact marker READY. Given a program P and input x, construct Q that simulates P(x), suppressing its output. If the simulation halts, Q prints READY; otherwise Q keeps simulating. Q prints the marker exactly when P(x) halts. A universal marker detector would therefore decide halting.

Useful tools can have narrower contracts

The theorem leaves room for tools that handle restricted languages, require termination annotations, return unknown, or make conservative approximations. A static analyzer can prove termination for a loop whose nonnegative counter decreases, yet decline to decide a complicated recursive program. A timeout can protect resources without proving nontermination.

Be precise about what a tool promises: sound conclusions, complete coverage, and total termination are separate properties. The contradiction rules out one particular combination for the unrestricted problem. It does not make verification pointless. Instead, it explains why practical verification relies on explicit assumptions, restricted models, human-supplied invariants, or a result space larger than a forced yes-or-no answer.

Practice problem

Assume someone offers a total tool Z that decides whether a program ever reaches a designated line. Reduce halting to this problem. Describe the generated wrapper, make sure the designated line cannot be reached accidentally during simulation, and prove both directions of the equivalence. Then diagnose this incorrect argument: “I can turn a reachability question into a halting question, and halting is undecidable, so reachability is undecidable.” Explain what is missing from that direction of reasoning.

Worked solution

Given P and x, generate a wrapper Q with a simulation phase followed by one unique designated instruction L. Q simulates P(x) inside the simulation mechanism and reaches L only after that simulation returns. If P halts on x, the wrapper eventually reaches L. If Q reaches L, its preceding simulation must have terminated, so P halted on x. A total Z applied to (Q,L) would therefore decide every halting instance, contradicting the theorem. Ensure L identifies the wrapper instruction, not a coincidentally similar instruction inside P. The incorrect argument reduces the target problem to a hard problem, which only gives an upper-bound relationship: even an easy problem can reduce to an undecidable one. To prove hardness, reduce the known hard problem into the target.

Check your understanding

To prove B undecidable using known undecidable A, which reduction is useful?

• Transform each A instance into an equivalent B instance.
• Transform B into A only.
• Show A and B use the same programming language.

Explanation

A solver for B must yield a solver for A, so A instances are transformed into B instances.

Which tool contract is consistent with the halting theorem?

• A total yes/no solver correct for every unrestricted program.
• A tool that proves some programs terminate and returns unknown for others.
• A timeout that proves every timed-out program runs forever.

Explanation

Allowing unknown avoids requiring a complete universal decision procedure.

Primary reading

• Automata, Computability, and Complexity: MIT OpenCourseWare

Open the study and save your work →