It is well known that $\text{Primes}= \{ a^p \mid p \text{ is prime}\}$ is not regular. The standard proof uses the pumping lemma for regular languages, but you can also use Parikh’s theorem or Myhill-Nerode theorem: see this question on cs.stackexchange.com. I tried to figure out another way to prove it, and came out with an alternate proof that uses a bit of number theory and Busy Beavers.

First of all: Theorem 1 (Prime gap theorem). There are gaps between primes that are arbitrarily large.

Another easy property of DFAs is:

Property 2. Given a DFA $A = { Q, \Sigma, \delta, q_0, F }$, if $w = uv$ and the state of $A$ on input $w$, after scanning $u$ is $q_i$ (when the head is at the beginning of subword $v$); and $A’ = { Q, \Sigma, \delta, q_i, F }$ then $w \in L(A)$ if and only if $v \in L(A’)$.

We can combine them in a (funny) proof that “uses” Busy Beavers:

Theorem 3. $\text{Primes}= \{ a^p \mid p \text{ is prime}\}$

Proof:

• suppose that you have a $DFA$ $A$ that accepts the primes $\{ a^p\mid p \text{ prime} \}$
• given a state $q$ of $A$, you can build a Turing machine $M_{\langle A,q \rangle}$ that sequentially simulates $A$ starting from state $q$ on inputs $a^1, a^2, a^3, a^4,…$ until $A$ accepts some $a^k$ (or never halt)
• let $|M_{\langle q,A \rangle}| = n$ be the size of such Turing machine, and $BB(n)$ the maximum number of steps achievable by a halting Turing machine of size $n$ (uncomputable)
• by the prime gaps theorem, there exists a prime $p_i$ such that $p_{i+1} – p_i \gg BB(n)$
• $A$ accepts $a^{p_{i+1}}$, so let $q_i$ be the state of $A$ on input $a^{p_{i+1}}$ after $p_{i}$ steps (i.e. it has scanned the first part $a^{p_i}…$ and the head is at the beginning of the remaining part of the input $…a^{p_{i+1} – p_{i}}$)
• so there exists $M_{\langle A,q_i\rangle}$ of size $n$ that by construction will run for a number of steps greater than $p_{i+1} – p_i \gg BB(n)$ and halt (Property 2), contradicting the hypothesis that $BB(n)$ is the maximum number of steps achievable by a halting TM of size $n$

$\square$

With the same technique, we could also use a Kolmogorov Complexity argument instead of Busy Beavers: pick a large enough incompressible binary string $x$ and let $p’- p$ be a large enough prime gap such that $p’ – p > x$. If there was a DFA $A$ that recognizes $\text{Primes}$, we could reconstruct $x$ using only the description of $A$ and its state after scanning the first part $a^{p’-x}$ of $a^{p’}$, i.e. $K(x) = |A| + c \ll |x|$.

Open problem: are there other funny proofs that the set $\text{Primes}$ is not regular, out there?