EQ_TM is undecidable · mapping reduction

EQ_TM = {⟨M₁, M₂⟩ : L(M₁) = L(M₂)}. We want to show EQ_TM is undecidable by reducing A_TM to it. The trick is to pick one fixed machine (M₁) and engineer the other (M₂) so the equality question turns into the A_TM question in disguise.

Why this works: M₁ accepts the empty language, no matter what. M₂ either accepts every string or accepts no string, depending on whether M accepts w. So L(M₁) = L(M₂) exactly when L(M₂) = ∅, which is exactly when M does not accept w.

Let M be the TM that on input y, halts and accepts if y starts with a 1, otherwise loops. Pick w = "01".

• Compute M(w): "01" starts with 0, so M(w) loops. M does not accept w.
• Build M₁: rejecter. L(M₁) = ∅.
• Build M₂: on any input x, run M on "01"; that simulation loops; therefore M₂ never accepts. L(M₂) = ∅.
• Verdict: L(M₁) = L(M₂) = ∅, so ⟨M₁, M₂⟩ ∈ EQ_TM. And indeed ⟨M, "01"⟩ ∉ A_TM. The reduction's contract — ⟨M, w⟩ ∈ A_TM iff ⟨M₁, M₂⟩ ∉ EQ_TM — holds.

Now flip it: let w = "1xyz". Then M accepts w. M₂ on every input runs M on "1xyz", accepts, so L(M₂) = Σ*. L(M₁) = ∅ ≠ Σ* = L(M₂), so ⟨M₁, M₂⟩ ∉ EQ_TM. Contract holds again.

A mapping (many-one) reduction is a single computable function f, no loops, no oracle calls. Our f takes the encoding ⟨M, w⟩ and outputs the encoding ⟨M₁, M₂⟩. The construction is purely syntactic — write down two new TM descriptions. No simulation happens during the reduction itself; the simulation only happens later, if and when M₂ actually runs.

Because the reduction is many-one, undecidability transfers cleanly: if EQ_TM were decidable, composing with f would give a decider for ¬A_TM and hence for A_TM — contradiction. The same composition would not work for a Turing reduction without extra care.

• The reduction is to ¬EQ_TM, not EQ_TM. ⟨M, w⟩ ∈ A_TM corresponds to ⟨M₁, M₂⟩ not in EQ_TM. That's fine — undecidability of ¬EQ_TM implies undecidability of EQ_TM immediately, since L is decidable iff ¬L is.
• M₂ ignores its input. A common mistake is to write "M₂ on input x runs M on x." That doesn't work — you'd get L(M₂) = L(M), not Σ* or ∅. M₂ must ignore its input and always test M against the fixed string w.
• "Loops" is not "rejects" for L(M₂). If M on w loops, M₂ on every input runs M on w forever. M₂ doesn't accept anything in that case, so L(M₂) = ∅. We're using "doesn't accept" — looping is one way to not accept.
• The construction never runs M. The reduction is a syntactic transformation of strings — write the description of M₂ that says "simulate M on w." The actual simulation only happens later, if the EQ_TM-oracle decides to invoke M₂.

• Q1. Why use the empty-language M₁?
  It's a fixed reference. Comparing L(M₂) against ∅ is the same as asking whether L(M₂) = ∅, which is the E_TM question for M₂. So under the hood this reduction is showing EQ_TM is at least as hard as E_TM, which we already know is undecidable.
• Q2. Is EQ_TM recognizable?
  No. Neither EQ_TM nor ¬EQ_TM is Turing-recognizable. It sits in the "neither" region of the recognizable/decidable Venn diagram. This is a stronger statement than mere undecidability — both directions fail.
• Q3. What's the difference between a mapping reduction and a Turing reduction?
  A mapping reduction is a single computable function f that translates instances of A into instances of B such that x ∈ A iff f(x) ∈ B. A Turing reduction is an algorithm for A that uses an oracle (black box) for B and is allowed to make any number of queries and post-processing. Mapping is stricter; it preserves both decidability and Turing-recognizability.
• Q4. Why does mapping reduction preserve undecidability?
  If EQ_TM had a decider D, then "on input ⟨M, w⟩, output the opposite of D(f(⟨M, w⟩))" would decide A_TM. Since A_TM is undecidable, no such D exists.
• Q5. Could we have reduced to EQ_TM directly (not its complement)?
  Yes — swap which machine plays which role. Make M₁ the one that depends on M(w) and let M₂ be a reference Σ*-acceptor. Then equality holds iff M accepts w. Either direction gives undecidability; the version above happens to use the simpler ∅-reference.

Sipser: Theorem 5.4 and §5.3 on mapping reductions. Lecture notes: Module 2 slide 4 (reductions to HALT_TM) and Module 3 slide 1 (the general reduction template). Companion problems: P5 (HALT_TM), P6 (E_TM), P14 (Rice's theorem — generalises this kind of argument to every non-trivial language property).