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?



Recent progress on the busy beaver problem?
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


