Wikipedia states that Milton Green demonstrated in 1964, that the busy beaver function $\Sigma(n)$ has the lower bound


I read the talk about the busy beaver article and someone had doubts about these bounds. I am not quite sure, if the bounds turned out to be true at last.

So my quesion : Are the bounds correct, and if yes, is there a simpley way to understand the bounds ?

A further question : Are there any higher lower bounds known for the busy beaver function $\Sigma(n)$ for $n\ge10$ ?


You can find some larger lower bounds on the Googology wiki, here.

Some notable lower bounds:

I found a lower bound $\Sigma(25) > F_{\omega+1}(6143) > $ Graham's number. The details are here. Wythagoras then improved the machine to prove the lower bound $\Sigma(23) > F_{\omega+1} ( F_{\omega+1}(9)) >$ Graham's number; details are in the comments of the previous page.

LittlePeng9 implemented a number of algorithms for fast-growing functions to provide very large lower bounds, and these Turing machines were optimized by Wythagoras as well. The machines are listed here. These include:

  • An implementation of the Kirby-Paris Hydra to prove $\Sigma(41,3) > F_{\varepsilon_0}(374676379)$.

  • An implementation of the Buchholz Hydra with two labels to prove $\Sigma(81,10) > F_{\vartheta(\varepsilon_{\Omega+1})}(2050)$. Here $\Sigma(m,n)$ indicates the largest number of ones printable by a Turing machine with m states and n symbols.

  • An implementation of the Buchholz Hydra with finite labels to prove $\Sigma(134,7) > F_{\psi_{\Omega_1}(\Omega_{\omega})}(2050)$. We can convert this to a two symbol machine with a conversion algorithm (devised by LittlePeng9) that proves $\Sigma (3350) > F_{\psi_{\Omega_1}(\Omega_{\omega})}(2050)$.

  • An implementation of the Buchholz Hydra with $\omega+1$ labels to prove $\Sigma(150, 7) > F_{\psi_{\Omega_1}(\varepsilon_{\Omega_{\omega}+1})}(683)$. The same reduction algorithm proves $\Sigma(3750) > F_{\psi_{\Omega_1}(\varepsilon_{\Omega_{\omega}+1})}(683)$.

It's likely that you are unfamiliar with the notations for these lower bounds. To understand them, you need to be familiar with the fast-growing hierarchy and notations for large ordinals. Suffice to say, these numbers are VERY large, making Graham's number seem like an infinitesimal!

Note that these machines are rather complex, and are rather hard to debug since they cannot be run to completion. So there is a definite possibility for errors.

Finally, Wythagoras modified the Busy Beaver machine for six states to create a seven state machine that prints more than $10^{10^{10^{10^{18705352}}}}$ ones. The machine is listed here, and the computation is verified here.

  • 1
    $\begingroup$ Wonderful results! I was unaware of those. $\endgroup$ – r.e.s. Apr 2 '14 at 14:35
  • $\begingroup$ Wow! Thank you very much! So, bb(7) is already out of reach. Great answer! $\endgroup$ – Peter Apr 2 '14 at 18:32
  • $\begingroup$ The site claims that for 18 of the HNR-machines (Hardly-Non-Regular-machines) it is not known whether they halt or not. But the site only gives a description what the machines do, but not the concrete structure. Where can I find the tables for those machines with 5 states? $\endgroup$ – Peter Apr 2 '14 at 22:24
  • $\begingroup$ And I would also like to have a complete survey for the machines with less than 5 states (I know that all those machines are solved, but did not find a list) $\endgroup$ – Peter Apr 2 '14 at 22:28
  • $\begingroup$ Skelet's 43 HNR machines can be found at googology.wikia.com/wiki/User:Ikosarakt1/…, and Skelet's original site is at skelet.ludost.net/bb/nreg.html. For machines with less than 5 states, I guess the best resource will be Brady's paper where he finds the value of Sigma(4), available at jstor.org/stable/2007539. $\endgroup$ – Deedlit Apr 5 '14 at 5:42
  • I posted that "doubting" question, but (as detailed on the talk page) these lower bounds do indeed follow from Green's paper: $$\Sigma(2k) > 3 \uparrow^{k-2} 3 \quad (k \ge 2)$$ Note that the bounds published by Green are stated in terms of recurrence relations, and are somewhat larger than what's given by the simpler Knuth arrow formula.

  • Is there a simple way to understand them? It becomes rather philosophical. If by "understand them" we mean "comprehend their magnitude", then the answer (at least for $k \ge 6$) is "probably not". Harvey Friedman proposed $2\uparrow^{4}5$ as a benchmark, such that the magnitude of any number at least this large is considered incomprehensible. He writes that "a profound level of incomprehensibility emerges. The definitions are not incomprehensible, but the largeness is incomprehensible." (For me, this is already true of $3 \uparrow^{3} 3$. I simply cannot comprehend the magnitude of the number denoted by an exponential tower of trillions of $3$s.)

  • Are any higher lower bounds known for $\Sigma(n)$ for $n\ge10$? Yes; e.g., here is a $64$-state BB-class Turing machine designed to compute a number that's far larger than Graham's number ($G$). As shown in the article, it halts eventually, leaving exactly $h_{\omega+1}(h_{\omega+1}(4)) + 1 $ contiguous ones on the tape, where $h_\omega$ is defined by an accelerated version of the fast-growing hierarchy: $$h_\alpha(n) = \begin{cases} & n+1, & \mbox{if }\alpha = 0 \\ & (h_{\alpha-1})^{n+2}(n+4), & \mbox{if }\alpha\mbox{ is a successor ordinal} \\ & (h_{\alpha[n+1]})^{n+5}(n+7), & \mbox{if }\alpha\mbox{ is a limit ordinal} \end{cases}$$ Hence, $$ \Sigma(64) \ \ge \ h_{\omega+1}(h_{\omega+1}(4)) + 1 \ \ggg \ f_{\omega+1}(f_{\omega+1}(4)) + 1 \ \ggg \ G $$ Of course this Turing machine has a "structured design logic" not required by a Busy Beaver, and so is surely nowhere close to having the minimum number of states needed to achieve similar results. (For all we know, even $12$ states with humanly impenetrable logic might be sufficient).

  • $\begingroup$ A very interesting answer! With understanding I did not mean understanding the magnitude, but understanding that there are machines that produces at least so many ones and halt. Quite impressing that bb(64) has been proven to be such an enourmous number! $\endgroup$ – Peter Apr 1 '14 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.