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).

The n-state busy beaver (BB-n) game (introduced by Tibor Radó in 1962, [1]) is a contest to find such an n-state Turing machine having the largest possible score, i.e. the largest number of 1s on its tape after halting. A machine that attains the largest possible score among all n-state Turing machines is called an n-state busy beaver.

The busy beaver function $\Sigma(n)$ (with $\Sigma: \mathbb{N} \to \mathbb{N}$), is the maximum attainable “score” (the maximum number of 1s finally on the tape) among all halting 2-symbol $n$-state Turing machines, when started on a blank tape. In addition to $\Sigma$, Radó also considered the maximum number of attaianable steps (or, equivalently, number of shifts, because the Turing machine makes a move at every transition) before halting and he denoted it with $S(n)$ (while we denote with $s(M)$ the number of steps made by $M$ before halting).

It is easy to prove that both functions are uncomputable: for example $S(n)$ could be used to decide the Halting problem of a Turing machine $M$ on input $x$: just build $M’$ that writes $x$ on the empty tape and simulate $M$ for $S(|M’|)$ steps; if it doesn’t halt it will run forever because $S(n)$ is the maximum number of steps that a halting Turing machine of size $n$ can perform). We have that $\Sigma$ grows faster than any computable function $f : \mathbb{N} \to \mathbb{N}$, and $S(n) \geq \Sigma(n)$.

The current record holder (a busy-beaver candidate), among the 6-states 2-symbols Turing machines, runs for more than $s(n) > 7.4 \times 10^{36534}$ steps (and it writes $ \Sigma > 3.5 \times 10^{18267} $ 1s on the tape). For more information on record holders, busy beaver history and “how to search yourself a busy beaver” you can visit Heiner Marxen’s site or Pascal Michel’s historical survey.

Now the open problem; if we consider two Turing machines different only if their underlying transition graphs are not isomorphic:

Yet Another (Tiny) Open Problem #1: What can be said about the number of busy beavers of a given size? Does the set:
$$BB(n) = \{ M \mid M \text{ has n states and is a busy beaver, i.e.  } s(M)=S(n)\}$$
always contain only one busy beaver for all $n$?

If the answer is yes, then $\#BB(n) =| BB(n) |$ is trivially computable, but what can be said if there can be two different busy beavers $M_1 \neq M_2$, both with $n$ states (but whose underlying transition graphs are not isomorphic) that run for $s(M_1)=s(M_2)=S(n)$? Can we show that $\# BB(n)$ is uncomputable?

[1] Radó, Tibor (May 1962). “On non-computable functions“. Bell System Technical Journal 41 (3): 877–884