FINITE_TM is undecidable

FINITE_TM = {⟨M⟩ : L(M) is finite}. Direct application of Rice (Problem 14): "finite" is a nontrivial property of L(M), so FINITE_TM is undecidable.

M' on input x:
  if |x| ≤ 10 then accept           // finite chunk: ≤ 10
  else run M on w
       if M accepts then accept x

• Don't conflate "finite" with "small." Finite means there's a bound, no matter how huge. Even 10¹⁰⁰ elements is finite.
• The reduction is to ¬FINITE_TM. ⟨M, w⟩ ∈ A_TM ⇔ L(M') is infinite ⇔ ⟨M'⟩ ∉ FINITE_TM.
• The "finite chunk" trick keeps L(M') non-empty in both cases. Without it, "M doesn't accept w" would make L(M') empty, but FINITE includes ∅, so we'd still be fine — the chunk just makes the semantic boundary cleaner.

• Q1. Why use a fixed finite chunk like {|x| ≤ 10}?
  It ensures L(M') is non-empty in both cases, but finite or infinite depending on M(w). The "10" is arbitrary — any explicit finite set works.
• Q2. Could we use any finite set?
  Yes — {ε}, {0, 1}, anything explicitly enumerable. The point is the set's finiteness is decidable independently of M.
• Q3. Apply Rice directly.
  "L(M) is finite" depends only on L(M) (semantic — it doesn't care about M's syntax) and is nontrivial (some TMs have finite languages, some don't). Rice's theorem says any semantic, nontrivial property is undecidable. So FINITE_TM is undecidable, no construction needed beyond Rice itself.
• Q4. What's the analog for REGULAR_TM?
  REGULAR_TM = {⟨M⟩ : L(M) is regular} is also undecidable by Rice's theorem (regularity is semantic and nontrivial). Construction is similar — make L(M') a specific non-regular language iff M accepts w.

Sipser: §5.2 (Rice's theorem). Lecture notes: Module 3 slide 6. Companion problems: P14 (Rice's theorem).