3
$\begingroup$

Has there been any progress on the Busy beaver problem in the last few years? It seems like there hasn't been much work done on the problem since 2010. Is there anything amateurs can do to solve the problem?

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ It is quite unclear what you mean by the busy beaver problem. It is known to be an incomputable function, so it is not really possible to get anything useful from it. $\endgroup$
    – Per Alexandersson
    Commented Jul 27, 2015 at 19:58
  • 4
    $\begingroup$ Maybe the OP is asking about computing small values of the Busy Beaver function? $\endgroup$
    – Noah Schweber
    Commented Jul 27, 2015 at 20:17
  • 1
    $\begingroup$ Or at least lower bounds on it (the last known value is already so large that we probably won't ever see more than one or two further values). $\endgroup$
    – Noam D. Elkies
    Commented Jul 27, 2015 at 20:31
  • 1
    $\begingroup$ Mota et al., Sophistication as randomness deficiency, Lecture Notes in Comput. Sci., 8031 (2013) 172-181, "derive an alternative formulation for busy beaver computational depth.'' Bienvenu and Shen, Random semicomputable reals revisited, Lecture Notes in Comput. Sci., 7160 (2012) 31-45, make "several simple observations relating lower semicomputable random reals and busy beaver functions.'' $\endgroup$
    – Gerry Myerson
    Commented Jul 27, 2015 at 23:25
  • 1
    $\begingroup$ The question as it stands implicitly asks for references on a topic in computability theory which could be started in an undergraduate class, but not finished there. It also asks (in an interesting way) for that part of the state of the art where contributions can be made. If amateurs found a way to, say, classify state machines so that some classes are recognizably non halting, that would help in mathematical logic and elsewhere. I am struggling to understand why this question is "off-topic". Gerhard "Please Explain Or Please Reopen" Paseman, 2015.07.28 $\endgroup$
    – Gerhard Paseman
    Commented Jul 28, 2015 at 20:59

2 Answers 2

Reset to default
4
$\begingroup$

Short answer to "is there anything amateurs can do to solve the problem?": Probably no.

Long answer: The amateurs can become professionals and understand why the problem is challenging, and what it might take to solve it. That is the briefest and most definite positive answer I can imagine at present.

One can try to organize the list of all possible programs of certain lengths to try to narrow the search space, and then use some notion of "acceleration" to predict or simulate when a certain program will stop, and how many 1's it will produce. Right now the search space is infeasibly large for small values of n. (My memory suggests n=6, but I need to review the literature.) Also, the value BB(n) is likely to be large enough to require arrow notation to express a good lower bound. Amateurs might be able to eliminate significant portions of the search space by simulating "slower" machines, but what would be really useful is a proof along the lines of "If a program listing contains any of these fragments as an active subtemplate, it will lose the Busy Beaver contest." With a large enough library of such fragments, you will know what to avoid simulating.

Another possibility is that amateurs could break off certain pieces, and establish results of the form BB(m,n) > k, meaning for all program of m states and n lines, there is at least one program which prints more than k ones and then stops. Even pushing n higher and figuring out why would be a useful contribution towards (but not completing) a solution.

Gerhard "Wants A Lazy Beaver Problem" Paseman, 2015.07.27

Improve this answer
$\endgroup$
6
$\begingroup$

Pascal Michel maintains a useful Historical survey of Busy Beavers web page, including a table of results from Radó in 1963 to 2010, whose tail end is:

         TableTail
A $(k,n)$-TM is a Busy Beaver (BB) with $k$ states and $n$ symbols. In the table, $s$ is the time taken by the BB, and $\sigma$ the number of non-blank symbols left on the tape. The records (as of 2012) are in bold. The best $6$-state, $2$-symbol BB takes $10^{36534}$ steps to stop.

The Ligockis also maintain a nice web page on their results.

Finally, see

Michel, Pascal. "Problems in number theory from busy beaver competition." arXiv:1311.1029 (2013).

He suggests that the best BB TMs achieve their results by "simulating Collatz-like functions, that are generalizations of the famous $3x+1$ function."

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .