A funny way to prove that the set of primes is not regular

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.

Continue reading