Editing Busy beaver (section)

==== Green machines ====
In 1964 Milton Green developed a lower bound for the 1s-counting variant of the Busy Beaver function that was published in the proceedings of the 1964 IEEE symposium on switching circuit theory and logical design. Heiner Marxen and Jürgen Buntrock described it as "a non-trivial (not primitive recursive) lower bound".<ref>{{Cite journal |last=Brady |first=Allen H. |date=March 1998 |title=Heiner Marxen and Jürgen Buntrock. Attacking the busy beaver 5. Bulletin of the European Association for Theoretical Computer Science, no. 40 (Feb.1990), pp. 247–251. - Pascal Michel. Busy beaver competition and Collatz-like problems. Archive for mathematical logic, vol. 32 (1993), pp. 351–367. |url=https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/heiner-marxen-and-jurgen-buntrock-attacking-the-busy-beaver-5-bulletin-of-the-european-association-for-theoretical-computer-science-no-40-feb1990-pp-247251-pascal-michel-busy-beaver-competition-and-collatzlike-problems-archive-for-mathematical-logic-vol-32-1993-pp-351367/D18FE9FA2B022BD2960AEF1E8AE28178 |journal=The Journal of Symbolic Logic |language=en |volume=63 |issue=1 |pages=331–332 |doi=10.2307/2586607 |jstor=2586607 |issn=0022-4812 |archive-date=2024-07-05 |access-date=2024-07-05 |archive-url=https://web.archive.org/web/20240705192622/https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/heiner-marxen-and-jurgen-buntrock-attacking-the-busy-beaver-5-bulletin-of-the-european-association-for-theoretical-computer-science-no-40-feb1990-pp-247251-pascal-michel-busy-beaver-competition-and-collatzlike-problems-archive-for-mathematical-logic-vol-32-1993-pp-351367/D18FE9FA2B022BD2960AEF1E8AE28178 |url-status=live }} [https://turbotm.de/~heiner/BB/mabu90.html Free HTML version by author] {{Webarchive|url=https://web.archive.org/web/20061009135243/https://drb.insel.de/~heiner/BB/mabu90.html |date=2006-10-09 }}</ref> This lower bound can be calculated but is too complex to state as a single expression in terms of ''n''.<ref name=":7">{{Cite journal |last=Green |first=Milton W. |date=1964-11-11 |title=A lower bound RADO's sigma function for binary turing machines |url=https://doi.org/10.1109/SWCT.1964.3 |journal=Proceedings of the 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design |series=SWCT '64 |location=USA |publisher=IEEE Computer Society |pages=91–94 |doi=10.1109/SWCT.1964.3}}</ref> This was done with a set of Turing machines, each of which demonstrated the lower bound for a certain ''n''.<ref name=":7" /> When ''n''=8 the method gives
: <math>\Sigma(8) \geq 3 \times (7 \times 3^{92} - 1) / 2 \approx 8.248 \times 10^{44}</math>.

In contrast, the best current (as of 2024) lower bound on <math>\Sigma(6)</math> is <math>10 \uparrow\uparrow 15</math>, where each <math>\uparrow</math> is [[Knuth's up-arrow notation]].<ref name=":5" /> This represents <math>10^{(10^{(10^{(10^{(\ldots)})})})}</math>, an exponentiated chain of 15 tens equal to <math>10^{10 \uparrow\uparrow 14}</math>. The value of <math>\Sigma(8)</math> is probably much larger still than that.

Specifically, the lower bound was shown with a series of recursive Turing machines, each of which was made of a smaller one with two additional states that repeatedly applied the smaller machine to the input tape.<ref name=":7" /> Defining the value of the N-state busy-beaver competitor on a tape containing <math>m</math> ones to be <math>B_N(m)</math> (the ultimate output of each machine being its value on <math>m = 0</math>, because a blank tape has 0 ones), the recursion relations are as follows:<ref name=":7" /> a
: <math>B_N(0) = 1</math>
: <math>B_1(m) = m + 1</math>
: <math>B_N(m) = 1 + B_{N-2}(1 + B_N(m - 1))</math>
This leads to two formulas, for odd and even numbers, for calculating the lower bound given by the Nth machine, <math>G(N)</math>:
: <math>G(N) = B_{N-2}(B_{N-2}(1))</math> for odd N
: <math>G(N) = 1 + B_{N-3}(1 + B_{N-3}(1))</math> for even N
The lower bound BB(N) can also be related to the [[Ackermann function]]. It can be shown that:<ref name=":8">{{cite journal
 | last1 = Ben-Amram | first1 = A. M.
 | last2 = Petersen | first2 = H.
 | doi = 10.1007/s00224-001-1052-0
 | issue = 1
 | journal = Theory of Computing Systems
 | mr = 1879169
 | pages = 1–11
 | title = Improved bounds for functions related to busy beavers
 | volume = 35
 | year = 2002}}</ref>
: <math>A(n,n) > G(4N+3) > A(4, 2N+1)</math>