YATOP #1: Are busy beavers lonely creatures?

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

6 thoughts on “YATOP #1: Are busy beavers lonely creatures?

  1. Actually, it’s trivial to see that BB(n) is not computable – indeed, if it was computable, or even recursively enumerable, then we could find, in finite time, some member M of BB(n). This way, by simulating M until it halts (we know that M is in BB(n), so it must halt) and counting number of steps, we will have computed the value of S(n) (because M is in BB(n), so this is how long it’s working for).
    The thing I don’t understand is: why does it follow that for some n the set BB(n) must have more than 1 element? It’s completely unclear to me why “If the answer [to YA(T)OP #1] is yes, then BB(n) is trivially computable”.

    • @Wojowu: sorry, your observations are right, but probably I made a typo in the copy-paste process and the cardinality symbols got lost: I mean the computability of $\# BB(n) = |BB(n)|$. I fixed the post. Note that the problem is not so “tiny” … if you have some ideas on it let me know 🙂

  2. Hi, there! This is cool. I’ve recently been pretty interested in enumerating tape configurations for time bounded TM’s.

    Anyways, I had a small potential typo. It says, “(and it writes $\Sigma > 3.5 × 10^{18267}1$s on the tape).” It appears that the tex didn’t render or maybe you meant for it to be like that (or maybe my browser is flawed).

    Have a nice day!

    -Mike

Leave a Reply

Your email address will not be published. Required fields are marked *