Category Archives: YA(T) Open Problems

Yet Another Tiny Problem series

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

Posted on by
Reply

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 →

YATOP #1: Are busy beavers lonely creatures?

Posted on by
6

This is the first of a new series of posts that I tagged with “Yet Another (Tiny) Open Problem”. In these posts I’ll describe some well known or original problems in Theoretical Computer Science that are still unsolved (up to my knowledge). Many of them are not so relevant, so I also added a “Tiny” in the acronym. If you discover that they have been solved or partially solved or, even better, YOU SOLVED them, let me know; I’ll try to keep their open/close status up-to-date.

We begin with a weird problem that involves those cute animals known as Busy Beavers : in computational theory a busy beaver is a Turing machine that attains the maximum number of steps performed before halting or the number of nonblank symbols finally on the tape, among all Turing machines of the same size. The Turing machine must follow some rigid design specifications: it operates on a single two-way unbounded tape initially filled with $0$s and the tape alphabet is $\{0,1\}$ (0 is the blank symbol); it has $n$ states plus a halting state, and every transition is a 5-tuple: (current non-halting state, current symbol, symbol to write, direction of shift, next state). Continue reading →