Introduction

Hey folks! Ready for another head-scratcher? Today we’re looking at the Equivalence Problem for Turing machines. The question is: given two machines $M_1$ and $M_2$, do they recognize exactly the same language? Simple to ask, impossible to decide in general.

Formal Setup

For Turing machines $M_1$ and $M_2$, define the language:

$$ \mathrm{EQ} = {\langle M_1, M_2 \rangle \mid L(M_1) = L(M_2)}. $$

A decider for EQ would be a Turing machine

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

such that for every pair $\langle M_1, M_2 \rangle$:

  • If $L(M_1) = L(M_2)$, then $E(\langle M_1, M_2\rangle) = 1$.
  • Otherwise, $E(\langle M_1, M_2\rangle) = 0$.

Spoiler: no such decider exists!

Example Machines

Let’s look at two easy cases:

# Machine Eq1: accepts all strings of even length
def Eq1(w):
    return len(w) % 2 == 0

# Machine Eq2: simulates Eq1 by counting pairs of symbols
def Eq2(w):
    i = 0
    while i + 1 < len(w):
        i += 2
    return i == len(w)
  • Question: Do Eq1 and Eq2 recognize the same language? Answer: Yes, they both accept exactly the even-length strings.
# Machine Eq3: accepts strings with an even number of 'a's
def Eq3(w):
    return w.count('a') % 2 == 0
  • Question: Are Eq1 and Eq3 equivalent? Answer: No, Eq1 cares about total length, Eq3 cares about number of ‘a’s.

These examples are checkable by hand, but can we automate this for all machines? Let’s see why it’s impossible.

Proof Sketch (Reduction from Emptiness)

We’ll reduce the Emptiness Problem (which is undecidable) to EQ.

  1. Assume we have a decider $E$ for EQ.

  2. Given a machine $M$ for the Emptiness Problem, construct two machines:

    • $M_1$: on input $w$, reject immediately (recognizes the empty language).

    • $M_2$: on input $w$:

      1. Simulate $M$ on the fixed input $\varepsilon$.
      2. If $M(\varepsilon)$ accepts, then accept $w$.
      3. Else, reject $w$.

    Notice:

    • If $L(M) = \emptyset$, then $M(\varepsilon)$ never accepts, so $M_2$ recognizes the empty language, same as $M_1$.
    • If $L(M) \neq \emptyset$, then $M_2$ recognizes all strings (since it accepts any $w$ once $M$ accepts $\varepsilon$), whereas $M_1$ recognizes none.

  3. Run $E(\langle M_1, M_2\rangle)$:

    • If it says “equivalent,” we deduce $L(M) = \emptyset$.
    • If it says “not equivalent,” we deduce $L(M) \neq \emptyset$.

This decides Emptiness, contradiction. So no decider for EQ.

Why It Matters

  • Software Verification: You can’t build a general tool to check if two programs always behave the same.
  • Subtle Differences: Two machines may look similar but differ on some edge-case input, and no algorithm can catch all those.

Wrap-Up

The Equivalence Problem is another chapter in the saga of undecidability, confirming that even asking if two programs do the same thing is beyond algorithmic reach. Next up: the Emptiness Problem for Context-Free Grammars (spoiler: it’s decidable!).