https://wiki.bbchallenge.org/w/index.php?action=history&feed=atom&title=Busy_Beaver_Frontier 2026-05-02T11:13:02Z Revision history for this page on the wiki MediaWiki 1.43.5 https://wiki.bbchallenge.org/w/index.php?title=Busy_Beaver_Frontier&diff=6197&oldid=prev 2026-02-12T05:00:39Z

<p><span class="autocomment">Conjectures</span></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 05:00, 12 February 2026</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l4">Line 4:</td> <td colspan="2" class="diff-lineno">Line 4:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* &#039;&#039;&#039;Conjecture 10&#039;&#039;&#039;: [[BB(5)]] = 47,176,870. &#039;&#039;&#039;Proven by bbchallenge in 2024&#039;&#039;&#039;.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* &#039;&#039;&#039;Conjecture 10&#039;&#039;&#039;: [[BB(5)]] = 47,176,870. &#039;&#039;&#039;Proven by bbchallenge in 2024&#039;&#039;&#039;.</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* '''Conjecture 11''': ZF cannot prove the value of BB(20). See [[<del style="font-weight: bold; text-decoration: none;">Independence from ZFC</del>]].</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* '''Conjecture 11''': ZF cannot prove the value of BB(20). See [[<ins style="font-weight: bold; text-decoration: none;">Logical independence</ins>]].</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* &#039;&#039;&#039;Conjecture 12&#039;&#039;&#039;: PA cannot prove the value of BB(10).</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* &#039;&#039;&#039;Conjecture 12&#039;&#039;&#039;: PA cannot prove the value of BB(10).</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* &#039;&#039;&#039;Conjecture 13&#039;&#039;&#039;: There exists a &lt;math&gt;n_0&lt;/math&gt; such that for all &lt;math&gt;n \ge n_0&lt;/math&gt;: &lt;math&gt;BB(n+1) &gt; 2^{BB(n)}&lt;/math&gt;.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* &#039;&#039;&#039;Conjecture 13&#039;&#039;&#039;: There exists a &lt;math&gt;n_0&lt;/math&gt; such that for all &lt;math&gt;n \ge n_0&lt;/math&gt;: &lt;math&gt;BB(n+1) &gt; 2^{BB(n)}&lt;/math&gt;.</div></td></tr> <!-- diff cache key mediawiki:diff:1.41:old-2317:rev-6197:php=table --> </table>

Sligocki https://wiki.bbchallenge.org/w/index.php?title=Busy_Beaver_Frontier&diff=2317&oldid=prev 2025-06-30T21:27:36Z

<p>Add conjectures</p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 21:27, 30 June 2025</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Line 1:</td> <td colspan="2" class="diff-lineno">Line 1:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;The Busy Beaver Frontier&#039;&#039;&#039;&lt;ref&gt;Scott Aaronson. 2020. [https://www.scottaaronson.com/papers/bb.pdf The Busy Beaver Frontier]. SIGACT News 51, 3 (August 2020), 32–54. https://doi.org/10.1145/3427361.3427369&lt;/ref&gt; was a Busy Beaver survey article published by Scott Aaronson in 2020. It describes the Busy Beaver problem, introduced a number of variants (such as the [[Lazy Beaver]] and [[Beeping Busy Beaver]]) and made a number of conjectures. This article introduced many new people to the Busy Beaver problem and was a major inspiration for the [[bbchallenge]] community.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&#039;&#039;&#039;The Busy Beaver Frontier&#039;&#039;&#039;&lt;ref&gt;Scott Aaronson. 2020. [https://www.scottaaronson.com/papers/bb.pdf The Busy Beaver Frontier]. SIGACT News 51, 3 (August 2020), 32–54. https://doi.org/10.1145/3427361.3427369&lt;/ref&gt; was a Busy Beaver survey article published by Scott Aaronson in 2020. It describes the Busy Beaver problem, introduced a number of variants (such as the [[Lazy Beaver]] and [[Beeping Busy Beaver]]) and made a number of conjectures. This article introduced many new people to the Busy Beaver problem and was a major inspiration for the [[bbchallenge]] community.</div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">== Conjectures ==</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* '''Conjecture 10''': [[BB(5)]] = 47,176,870. '''Proven by bbchallenge in 2024'''.</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* '''Conjecture 11''': ZF cannot prove the value of BB(20). See [[Independence from ZFC]].</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* '''Conjecture 12''': PA cannot prove the value of BB(10).</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* '''Conjecture 13''': There exists a &lt;math&gt;n_0&lt;/math&gt; such that for all &lt;math&gt;n \ge n_0&lt;/math&gt;: &lt;math&gt;BB(n+1) &gt; 2^{BB(n)}&lt;/math&gt;.</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* '''Conjecture 18''': &lt;math&gt;BB(n) &lt; \Sigma(n+1)&lt;/math&gt; for all &lt;math&gt;n \ge 4&lt;/math&gt;.</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* '''Conjecture 19''': &lt;math&gt;\lim_{n \to \infty} \frac{\log BB(n)}{\log \Sigma(n)} = 2&lt;/math&gt;</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* '''Conjecture 22''': The function &lt;math&gt;g&lt;/math&gt; defined in [[5-state busy beaver winner]] eventually terminates for all starting numbers.</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* '''Conjecture 23''': For all &lt;math&gt;n \ge 3&lt;/math&gt;, there is an "essentially unique" n-state Busy Beaver.</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* '''Conjecture 24''': Every Busy Beaver Turing machine, viewed as a directed graph, is strongly connected.</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* '''Conjecture 25''': &lt;math&gt;LB(n) \ge \frac{D(n)}{n^{O(1)}}&lt;/math&gt; where LB is the [[Lazy Beaver]] function, D(n) is the number of "essentially different" n-state TMs.</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== References ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== References ==</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;references/&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&lt;references/&gt;</div></td></tr> <!-- diff cache key mediawiki:diff:1.41:old-2311:rev-2317:php=table --> </table>

Sligocki https://wiki.bbchallenge.org/w/index.php?title=Busy_Beaver_Frontier&diff=2311&oldid=prev 2025-06-30T21:05:13Z

<p>Created page with &quot;&#039;&#039;&#039;The Busy Beaver Frontier&#039;&#039;&#039;&lt;ref&gt;Scott Aaronson. 2020. [https://www.scottaaronson.com/papers/bb.pdf The Busy Beaver Frontier]. SIGACT News 51, 3 (August 2020), 32–54. https://doi.org/10.1145/3427361.3427369&lt;/ref&gt; was a Busy Beaver survey article published by Scott Aaronson in 2020. It describes the Busy Beaver problem, introduced a number of variants (such as the <a href="/wiki/Lazy_Beaver" title="Lazy Beaver">Lazy Beaver</a> and <a href="/wiki/Beeping_Busy_Beaver" title="Beeping Busy Beaver">Beeping Busy Beaver</a>) and made a number of conjectures. This article introduced ma...&quot;</p> <p><b>New page</b></p><div>&#039;&#039;&#039;The Busy Beaver Frontier&#039;&#039;&#039;&lt;ref&gt;Scott Aaronson. 2020. [https://www.scottaaronson.com/papers/bb.pdf The Busy Beaver Frontier]. SIGACT News 51, 3 (August 2020), 32–54. https://doi.org/10.1145/3427361.3427369&lt;/ref&gt; was a Busy Beaver survey article published by Scott Aaronson in 2020. It describes the Busy Beaver problem, introduced a number of variants (such as the [[Lazy Beaver]] and [[Beeping Busy Beaver]]) and made a number of conjectures. This article introduced many new people to the Busy Beaver problem and was a major inspiration for the [[bbchallenge]] community.<br /> <br /> == References ==<br /> &lt;references/&gt;</div>

Sligocki