Introduction

What’s up, readers? Let’s tackle the Finiteness Problem for Turing machines. We ask: given any machine $M$, does it accept only a finite set of strings, or infinitely many? You might think “I can just test a bunch of inputs,” but in general, there’s no catch-all procedure. Yep, this one’s undecidable, too.

Formal Setup

Recall a Turing machine $M$ recognizes a language

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

Define the Finiteness language:

$$ \mathrm{FINITE} = {\langle M \rangle \mid |L(M)| < \infty}. $$

A decider for FINITE would be a machine

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

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

  • If $L(M)$ is finite, then $F(\langle M \rangle) = 1$.
  • If $L(M)$ is infinite, then $F(\langle M \rangle) = 0$.

Turing proved no such decider $F$ can exist.

Example Machines

Here are two toy examples:

# Machine F1: accepts exactly "hello" and "world"
def F1(w):
    if w in ["hello", "world"]:
        return True
    return False

# Machine F2: accepts any string that starts with 'a'
def F2(w):
    if w.startswith('a'):
        return True
    return False

  • Question: Is $L(F1)$ finite? Answer: Yes, only two strings.

  • Question: Is $L(F2)$ finite? Answer: No, there are infinitely many strings beginning with ‘a’.

But could there be a universal decider $F$ that handles all $M$? Not a chance.

Proof Sketch (Reduction from Emptiness)

We’ll show that if you could decide FINITE, you could also decide the Emptiness Problem, which we already know is impossible.

  1. Assume a decider $F$ for FINITE exists.

  2. Given any machine encoding $\langle M \rangle$ for the Emptiness Problem, build a new machine $M’$ that on input $y$:

    1. Simulates $M$ on the fixed input $\varepsilon$ (the empty string).
    2. If $M(\varepsilon)$ accepts, then accept $y$ immediately.
    3. Otherwise, loop forever.

    Now observe:

    • If $L(M) = \emptyset$, then $M(\varepsilon)$ never accepts, so $M’$ never accepts any $y$; hence $|L(M’)| = 0$, which is finite.
    • If $L(M) \neq \emptyset$, then $M(\varepsilon)$ halts and accepts, so $M’$ accepts every $y$; hence $|L(M’)|$ is infinite.

  3. Feed $\langle M’ \rangle$ into our mythical decider $F$:

    • If $F$ says “finite,” we deduce $L(M)$ was empty.
    • If $F$ says “infinite,” we deduce $L(M)$ was nonempty.

This would solve Emptiness, a known undecidable problem. Contradiction! So no decider for FINITE.

Why It Matters

  • Testing Limits: You can’t build a tool to certify whether a program’s accepted language has a size bound.
  • Language Theory: Helps draw clear lines between regular/CFG cases (where finiteness is decidable) and full Turing machines.

Wrap-Up

The Finiteness Problem reminds us that even asking “finite or infinite?” about a machine’s language is too much to handle generally. Stick around for the next post: The Equivalence Problem for Turing machines, yet another undecidable beast!