Introduction

Hey everyone! Here’s another classic puzzle: the Emptiness Problem for Turing machines. Imagine you hand me any program (Turing machine), and I ask: “Does this machine accept no strings at all?” In other words, is its language empty? Feels like something we should be able to check, right? But surprise: it’s undecidable.

Formal Setup

Recall that a Turing machine $M$ recognizes a language:

$$ L(M) = {w \in \Sigma^* \mid M \text{ accepts } w}. $$

The Emptiness Problem asks for the language:

$$ \mathrm{EMPTY} = {\langle M \rangle \mid L(M) = \emptyset}. $$

A decider for EMPTY would be a machine

$$ E: \Sigma^* \to {0,1} $$

such that for every encoding $\langle M \rangle$:

  • If $L(M) = \emptyset$, then $E(\langle M \rangle) = 1$.
  • If $L(M) \neq \emptyset$, then $E(\langle M \rangle) = 0$.

Turing proved no such decider $E$ exists.

Example Machines

Let’s look at two simple “machines” in Python-ish pseudocode:

# Machine E1: accepts only the empty string
# So L(E1) = {""}, not empty
def E1(w):
    if w == "":
        return True
    else:
        return False

# Machine E2: loops on everything, never accepts
# So L(E2) = ∅
def E2(w):
    while True:
        pass

  • Question: Is $L(E1)$ empty? Answer: No. E1 accepts the empty string.

  • Question: Is $L(E2)$ empty? Answer: Yes. E2 never accepts anything.

But could we write one machine E that decides emptiness for all $M$? Spoiler: nope.

Proof Sketch (Reduction from ATM)

  1. Assume we have a decider E for EMPTY.

  2. We’ll use E to decide the Acceptance Problem ATM, which we know is undecidable.

    • Given $\langle M, w\rangle$ for ATM, build a new machine M' that on input x:

      1. Simulates M on w.
      2. If M accepts w, then accept x immediately.
      3. Otherwise (if M rejects or loops), loop forever.

    • Notice: L(M') is empty iff $M$ does not accept $w$ (i.e., $\langle M,w\rangle \notin ATM$).

  3. Feed $\langle M’\rangle$ to our magical E:

    • If E says “empty,” we know M doesn’t accept w.
    • If E says “not empty,” we know M does accept w.

This solves ATM, contradiction. Thus no decider for EMPTY.

Why It Matters

  • Checker Limits: You can’t build a tool that says for sure whether a program accepts at least one string.
  • Data Privacy Analogy: Think of a data validator that’s supposed to check if a dataset has any valid entries, undecidable in the general case!
  • Rice’s Theorem: Emptiness is a nontrivial property of the language recognized by $M$, so by Rice’s theorem it’s undecidable.

Wrap-Up

The Emptiness Problem drives home that even seemingly simple questions about a program’s behavior can be impossible to automate in full generality. Up next: the Finiteness Problem, can a machine’s language be finite? Stay tuned!