Milton Green's lower bounds of the busy beaver function

Question

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

$$\Sigma(2k)>3\uparrow^{k-2}3$$

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$ ?

Answer 1

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.

Answer 2

• 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).