Editing Busy beaver (section)

=== Open mathematical problems ===
In addition to posing a rather challenging [[mathematical game]], the busy beaver functions Σ(n) and ''S''(''n'') offer an entirely new approach to solving pure mathematics problems. Many [[open problem in mathematics|open problems in mathematics]] could in theory, but not in practice, be solved in a systematic way given the value of ''S''(''n'') for a sufficiently large ''n''.<ref name=":1" /><ref name=":9">{{cite book |last=Chaitin |first=Gregory J. |author-link=Gregory Chaitin |title=Open Problems in Communication and Computation |publisher=Springer |year=1987 |isbn=978-0-387-96621-2 |editor1-last=Cover |editor1-first=T. M. |pages=108–112 |chapter=Computing the Busy Beaver Function |access-date=2022-07-07 |editor2-last=Gopinath |editor2-first=B. |chapter-url=https://cs.auckland.ac.nz/~chaitin/bellcom.pdf |archive-url=https://web.archive.org/web/20171230195953/https://www.cs.auckland.ac.nz/~chaitin/bellcom.pdf |archive-date=2017-12-30 |url-status=dead}}</ref> Theoretically speaking, the value of S(n) encodes the answer to all mathematical conjectures that can be checked in infinite time by a Turing machine with less than or equal to ''n'' states.<ref name=":62" />

Consider any <math>\Pi_1^0</math> [[conjecture]]: any conjecture that could be [[mathematical proof|disproven]] via a [[counterexample]] among a [[countable]] number of cases (e.g. [[Goldbach's conjecture]]). Write a computer program that sequentially tests this conjecture for increasing values. In the case of Goldbach's conjecture, we would consider every even number ≥ 4 sequentially and test whether or not it is the sum of two prime numbers. Suppose this program is simulated on an ''n''-state Turing machine. If it finds a counterexample (an even number ≥ 4 that is not the sum of two primes in our example), it halts and indicates that. However, if the conjecture is true, then our program will never halt. (This program halts ''only'' if it finds a counterexample.)<ref name=":62" />

Now, this program is simulated by an ''n''-state Turing machine, so if we know ''S''(''n'') we can decide (in a finite amount of time) whether or not it will ever halt by simply running the machine that many steps.  And if, after ''S''(''n'') steps, the machine does not halt, we know that it never will and thus that there are no counterexamples to the given conjecture (i.e., no even numbers that are not the sum of two primes).  This would prove the conjecture to be true.<ref name=":62" /> Thus specific values (or upper bounds) for ''S''(''n'') could be, in theory, used to systematically solve many open problems in mathematics.<ref name=":62" />

However, current results on the busy beaver problem suggest that this will not be practical for two reasons:{{citation needed|date=July 2024}}
* It is extremely hard to prove values for the busy beaver function (and the max shift function). Every known exact value of ''S''(''n'') was proven by enumerating every ''n''-state Turing machine and proving whether or not each halts. One would have to calculate ''S''(''n'') by some less direct method for it to actually be useful.{{citation needed|date=July 2024}}
* The values of S(n) and the other busy beaver functions get very large, very quickly. While the value of S(5) is only around 47 million, the value of S(6) is more than 10⇈15, which is equal to <math>10^{(10^{(10^{(10^{(\ldots)})})})}</math> with a stack of 15 tens.<ref name=":5" /><ref>{{cite web|url=http://scientificamerican.com/article/new-math-breakthrough-reveals-the-fifth-busiest-beaver|title=Mathematicians Have Finally Found the Fifth 'Busiest Beaver'|publisher=Scientific American|last=Bischoff|first=Manon|date=2024-07-25|access-date=28 February 2025}}</ref> This number has 10⇈14 digits and is unreasonable to use in a computation. The value of S(27), which is the number of steps the current program for the [[Goldbach's conjecture|Goldbach conjecture]] would need to be run to give a conclusive answer, is incomprehensibly huge, and not remotely possible to write down, much less run a machine for, in the observable universe.<ref name=":1" />

==== Consistency of theories ====
Another property of S(n) is that no arithmetically sound, computably axiomatized [[Axiomatic system|theory]] can prove all of the function's values. Specifically, given a computable and arithmetically sound theory <math>T</math>, there is a number <math>n_T</math> such that for all <math>n \geq n_T</math>, no statement of the form <math>S(n) = k</math> can be proved in <math>T</math>.<ref name=":62" /> This implies that for each theory there is a specific largest value of S(n) that it can prove. This is true because for every such <math>T</math>, a Turing machine with <math>n_T</math> states can be designed to enumerate every possible proof in <math>T</math>.<ref name=":62" /> If the theory is inconsistent, then all false statements are provable, and the Turing machine can be given the condition to halt if and only if it finds a proof of, for example, <math>0 = 1</math>.<ref name=":62" /> Any theory that proves the value of <math>S(n_T)</math> proves its own consistency, violating [[Gödel's incompleteness theorems|Gödel's second incompleteness theorem]].<ref name=":62" /> This can be used to place various theories on a scale, for example the various [[Large cardinal axiom|large cardinal axioms]] in [[ZFC]]: if each theory <math>T</math> is assigned as its number <math>n_T</math>, theories with larger values of <math>n_T</math> prove the consistency of those below them, placing all such theories on a countably infinite scale.<ref name=":62" />

==== Notable examples ====
* A 745-state binary Turing machine has been constructed that halts [[if and only if]] [[ZFC]] is inconsistent.<ref name="AaronsonJuly2023" /><ref name=":3" />

* A 744-state Turing machine has been constructed that halts if, and only if, the [[Riemann hypothesis]] is false.<ref name="Aaronson3" /><ref name=":1" />

* A 43-state Turing machine was constructed that halts if, and only if, [[Goldbach's conjecture]] is false. This was further reduced to 25-state machine,<ref name="Aaronson3" /><ref name=":1" /> and later formally proved and verified in the [[Lean 4]] theorem proving language.<ref>{{cite web|last=Leng|first=Yijun|title=GitHub Repository "goldbach_tm27"|website=[[GitHub]] |url=https://github.com/lengyijun/goldbach_tm}}</ref>

* A 15-state Turing machine has been constructed that halts if and only if the following conjecture formulated by [[Paul Erdős]] in 1979 is false: for all ''n'' > 8 there is at least one digit 2 in the base 3 representation of 2<sup>''n''</sup>.<ref>{{cite report |title=On the hardness of knowing busy beaver values BB(15) and BB(5,4) |author=Tristan Stérin and Damien Woods |date=July 2021 |arxiv=2107.12475 |institution=Maynooth University |type=Technical Report}}</ref><ref>{{cite journal |last=Erdös |first=Paul |author-link=Paul Erdős |date=1979 |title=Some unconventional problems in number theory. |url=https://jstor.org/stable/2689842 |journal=[[Math. Mag.]] |volume=52 |issue=2 |pages=67–70 |doi=10.1080/0025570X.1979.11976756 |jstor=2689842 |archive-date=2022-06-13 |access-date=2022-07-07 |archive-url=https://web.archive.org/web/20220613231912/https://www.jstor.org/stable/2689842 |url-status=live }}</ref>