Introduction

Alright, let’s dive into our next classic: the Acceptance Problem for Turing machines. Imagine you hand me any program (Turing machine) and an input string, and I tell you, “Yep, this program will eventually accept that string,” or “Nope, it never will.” Nice, right? Well, spoiler: no program can always get that right.

Formal Setup

We encode machines and inputs as strings over some alphabet Σ, and consider the language:

$$ \text{ATM} = {\langle M, w \rangle \mid M \text{ accepts } w} $$

A decider for ATM would be a Turing machine

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

such that:

  • If $M$ eventually enters an accept state on input $w$, then $A(\langle M,w\rangle)=1$.
  • Otherwise (if $M$ rejects or loops), then $A(\langle M,w\rangle)=0$.

Turing showed no such decider $A$ can exist.

Example Machines

Consider two toy machines in Python-ish pseudocode:

# Machine A1: accepts if input has an 'x', loops otherwise
def A1(w):
    for c in w:
        if c == 'x':
            return True  # accept
    while True:
        pass            # loop forever

# Machine A2: rejects (never accepts)
def A2(w):
    while True:
        pass            # loops forever, so never accepts

  • Question: Does A1 accept on input "xyz"? Answer: Yes, 'x' is in the string, so the loop breaks and it accepts.

  • Question: Does A2 accept on input "anything"? Answer: No, it loops unconditionally and never reaches an accept state.

Easy for these examples, but we want a single machine A that works for all machines $M$ and inputs $w$.

Proof Sketch (Reduction from HALT)

  1. Assume we have a decider $A$ for ATM.

  2. We’ll show we could then decide the Halting Problem (which we know is impossible):

    • Given input $\langle M,w\rangle$, build a new machine $M’$ that on any input $u$:

      1. Simulate $M$ on $w$.
      2. If $M(w)$ halts, then accept.
      3. Otherwise (if $M$ loops), loop forever.

    • Notice: $M’$ accepts every input iff $M(w)$ halts (and loops on everything otherwise).

  3. Feed $\langle M’, u\rangle$ (for any fixed $u$, say $\varepsilon$) into our magical decider $A$.

    • If $A$ says “accepts”, we know $M(w)$ halts.
    • If $A$ says “doesn’t accept”, we know $M(w)$ loops.

This would solve Halting, a contradiction. Hence, no decider for ATM.

Why This Matters

  • Language Recognition Limits: We can’t build a universal “will this program accept?” checker.
  • Foundation for NP-Completeness: Decidable vs. undecidable sets form the backdrop for understanding which problems are in NP or beyond.
  • Rice’s Theorem Again: Acceptance is a nontrivial property of the language accepted by $M$, so by Rice’s theorem it’s undecidable.

Wrap-Up

So, the Acceptance Problem is another nail in the coffin of “perfect automation” for program behavior. No machine can tell you for sure whether every other machine will accept its input. Next up: the Emptiness Problem for Turing machines, catch you there!