REGULAR_TM is undecidable

"Can my program's language be described by a regex?" is a natural classification question. It would be useful to know — regular languages have linear-time matchers, predictable behavior, no need for stack or tape. Sadly, the question is undecidable in general. This is the simplest example of a structural language property that Rice's theorem will later unify.

Reduce A_TM to REGULAR_TM. Given ⟨M, w⟩, build M' with two branches:

Why 0ⁿ1ⁿ? Because it's the canonical non-regular decidable language. The construction needs a "non-regular base case" that M' can recognize on its own; {0ⁿ1ⁿ} is the simplest.

• If M does NOT accept w · branch 2 never accepts. So L(M') = {0ⁿ1ⁿ} — not regular (pumping lemma).
• If M accepts w · branch 2 accepts every x. So L(M') = Σ* (everything from branch 1 ∪ branch 2) — regular.

So ⟨M, w⟩ ∈ A_TM ⇔ ⟨M'⟩ ∈ REGULAR_TM. A decider for REGULAR_TM ⇒ decider for A_TM. Contradiction ⇒ REGULAR_TM undecidable. ∎

Take M = "always halts and rejects" (so M(w) = reject for every w). Then for every choice of w:

• M does not accept w.
• Branch 2 never accepts.
• L(M') = {0ⁿ1ⁿ}, non-regular.
• ⟨M'⟩ ∉ REGULAR_TM.

Take M' = "always halts and accepts everything", w = anything. M accepts w. Branch 2 always accepts. L(M') = Σ*, regular. ⟨M'⟩ ∈ REGULAR_TM.

• E_TM (P6) · same trick, gadget = ∅ vs Σ*.
• CFL_TM · "is L(M) context-free?" — replace {0ⁿ1ⁿ} with a non-CF language like {0ⁿ1ⁿ2ⁿ}.
• FIN_TM · "is L(M) finite?" — gadget = {ε} vs Σ*.
• Rice's theorem (P14) · the master pattern: every nontrivial semantic property is undecidable.

1. Forgetting branch 1. Without the unconditional accept of 0ⁿ1ⁿ, L(M') = ∅ when M doesn't accept w — and ∅ is regular. The construction fails.
2. Confusing "regular" with "decidable". {0ⁿ1ⁿ} is decidable but not regular. The gadget needs decidable + non-regular.
3. "M' must be deterministic." Not required. The TM model here is the standard deterministic TM; M' just uses a polynomial gadget on its input.
4. Mixing up the direction. ⟨M, w⟩ ∈ A_TM ⇔ L(M') regular. Don't flip it.

• Q1. Why {0ⁿ1ⁿ}?
  Because it's not regular (pumping lemma) but is decidable. Any non-regular decidable language would work; this is the canonical choice.
• Q2. What if M loops on w?
  Then for x ∉ {0ⁿ1ⁿ}, M' loops. But L(M') = {0ⁿ1ⁿ} still — those are exactly the strings M' accepts. Looping on other strings doesn't add them to the language.
• Q3. Why doesn't this prove REGULAR_TM is not even recognizable?
  It only shows undecidability. To prove non-recognizability you'd argue: if REGULAR_TM were recognizable, by symmetric construction so would be ¬REGULAR_TM, contradicting the bridge theorem.
• Q4. Generalize: which other properties of L(M) is this proof template good for?
  Any nontrivial semantic property — that's Rice's theorem (Problem 14). Pick any pair of languages, one with property P and one without; build a similar gadget.

Total time: 8 minutes.

• (1 min) Motivate: "Can I tell if my program's language is regular?"
• (2 min) Construction of M' on the board with two branches.
• (2 min) Run the visualization. Pause between the two cases.
• (2 min) Two-case analysis: L(M') = {0ⁿ1ⁿ} or Σ*.
• (1 min) Tease Rice's theorem: this is one of many.