We denote the busy beaver function by BB.
BB(n) is the max time a Turing machine of size n takes to halt on the empty string.
(A particular model of TM and a notion of size has become standardized.)
BB(n) grows faster than any computable function. That is obviously interesting. What is less obvious (and some of my co-bloggers disagree) the pursuit of actual values of BB is interesting. For an excellent overview of the BB numbers, written in 2020 (that is relevant) by Scott Aaronson, see here. (Computable and Aaronson are flagged by my spell check but I think they are spelled correctly.)
When Scott's article appeared, BB(5) was not known. In June 2024 the value of BB(5) was discovered. See Scott's blog on this, here. The value of BB(5) isn't even that big- its just 47,176,870. That's one of those numbers that is SMALL now but would have been LARGE in (say) 1964 (see my blog about a different number of that type here).
What about BB(6)?
No, I am not going to announce that Scott announced it is now known.
I am going to announced that Scott announced better lower bounds for BB(6) are now known.
I won't restate the lower bounds since (a) Scott already has (see here) and (b) typesetting the bounds is hard (for me).
SO, what to make of all this?
1) At the time of Scott's article it looked like BB(6) was large. How large was hard to say. Intuitions about how large BB(6) would be are hard to come by, so the new result is neither surprising nor unsurprising.
2) We will never know BB(6). Shucky Darns!
3) Many of the results on BB are not published in refereed journals. However, the ones mentioned in the context of BB(5) and BB(6) were verified in Coq. I doubt other parts of math could take this approach; however, it is interesting that results can be verified via computer in this field. Indeed- I doubt a referee could verify the results without a computer aid.
4) Why the interest in BB? Some speculation:
a) Computing power is such that one can actually get out some results (read Scott's blog on BB(5) for more on that).
b) The internet: there are not that many people working on BB but those that are can easily communicate with each other.
c) Scott's article and his blog posts on it helped generate interest. Since I asked Scott to write the article for my open problems column, I get some credit here also (very little).
d) Results generate interest, and interest generates results.
e) Items a,b,c,d,e all help to reinforce each other.
Suppose we know there is an n state universal Turing machine with alphabet size 2. Does this tell us anything about BB(n)?
ReplyDeleteI assume you mean: "Let S be an n-state universal TM with alphabet size 2. Could S be a machine that runs for BB(n) steps?" I make this adjustment because we certainly know a UTM exists with alphabet size 2: you composed your comment on one.
ReplyDeleteA universal TM is a turing machine that simulates other TM's. While a UTM could potentially be a BB, the fact that it is a UTM is irrelevant to the BB game because the BB game requires the TM to begin with a blank input tape, while the portion of a UTM's behavior that makes it a UTM depends on its input tape beginning with a well-formed code that represents a TM and its input. So, knowing a TM is a UTM for some encoding does not tell you anything about its behavior in the BB game, unless it has a specific quirky interpretation for a blank tape.
I guess you could say it's unlikely for a UTM to be a BB(n) generator for any n, if only because a handful of those states are needed to operate in a particular manner in order to perform the functions of a UTM so it would be rather coincidental if it also was a BB(n) generator.
(I'm not sure how many states are needed for the universality behavior. It's been proven that UTM's exist for two-symbol machines with n states, as well as for two-state machines with m symbols, but the bounds on these are not known afaik. Wolfram came up with a two-state machine using an alphabet of three symbols which he claims to be universal, but I think the claim has been disputed (it may require meta-manipulation of the TM iirc) and the TM model he used is nonstandard. Either way, if an n-state TM could be both a UTM and a BB(n) generator, the number of states would likely be much larger than five, so it's probably fundamentally impossible to know.)
If you didn't mean to ask about a universal TM (if you just meant a TM in general), then I don't understand what you're asking. The BB game is defined in Rado's paper as a comparison of the behavior of any definable n-state two-symbol-alphabet TM on a single two-way unbounded tape, where one of the symbols in the alphabet does double-duty as the blank tape symbol (which is reasonable here since the game is only defined based on the behavior of the TM when the input is guaranteed to be a blank tape). That's just part of the definition of what the function BB(n) means.