E_TM is undecidable

"Is this program's language empty?" is one of the most basic questions you can ask about a TM — and it is undecidable. This means: there is no algorithm that, given an arbitrary program, can tell you whether it ever produces any output on any input. Practical examples: "does this regex with backreferences match any string?" "does this program have any reachable accepting path?" — undecidable in general.

We turn a question about M accepting one specific input w into a question about a new machine M' accepting anything at all. The trick: hard-code w inside M', and have M' ignore its input.

Note ⟨M, w⟩ is finite, so writing M' down is computable. The map ⟨M, w⟩ ↦ ⟨M'⟩ is the reduction.

Two cases:

• If M accepts w · Every x triggers the accept branch ⇒ L(M') = Σ* ⇒ ⟨M'⟩ ∉ E_TM.
• If M does NOT accept w (rejects or loops) · Every x makes M' reject or loop ⇒ L(M') = ∅ ⇒ ⟨M'⟩ ∈ E_TM.

So ⟨M, w⟩ ∈ A_TM ⇔ ⟨M'⟩ ∉ E_TM. If we had a decider for E_TM, we could build a decider for A_TM (run the E_TM-decider, flip the answer). Impossible ⇒ E_TM is undecidable. ∎

Take M = "accept iff input length is a multiple of 3", w = "aaaaaa" (length 6).

• M(w) = accept (6 ≡ 0 mod 3).
• So M' on any x: runs M on "aaaaaa", which accepts, then M' accepts x.
• L(M') = Σ*. ⟨M'⟩ ∉ E_TM.

Now change w to "aaaaa" (length 5).

• M(w) = reject.
• M' on any x: runs M on "aaaaa", which rejects, M' never accepts.
• L(M') = ∅. ⟨M'⟩ ∈ E_TM.

The "membership in A_TM" question (does M accept w?) became "is L(M') empty?" — a question about E_TM.

• REGULAR_TM (Problem 7) · "Is L(M) regular?" Same construction trick: make L(M') simple iff M accepts w.
• EQ_TM (Problem 8) · "Do M₁, M₂ recognize the same language?" Even stronger — not even recognizable.
• Rice's theorem (Problem 14) · The grand generalization: any non-trivial property of L(M) is undecidable.
• Halting · A_TM ≤_m HALT_TM ≤_m E_TM — a chain of reductions all going through the same trick.

1. "M' runs M on x, not on w." No! M' runs M on the fixed w that's hard-coded inside M'. Otherwise the trick fails.
2. Reducing the wrong direction. We need A_TM ≤ E_TM, not the other way. The known-undecidable problem must be the source.
3. Confusing ¬E_TM with E_TM. The reduction gives M accepts w ⇔ L(M') = Σ*, which is ⟨M'⟩ ∉ E_TM. So we reduce to the complement; that still shows E_TM undecidable.
4. "M' must halt to be a valid TM." No — a TM is valid even if it loops on every input. L(M') = ∅ is perfectly legal.
5. Trying to make L(M') = {w}. Tempting but wrong. The trick is L(M') = Σ* vs ∅, because that's the question E_TM asks about.

• Q1. Why does M' "ignore" its input?
  Because we want L(M') to be either everything or nothing — a binary signal mirroring M's acceptance of the fixed w. Ignoring x kills any dependence on x.
• Q2. Does this construction halt?
  M' halts (and accepts) iff M halts (and accepts) on w. If M loops on w, M' loops on every x. That's fine — we only need ⟨M'⟩ to encode the membership question.
• Q3. Is this a mapping reduction or Turing reduction?
  Mapping reduction. The function ⟨M, w⟩ ↦ ⟨M'⟩ is computable and preserves the membership question.
• Q4. Is E_TM co-recognizable?
  Yes. ¬E_TM is recognizable: enumerate strings w₁, w₂, …; run M on each in parallel; accept as soon as any one accepts.
• Q5 (bonus). Place E_TM in the Venn diagram (Problem 4).
  co-Rec \\ Dec. Because ¬E_TM is recognizable (Q4) and E_TM is undecidable (proven here).

Total time: 10 minutes.

• (1 min) State the question: "is L(M) empty?" Hook: connect to "does this program ever produce output?"
• (2 min) Write the construction of M' on the board. Stress: x ignored, w hard-coded.
• (2 min) Run the visualization. Pause when M' is constructed and L(M') is computed.
• (2 min) Work out the two cases explicitly: L(M') = Σ* vs L(M') = ∅.
• (2 min) Worked example with concrete M and w.
• (1 min) Forward link to Rice's theorem.