Proving Undecidability by Reduction

Context: FIT2014_MOC · the exam hand skill of Week 9 — take the one language known undecidable (DIAGONAL HALTING PROBLEM) and mass-produce more with the transfer corollary of Mapping Reductions

Quick Revision

• 🎯 Objective: to prove $L$ undecidable, exhibit a computable $M\mapsto M^{\prime }$ with $M\in \text{DIAG-HALT}⟺⟨M^{\prime }⟩\in L$ ➔ $\text{DIAG-HALT}{\le }_{m}L$ and the corollary fires.
• 📦 Core Components: the universal gadget $M^{\prime }$ = “ignore your input; run $M$ on $M$” ➔ settles $\text{HALT FOR INPUT ZERO}$, $\text{ALWAYS HALTS}$, $\text{SOMETIMES HALTS}$ with one construction | the complement swap ➔ settles $\text{NEVER HALTS}$.
• ⚠️ Key Constraint: reduce from the known-undecidable language to the new one. $L{\le }_m\text{DIAG-HALT}$ is the wrong arrow and proves nothing.

📝 How It Works

1. The proof skeleton (four lines, always the same)

• Line 1 — fix the source ➔ “Let $M$ be any program, regarded as an input to the DIAGONAL HALTING PROBLEM.”
• Line 2 — define the image ➔ construct $M^{\prime }$ from $M$; the definition may mention $M$ freely but must never run a decider for anything.
• Line 3 — computability ➔ “The construction $M\mapsto M^{\prime }$ is computable” — $M^{\prime }$ is assembled by textual surgery on $⟨M⟩$, so a TM builds it and halts (totality is mandatory).
• Line 4 — the iff ➔ ”$M$ halts on input $M$ if and only if $M^{\prime }$ has property $\Pi$”, then conclude $\text{DIAG-HALT}{\le }_m{L}_{\Pi }$, therefore $L_{\Pi }$ is undecidable.

2. The universal gadget

$M^{\prime }$: Input: $x$. Body: run $M$ on input $M$.

• $x$ is discarded ➔ $M^{\prime }$ never reads its own input, so its behaviour is the same on every input — either it halts on all of them, or on none.
• Consequence ➔ halts on $0$, halts on $42$, always halts, and halts for some input all collapse into the single event ”$M$ halts on $M$“. One gadget, one iff, four theorems.
• ⚡ Key Constraint: $M^{\prime }$ is built, not run — the reduction outputs the string $⟨M^{\prime }⟩$. Nothing simulates $M$ at reduction time, which is why $f$ halts even though $M$ may not.

3. Reading off the family

Target problem $L$	Question asked of $P$	The iff the gadget certifies	Verdict
$\text{HALT FOR INPUT ZERO}$	halts on input $0$?	$M$ halts on $M$ $⟺$ $M^{\prime }$ halts on $0$	undecidable
$\text{HALT FOR INPUT 42}$	halts on input $42$?	$M$ halts on $M$ $⟺$ $M^{\prime }$ halts on $42$	undecidable
$\text{ALWAYS HALTS}$	halts on every input?	$M$ halts on $M$ $⟺$ $M^{\prime }$ always halts	undecidable
$\text{SOMETIMES HALTS}$	halts on some input?	$M$ halts on $M$ $⟺$ $M^{\prime }$ halts for some input	undecidable
$\text{NEVER HALTS}$	loops on every input?	complement of $\text{SOMETIMES HALTS}$	undecidable

• Nothing special about $0$ ➔ the constant is a free parameter, so the gadget generates an infinite family of undecidable problems at zero extra cost.
• Why $\forall$ and $\exists$ both work ➔ because $M^{\prime }$ is input-blind, the quantifier over inputs is vacuous — “for all $x$” and “for some $x$” agree, and both equal the single fact about $M$ on $M$.

4. The complement route — $\text{NEVER HALTS}$

• Not a mapping reduction ➔ the lecture calls it “a more general type of reduction”: a decider $D$ for $\text{NEVER HALTS}$ becomes a decider for $\text{SOMETIMES HALTS}$ by swapping Accept and Reject.
• What it spends ➔ exactly the closure of decidable languages under complement (Decidability and Decision Problems) — legal only because a decider always halts, so swapping its two halting states is well defined.
• Chain ➔ $\text{DIAG-HALT}{\le }_m\text{SOMETIMES HALTS}$, and $\text{NEVER HALTS}=\overline{\text{SOMETIMES HALTS}}$ decidable would make $\text{SOMETIMES HALTS}$ decidable. Contradiction.
• 💡 Do not try the swap on a recogniser ➔ swapping Accept/Reject on a machine with $\text{Loop}\ne \varnothing$ loses the looping inputs entirely; this is the asymmetry that makes $\overline{\text{HALT}}$ not even r.e. (Recursively Enumerable Languages).

📚 Catalogue of undecidable problems (lecture list — quotable without proof)

• About one TM ➔ does $P$ on input "What's the answer?" output "42"? · is $\text{Accept}(P)$ regular (is $P$ equivalent to a finite automaton)?
• About two TMs ➔ $\forall x:P\text{ halts on }x⟺Q\text{ halts on }x$ (do they always both halt or both loop)?
• About grammars ➔ is the language of a CFG regular? · does a CFG fail to generate some string over its alphabet? · do two CFGs define the same language? (contrast Deciding Properties of FAs and CFGs: CFG-Empty IS decidable, and RegExpEquiv IS decidable — equivalence survives for automata, dies for grammars.)
• Outside computation ➔ does a multivariate polynomial have an integer root? (Hilbert’s tenth problem; Matiyasevich, 1970) · the Post Correspondence Problem (string matching; Sipser §5.2, Emil Post).
• The pattern ➔ once a non-trivial semantic property of a machine’s language is asked, undecidability is the default; syntactic properties (state count, tape alphabet) stay decidable.

✍️ Practice

(the lecture’s “Decidable or Undecidable?” slide, posed without answers — write your verdict cold, then expand.)

Practice 1: Input: TM $P$, input $x$. Question: does $P$ accept $x$?

Reference solution

• Verdict: undecidable.
• Key move: the gadget again — send $M\mapsto M^{\prime \prime }$ where $M^{\prime \prime }$ ignores $x$, runs $M$ on $M$, and Accepts if that halts. Then $M$ halts on $M$ $⟺$ $M^{\prime \prime }$ accepts (any fixed) $x$, so $\text{DIAG-HALT}{\le }_m\text{ACCEPTANCE}$.

Practice 2: Input: TM $P$, input $x$, positive integer $t$. Question: does $P$ halt on $x$ in $\le t$ steps?

Reference solution

• Verdict: decidable.
• Key move: the bound is part of the input. Simulate $P$ on $x$ for at most $t$ steps with a UTM and answer; the simulation cannot run away, so $\text{Loop}=\varnothing$. Undecidability of halting comes entirely from the absence of a computable time bound.

Practice 3: Input: TM $P$, positive integer $s$. Question: does $P$ have $\le s$ states?

Reference solution

• Verdict: decidable.
• Key move: this is a syntactic question about $⟨P⟩$, not a semantic one about $\text{Accept}(P)$ — count the state blocks in the code word and compare. No execution is involved, so nothing can loop.

Practice 4: Input: TM $P$, positive integer $k$. Question: does $P$ halt for some input of length $\le k$?

Reference solution

• Verdict: undecidable.
• Key move: finitely many candidate inputs does not rescue you — each individual test is still a halting question. The input-blind gadget gives $M$ halts on $M$ $⟺$ $M^{\prime }$ halts on every input, in particular on $\epsilon$, whose length is $\le k$ for all $k\ge 0$.

⚠️ Common Mistakes

• 💡 Arrow reversed ➔ writing $L{\le }_m\text{DIAG-HALT}$ proves only that $L$ is no harder than something hard — compatible with $L$ being trivially decidable. The corollary needs the known-undecidable language as the source.
• 💡 Running $M$ inside the reduction ➔ if $f$ simulates $M$ to decide what to output, $f$ is not total and the transfer theorem collapses. The reduction only ever writes down $⟨M^{\prime }⟩$.
• 💡 Proving one implication ➔ ”$M$ halts on $M$ $\Rightarrow$ $M^{\prime }$ halts on $0$” is half a reduction; the converse is what forbids a No-instance from mapping to a Yes-instance.
• 💡 Skipping the computability line ➔ markers award a mark for stating $M\mapsto M^{\prime }$ is computable. It is one sentence and it is never free.
• 💡 Reusing the Accept/Reject swap on r.e. sets ➔ complementation is a property of deciders, not recognisers; using it on a merely-r.e. language is the single most common invalid step in this material.

🧠 Active Recall

Why does the same machine $M^{\prime }$ — "ignore $x$, run $M$ on $M$" — settle both $\text{ALWAYS HALTS}$ ($\forall$) and $\text{SOMETIMES HALTS}$ ($\exists$)?

Answer

• Short answer: $M^{\prime }$ is input-blind, so its halting behaviour is a constant function of the input — the $\forall$ and $\exists$ quantifiers range over a set on which the predicate is constant, hence they coincide.
• Why: Both reduce to one bit ➔ if $M$ halts on $M$ then $M^{\prime }$ halts on every $x$ (so it is in both $\text{ALWAYS}$ and $\text{SOMETIMES}$ $\text{HALTS}$); if not, $M^{\prime }$ halts on no $x$ (so it is in neither). The iff chain $M\in \text{DIAG-HALT}⟺⟨M^{\prime }⟩\in L$ is therefore valid for either target with the same construction.

"Halt in $\le t$ steps" is decidable but "halt" is undecidable. Where exactly does the difference live?

Answer

• Short answer: in who supplies the bound. When $t$ arrives as input, the simulation is guaranteed to terminate; when it does not, no computable function of $⟨P,x⟩$ can supply one — such a function would decide halting.
• Why: Decidability is about guaranteed termination, not about difficulty ➔ the bounded version has $\text{Loop}=\varnothing$ by construction, so it is a decider. Any attempted timeout for the unbounded version must either cut off a machine that would have halted later (unsound) or run forever (not a decider) — this is also why simulation makes $\text{HALT}$ only r.e. (Recursively Enumerable Languages).