https://wiki.bbchallenge.org/w/api.php?action=feedcontributions&feedformat=atom&user=QwerpiwBusyBeaverWiki - User contributions [en]2026-04-30T19:12:46ZUser contributionsMediaWiki 1.43.5https://wiki.bbchallenge.org/w/index.php?title=TMBR:_September_2025&diff=3676TMBR: September 20252025-09-07T20:12:46Z<p>Qwerpiw: </p>
<hr />
<div>{{TMBRnav|August 2025|October 2025}}<br />
{{stub}}<br />
<br />
[[:Category:This Month in Beaver Research|This Month in Beaver Research]] for September 2025.<br />
<br />
==Cryptids==<br />
<br />
==Holdouts==<br />
* [[BB(6)|BB(6):]] <br />
** Andrew Ducharme and @mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1413428240000745618 both found a family of 10 halting TMs] independently, all halting in around <math>10^{69}</math> steps.<br />
** @mxdys [https://discord.com/channels/960643023006490684/1400456788955893840/1413542505772748810 decided two machines’ fates] from the [[TMBR: August 2025#Misc|50 Random Holdouts released in August]], making 8/50 machined solved as of this month.<br />
* [[BB(7)|BB(7):]] Andrew Ducharme has continued reducing [https://wiki.bbchallenge.org/wiki/BB(7)#Phase_2 the number of holdouts], from 59,727,905 to 31,811,445 (46.7394% reduction)<br />
<br />
==BB Adjacent==<br />
*John Tromp announced on Discord that a 350-bit <math>BB \lambda (n)</math> function now reaches the limit of BMS, an improvement from the previous 404 bits.<br />
TODO: phrasing. Discord source: https://discord.com/channels/960643023006490684/1355653587824283678/1413637783045542038 and https://github.com/tromp/AIT/blob/master/fast_growing_and_conjectures/bms.lam<br />
<br />
[[Category:This Month in Beaver Research|2025-09]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=TMBR:_September_2025&diff=3671TMBR: September 20252025-09-07T05:57:39Z<p>Qwerpiw: </p>
<hr />
<div>{{TMBRnav|August 2025|October 2025}}<br />
{{stub}}<br />
<br />
[[:Category:This Month in Beaver Research|This Month in Beaver Research]] for September 2025.<br />
<br />
==Cryptids==<br />
<br />
==Holdouts==<br />
* [[BB(6)|BB(6):]] <br />
** Andrew Ducharme and @mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1413428240000745618 both found a family of 10 halting TMs] independently, all halting in around <math>10^{69}</math> steps.<br />
** @mxdys [https://discord.com/channels/960643023006490684/1400456788955893840/1413542505772748810 decided two machines’ fates] from the [[TMBR: August 2025#Misc|50 Random Holdouts released in August]], making 8/50 machined solved as of this month.<br />
* [[BB(7)|BB(7):]] Andrew Ducharme has continued reducing [https://wiki.bbchallenge.org/wiki/BB(7)#Phase_2 the number of holdouts], from 59,727,905 to 37,514,197 (37.1915% reduction)<br />
<br />
==BB Adjacent==<br />
*John Tromp announced on Discord that a 350-bit <math>BB \lambda (n)</math> function now reaches the limit of BMS, an improvement from the previous 404 bits.<br />
TODO: phrasing. Discord source: https://discord.com/channels/960643023006490684/1355653587824283678/1413637783045542038 and https://github.com/tromp/AIT/blob/master/fast_growing_and_conjectures/bms.lam<br />
<br />
[[Category:This Month in Beaver Research|2025-09]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=TMBR:_August_2025&diff=3601TMBR: August 20252025-09-03T04:35:59Z<p>Qwerpiw: /* Holdouts */ this happened in September</p>
<hr />
<div>[[File:Conference poster for DNA31 by Tristan Stérin.png|thumb|396x396px|Conference poster for the [https://dna31.sciencesconf.org/ 31st International Conference on DNA Computing and Molecular Programming], [https://discord.com/channels/960643023006490684/960643023530762341/1409904231468761159 made by Tristan Stérin (cosmo)]]]<br />
<br />
[[:Category:This Month in Beaver Research|This Month in Beaver Research]] for August 2025. This month, Tristan Stérin presented a poster (see right) at DNA 31, there were significant holdouts reduction in numerous domains, a fast algorithm for Antihydra (and similar Collatz-like problems) was re-discovered, and multisymbol support was added to the Blaze TM visualizer.<br />
<br />
The official [[bbchallenge]] [[BB(5)]] paper "Determination of the fifth Busy Beaver value" has reached [https://github.com/bbchallenge/bbchallenge-paper/blob/build-paper-pdf/bbchallenge-paper.pdf v0.99] and v1.0 will be posted to Arxiv in the first week or two of September.<br />
<br />
An early announcement: October will be [[BB(3,3)]] month. This is a first test of the idea of "themed focus months". The idea is to encourage broad research focus into the BB(3,3) domain to reduce or describe holdouts more deeply, spread understanding of some of the most complex TMs and analysis techniques, etc. More information will come in next month's TMBR.<br />
<br />
== Cryptids ==<br />
A fast algorithm for [[Consistent Collatz]] simulation was re-discovered and popularized. Using it:<br />
* apgoucher simulated [[Antihydra]] to <math>2^{38}</math> iterations. This is actually a result from one year ago, but was rediscovered and added to the wiki. https://discord.com/channels/960643023006490684/1026577255754903572/1271528180246773883<br />
* Shawn Ligocki simulated {{TM|1RB1RA_0RC1RC_1LD0LF_0LE1LE_1RA0LB_---0LC}} out to one additional Collatz reset, demonstrating that (if they halt, which they probviously should) they will have sigma scores <math>> 10^{10^{10^7}}</math>.<br />
This algorithm has near linear runtime (in the number of iterations simulated), but also linear memory growth since the parameters grow exponentially. This memory limit seems to be the main bottleneck to simulating Antihydra and other Consistent Collatz iterations further. There has been some discussion on more efficient memory usage or a distributed algorithm to support further scaling, but no results are available yet.<br />
<br />
== Holdouts ==<br />
In August there were significant reductions in [[Holdouts lists]] across many [[BB Domains]]<br />
{| class="wikitable"<br />
|+BB Holdout Reduction by Domain<br />
!Domain<br />
!New Holdout Count<br />
!July Holdout Count<br />
!Holdout Reduction<br />
!% Reduction<br />
|-<br />
|[[BB(6)]]<br />
|2,592<br />
|2,728<br />
|136<br />
|5.0%<br />
|-<br />
|[[BB(2,6)]]<br />
|18,054,938<br />
|22,302,296<br />
|4,247,358<br />
|19.0%<br />
|-<br />
|[[BB(7)]]<br />
|59,727,905<br />
|86,129,304<br />
|26,401,399<br />
|30.7%<br />
|}<br />
* [[BB(6)]] holdouts: Reduced by a total of 136 holdouts by 4 people.<br />
** XnoobSpeakable found 9 new halting TMs in the high exponential runtime range (~<math>10^{100000}</math>) by running Enumerate.py out to extremely high parameters. https://discord.com/channels/960643023006490684/1239205785913790465/1401470301467836556<br />
** [https://discord.com/channels/960643023006490684/1239205785913790465/1407580922831831152 Andrew Ducharme found a surprisingly short running halting TM] in the [[BB(6)]] holdouts list with runtime ~<math>10^{78}</math>, to which [https://discord.com/channels/960643023006490684/1239205785913790465/1407659104910053387 Peacemaker replied with another TM] that was almost identical, and soon, simulation showed it to halt in the same number of steps. Later on the 28th, [https://discord.com/channels/960643023006490684/1239205785913790465/1410465964528504872 Ducharme found another one] with surprisingly low runtime: ~<math>10^{11}</math>. In response, [https://discord.com/channels/960643023006490684/1239205785913790465/1410475867200815114 Peacemaker found an almost identical machine], which also halts with similar runtime.<br />
** Peacemaker shared a list of BB(6) holdouts and how many steps are required to use all defined transitions. https://discord.com/channels/960643023006490684/1239205785913790465/1410437756777398344<br />
** @mxdys shared a list of 7 holdouts that he solved using [https://github.com/ccz181078/busycoq/blob/b1e53d74e5053c3379645aaf75fa8c7a72d00547/verify/RWLAcc.v his RWLAcc decider in Rocq] (previously known as Coq). https://discord.com/channels/960643023006490684/1239205785913790465/1408304281039409212 He also shared results featuring 6 holdouts that were solved in "50 Random Holdouts", see https://discord.com/channels/960643023006490684/1400456788955893840/1409115537631613020<br />
** On August 30, @mxdys shared the [https://wiki.bbchallenge.org/wiki/Holdouts_lists#Downloadable_Holdout_Lists new holdouts list], consisting of 2,592 TMs. (The additional 110 TMs not listed here were solved by @mxdys using deciders or individual proofs.)<br />
*After the [[BB(7)#Phase 1|enumeration of BB(7)]] was completed, Andrew Ducharme ran [[BB(7)#Phase 2|several deciders]] on the holdouts list, filtering the original 86,129,304 holdouts down to 59,727,905 in 10 days. https://drive.google.com/drive/u/0/folders/17U0BRpJHTMLtB0poBlOSZhGGp4FkCHIO<br />
*[[BB(3,3)|BB(3,3):]] 9 holdouts were proven non-halting in Rocq (previously known as Coq) by mxdys. [https://wiki.bbchallenge.org/wiki/BB(3,3)#Holdouts 10 holdouts remain, 4 of them solved with moderate rigor.] https://discord.com/channels/960643023006490684/1259770474897080380/1410308974275985428<br />
*[https://discord.com/channels/960643023006490684/1259770421046411285/1411488532500971631 @mxdys proved] 2 [[BB(2,5)]] machines are non-halting in Rocq.<br />
<br />
==BB Adjacent==<br />
*John Tromp introduced the <math>BB \lambda _1(n)</math> function for [[Busy Beaver for lambda calculus#Oracle Busy Beaver|Busy Beaver for lambda calculus with an oracle]] and computed it up to <math>BB \lambda _1(22)</math>.<br />
* Instruction-Limited Greedy Busy Beaver gBBi(n) and an [[Instruction-Limited Busy Beaver#Instruction-Limited Busy Beaver Variants|Instruction-Limited variant]] of the [[Blanking Busy Beaver]] (BLBi(n)) were introduced. gBBi(n) was computed up to n = 13 and BLBi(n) was computed up to n = 7.<br />
<br />
== Misc ==<br />
* Iijil shared an algorithm for converting an arbitrary n-state m-symbol TM into a 2-state TM with 3(n+1)m symbols. https://gist.github.com/Iijil1/0d611dbf0a9d52984f72cb14e66a4b28<br />
* Carl K updated his TM web-visualizer to support multi-symbol machines. [https://carlkcarlk.github.io/busy_beaver_blaze/v0.2.6/index.html#palette=edit&colors=000000%2Cff0000%2Cffff00%2Cff00ff%2C00ffff&run=true https://carlkcarlk.github.io/busy_beaver_blaze/v0.2.6/index.html] He also extended his series of videos showing TM simulation accompanied by classical music out to some multi-symbol TMs:<br />
** [[Bigfoot]]: https://youtu.be/YvOHWbQNMoY<br />
** [[Surprise in a Box|Brady's Surprise in a Box]]: https://youtu.be/vIG2CvJShRc<br />
** [[1RB3LA4RB0RB2LA 1LB2LA3LA1RA1RZ|BB(2,5) champ:]] https://youtu.be/QpYBzYDdLEY<br />
** Some interesting BB(2,5) machines: https://youtu.be/CSEKxTpXrDE<br />
*@mxdys Introduced "50 Random Holdouts", a thread on the Discord server, where 50 random TMs are selected from the BB(6) holdout list, and everybody focuses on these 50 machines. This month, 6/50 TMs were solved by @mxdys single-handedly.<br />
*The community (especially, Andrew Ducharme) [https://discord.com/channels/960643023006490684/992572017683472514/1408559249067479145 proposed a concept "BB(n,m) month",] where the community mainly focuses on a single domain, i.e. BB(3,3). The motive of this focused month is to make genuine progress in the one selected domain, with the ultimate goal to reduce all holdouts to [[Cryptids]], with all remaining TMs having been proven in Rocq.<br />
<br />
==Blog Posts==<br />
* 1 Sep 2025. Katelyn Doucette. [https://katelyndoucette.com/articles/all-about-space-needle All About Space Needle].<br />
<br />
==In the News==<br />
* 22 Aug 2025. Ben Brubaker. Quanta Magazine. [https://www.quantamagazine.org/busy-beaver-hunters-reach-numbers-that-overwhelm-ordinary-math-20250822/ Busy Beaver Hunters Reach Numbers That Overwhelm Ordinary Math].<br />
<br />
==Interesting TMs==<br />
A collection of interesting TMs that were mentioned on Discord, mostly because of their space-time diagrams or general behavior.<br />
<br />
* {{TM|1RB0LE_1RC0RF_1RD---_0LA1RB_1RB1LE_1LD1RF}}: Wavy Machine<br />
* {{TM|1RB0LD_1RC1RA_1LD0RB_1LE1LA_1RF0RC_---1RE}}: [[Probviously]] halting Cryptid<br />
* <code>[[1RB1LE_1LC0RA_0RF0LD_1LE1LA_1RC0LB_---1RC]]</code> ([https://bbchallenge.org/1RB1LE_1LC0RA_0RF0LD_1LE1LA_1RC0LB_---1RC bbch]): Unsolved BB(6) TM with pseudorandom behaviour<br />
<br />
[[Category:This Month in Beaver Research|2025-08]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=TMBR:_September_2025&diff=3570TMBR: September 20252025-09-01T02:40:23Z<p>Qwerpiw: </p>
<hr />
<div>{{stub}}<br />
[[:Category:This Month in Beaver Research|This Month in Beaver Research]] for September 2025<br />
[[Category:This Month in Beaver Research]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Talk:1RB1LE_1LC0RA_0RF0LD_1LE1LA_1RC0LB_---1RC&diff=3569Talk:1RB1LE 1LC0RA 0RF0LD 1LE1LA 1RC0LB ---1RC2025-09-01T02:39:17Z<p>Qwerpiw: </p>
<hr />
<div><br />
== More simulation ==<br />
<br />
It looks like it writes at least 10^53 ones according to Quick_Sim.py, I can try more experiments by messing with the block finder [[User:C7X|C7X]] ([[User talk:C7X|talk]]) 11:16, 30 August 2025 (UTC)<br />
<br />
Edit: no halt yet at >10^261 ones, >10^527 steps [[User:C7X|C7X]] ([[User talk:C7X|talk]]) 03:50, 31 August 2025 (UTC)</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=TMBR:_September_2025&diff=3568TMBR: September 20252025-09-01T02:38:43Z<p>Qwerpiw: </p>
<hr />
<div>{{stub}}<br />
This Month in Beaver Research for September 2025</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=TMBR:_September_2025&diff=3567TMBR: September 20252025-09-01T02:38:25Z<p>Qwerpiw: Created page with "{{stub}} This Month in Beaver Research for August 2025"</p>
<hr />
<div>{{stub}}<br />
This Month in Beaver Research for August 2025</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=TMBR:_August_2025&diff=3199TMBR: August 20252025-08-16T16:23:25Z<p>Qwerpiw: </p>
<hr />
<div>{{Stub}} <br />
[[:Category:This Month in Beaver Research|This Month in Beaver Research]] for August 2025.<br />
<br />
==Champions==<br />
<br />
==Holdouts==<br />
<br />
==BB Adjacent==<br />
*John Tromp introduced the <math>BB \lambda _1(n)</math> function for [[Busy Beaver for lambda calculus#Oracle Busy Beaver|Busy Beaver for lambda calculus with an oracle]] and computed it up to <math>BB \lambda _1(22)</math>.<br />
* Greedy Busy Beaver gBBi(n) was made.<br />
[[Category:This Month in Beaver Research]]<br />
<br />
==Blog Posts==<br />
<br />
==In the News==<br />
<br />
==Interesting TMs==<br />
<br />
[[Category:This Month in Beaver Research]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Doodle_function&diff=3143Doodle function2025-08-14T20:45:46Z<p>Qwerpiw: </p>
<hr />
<div>The '''doodle function''' is a function made by Lawrence Hollom. It is a two-argument function.<ref>https://web.archive.org/web/20230901195926/https://sites.google.com/a/hollom.com/extremely-big-numbers/home/doodle-function</ref><br />
<br />
== Definition ==<br />
The function revolves around a specific type of one-dimensional cellular automaton, in which state of a cell is determined by its own state and state of the cell to its right at previous generation (Hollom's original explanation is slightly different, but equivalent to this one). The function doodle(c,n) is then defined to be the longest time an automaton can go on without repeating the state, if we are constrained to automata with c states and initial seed of length at most n (with blank cells between non-blank cells counted).<br />
<br />
== Notation ==<br />
doodle(c) = doodle(c,2), just like how BB(n) = BB(n,2)<br />
== Known values ==<br />
doodle(1,n) = 1<br />
<br />
doodle(2,n) = n<br />
<br />
doodle(3,2) ≥ 487. Hollom checked every possible setup using a computer program and all others either looped in smaller number of steps, or haven't done so in 10,000 steps. He believes that 487 is the exact value of this function.<br />
<br />
They are no lower bounds for doodle(4,2), and doodle(5,2) yet.<br />
<br />
[[category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=1RB1LE_1LC0RA_1RB1LD_1LC0LC_1RF0LB_---1RE&diff=30751RB1LE 1LC0RA 1RB1LD 1LC0LC 1RF0LB ---1RE2025-08-13T17:03:25Z<p>Qwerpiw: Redirected page to 1RB1LC 1LA1RE 0RD0LA 1RZ1LB 1LD0RF 0RD1RB</p>
<hr />
<div>#redirect [[1RB1LC_1LA1RE_0RD0LA_1RZ1LB_1LD0RF_0RD1RB]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=1RB1LC_1LA1RD_1LA0LA_1LF0RE_0RF1RB_---1LB&diff=30741RB1LC 1LA1RD 1LA0LA 1LF0RE 0RF1RB ---1LB2025-08-13T17:02:58Z<p>Qwerpiw: Redirected page to 1RB1LC 1LA1RE 0RD0LA 1RZ1LB 1LD0RF 0RD1RB</p>
<hr />
<div>#redirect [[1RB1LC_1LA1RE_0RD0LA_1RZ1LB_1LD0RF_0RD1RB]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=1RB1LC_1LA1RD_1LA0LA_1LD0RE_0RF1RB_---1LC&diff=30731RB1LC 1LA1RD 1LA0LA 1LD0RE 0RF1RB ---1LC2025-08-13T17:01:51Z<p>Qwerpiw: Redirected page to 1RB1LC 1LA1RE 0RD0LA 1RZ1LB 1LD0RF 0RD1RB</p>
<hr />
<div>#redirect [[1RB1LC_1LA1RE_0RD0LA_1RZ1LB_1LD0RF_0RD1RB]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=1RB1LC_1LA1RD_1LA0LA_1LD0RE_0RF1RB_---1LB&diff=30721RB1LC 1LA1RD 1LA0LA 1LD0RE 0RF1RB ---1LB2025-08-13T17:01:16Z<p>Qwerpiw: Redirected page to 1RB1LC 1LA1RE 0RD0LA 1RZ1LB 1LD0RF 0RD1RB</p>
<hr />
<div>#redirect [[1RB1LC_1LA1RE_0RD0LA_1RZ1LB_1LD0RF_0RD1RB]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=1RB1LC_1LA1RE_0RD0LA_---1LB_1LE0RF_0RD1RB&diff=30701RB1LC 1LA1RE 0RD0LA ---1LB 1LE0RF 0RD1RB2025-08-13T17:00:46Z<p>Qwerpiw: Redirected page to 1RB1LC 1LA1RE 0RD0LA 1RZ1LB 1LD0RF 0RD1RB</p>
<hr />
<div>#redirect [[1RB1LC_1LA1RE_0RD0LA_1RZ1LB_1LD0RF_0RD1RB]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=1RB0RF_1RC1RB_1RD---_1LE0RA_1RB0LF_0LE1RD&diff=30691RB0RF 1RC1RB 1RD--- 1LE0RA 1RB0LF 0LE1RD2025-08-13T16:59:19Z<p>Qwerpiw: Redirected page to 1RB1RA 1RC1RZ 1LD0RF 1RA0LE 0LD1RC 1RA0RE</p>
<hr />
<div>#Redirect [[1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=1RB0LE_1RC1RB_1RD---_1LA0RF_0LA1RD_1RB0RE&diff=30681RB0LE 1RC1RB 1RD--- 1LA0RF 0LA1RD 1RB0RE2025-08-13T16:58:41Z<p>Qwerpiw: Redirected page to 1RB1RA 1RC1RZ 1LD0RF 1RA0LE 0LD1RC 1RA0RE</p>
<hr />
<div>#Redirect [[1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=1RB---_1LC0RF_1RE0LD_0LC1RB_1RA1RE_1RE0RD&diff=30661RB--- 1LC0RF 1RE0LD 0LC1RB 1RA1RE 1RE0RD2025-08-13T16:57:57Z<p>Qwerpiw: Redirected page to 1RB1RA 1RC1RZ 1LD0RF 1RA0LE 0LD1RC 1RA0RE</p>
<hr />
<div>#redirect [[1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Beeping_Busy_Beaver&diff=3065Beeping Busy Beaver2025-08-13T16:47:47Z<p>Qwerpiw: </p>
<hr />
<div>The '''Beeping Busy Beaver''' (BBB) function is a variant of the [[Busy Beaver Functions|Busy Beaver function]] proposed by Scott Aaronson in his 2020 [[Busy Beaver Frontier]] survey.<ref name=":0">Scott Aaronson. "The Busy Beaver Frontier". https://www.scottaaronson.com/papers/bb.pdf</ref> It is notable because it is uncomputable even if you have access to a halting oracle for Turing Machines.<br />
<br />
== Definition ==<br />
Consider a ''beeping Turing machine'', which is a [[Turing machine]] that has a special state named "beep state". Every time the TM enters the "beep state" it ''beeps''. There are two possibilities, either this TM beeps a finite number of times (and thus there is a final beep) or it never stops beeping. Nick Drozd coined the term [[Quasihalt|quasihalting]] to describe the event when a TM last beeps. A TM quasihalts if it beeps only a finite number of times.<ref>Nick Drozd. Beeping Busy Beavers. https://nickdrozd.github.io/2020/08/13/beeping-busy-beavers.html</ref> The Beeping Busy Beaver problem is analogous to the Busy Beaver problem, replacing halting with quasihalting. In other words, let <math>b(M)</math> be the number of steps the machine M takes until it quasihalts (beeps for the last time) if it quasihalts (we will say <math>b(M) = \infty</math> if the TM never stops beeping). Then<br />
<br />
<math display="block">\operatorname{BBB}(n) := \max_{{M \in T(n)\ :\ b(M) < \infty}} b(M)</math><br />
<br />
where <math>T(n)</math> is the set of Turing machines with <math>n</math> states and two symbols.<br />
<br />
Note that these Turing machines need not ever halt, so the [[Tree Normal Form]] algorithm needs to be modified (to allow TMs with no halt transitions) when searching for BBB champions.<br />
<br />
== Significance ==<br />
<br />
It is easy to see that <math>\operatorname{BBB}(n) \ge \operatorname{BB}(n)</math>, by letting the beep state be the state that is reached immediately before the halt state.<br />
<br />
Values <math>> \operatorname{BB}(n)</math> may occur when the machine emits a beep before entering non-halting behavior.<br />
<br />
Moreover, it turns out that <math>\operatorname{BBB}</math> grows uncomputably faster than <math>\operatorname{BB}</math> (as fast as BB augmented with a halting oracle).<br />
<br />
== Results ==<br />
<br />
* BBB(1) = 1<ref name=":0" /><br />
* BBB(2) = 6<ref name=":0" /><br />
* BBB(3) = 55<br />
* BBB(4) ≥ 32,779,478<br />
* BBB(5) ≥ 10<sup>14,006</sup><ref>Nick Drozd. https://scottaaronson.blog/?p=8088#comment-1981333</ref> and probably <math>BBB(5) \ge 10^{10^{10^5}}</math> due to a "[[probviously]]" quasihalting [[Cryptids|Cryptid]].<ref>Shawn Ligocki. Mother of Giants.https://www.sligocki.com/2022/04/03/mother-of-giants.html</ref><br />
<br />
*BBB(3,3) ≥ 10↑↑6<ref>https://groups.google.com/g/busy-beaver-discuss/c/EuIXSir4Eps</ref><br />
<br />
All known champions quasihalt by becoming [[Translated Cycler|Translated Cyclers]], a property which is known to be weaker than the general quasihalting condition.<br />
<br />
==Beeping booping busy beavers==<br />
An extension devised by Bram Cohen goes as follows: a Turing machine has two special transitions, a beep transition and a boop transition, both of which repeat infinitely often. The machine outputs an integer sequence corresponding to the number of beeps between successive boops. The machine's number is the number of transitions it takes to finish the first output value that is repeated infinitely many times. These machines are considered equivalent to Turing machines with second-order oracles.<br />
<br />
== References ==<br />
<br />
[[category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Beeping_Busy_Beaver&diff=3064Beeping Busy Beaver2025-08-13T16:47:30Z<p>Qwerpiw: </p>
<hr />
<div>The '''Beeping Busy Beaver''' (BBB) function is a variant of the [[Busy Beaver Functions|Busy Beaver function]] proposed by Scott Aaronson in his 2020 [[Busy Beaver Frontier]] survey.<ref name=":0">Scott Aaronson. "The Busy Beaver Frontier". https://www.scottaaronson.com/papers/bb.pdf</ref> It is notable because it is uncomputable even if you have access to a halting oracle for Turing Machines.<br />
<br />
== Definition ==<br />
Consider a ''beeping Turing machine'', which is a [[Turing machine]] that has a special state named "beep state". Every time the TM enters the "beep state" it ''beeps''. There are two possibilities, either this TM beeps a finite number of times (and thus there is a final beep) or it never stops beeping. Nick Drozd coined the term [[Quasihalt|quasihalting]] to describe the event when a TM last beeps. A TM quasihalts if it beeps only a finite number of times.<ref>Nick Drozd. Beeping Busy Beavers. https://nickdrozd.github.io/2020/08/13/beeping-busy-beavers.html</ref> The Beeping Busy Beaver problem is analogous to the Busy Beaver problem, replacing halting with quasihalting. In other words, let <math>b(M)</math> be the number of steps the machine M takes until it quasihalts (beeps for the last time) if it quasihalts (we will say <math>b(M) = \infty</math> if the TM never stops beeping). Then<br />
<br />
<math display="block">\operatorname{BBB}(n) := \max_{{M \in T(n)\ :\ b(M) < \infty}} b(M)</math><br />
<br />
where <math>T(n)</math> is the set of Turing machines with <math>n</math> states and two symbols.<br />
<br />
Note that these Turing machines need not ever halt, so the [[Tree Normal Form]] algorithm needs to be modified (to allow TMs with no halt transitions) when searching for BBB champions.<br />
<br />
== Significance ==<br />
<br />
It is easy to see that <math>\operatorname{BBB}(n) \ge \operatorname{BB}(n)</math>, by letting the beep state be the state that is reached immediately before the halt state.<br />
<br />
Values <math>> \operatorname{BB}(n)</math> may occur when the machine emits a beep before entering non-halting behavior.<br />
<br />
Moreover, it turns out that <math>\operatorname{BBB}</math> grows uncomputably faster than <math>\operatorname{BB}</math> (as fast as BB augmented with a halting oracle).<br />
<br />
== Results ==<br />
<br />
* BBB(1) = 1<ref name=":0" /><br />
* BBB(2) = 6<ref name=":0" /><br />
* BBB(3) = 55<br />
* BBB(4) ≥ 32,779,478<br />
* BBB(5) ≥ 10<sup>14,006</sup><ref>Nick Drozd. https://scottaaronson.blog/?p=8088#comment-1981333</ref> and probably <math>BBB(5) \ge 10^{10^{10^5}}</math> due to a "[[probviously]]" quasihalting [[Cryptids|Cryptid]].<ref>Shawn Ligocki. Mother of Giants.https://www.sligocki.com/2022/04/03/mother-of-giants.html</ref><br />
<br />
*BBB(3,3) ≥ 10↑↑6<ref>https://groups.google.com/g/busy-beaver-discuss/c/EuIXSir4Eps</ref><br />
<br />
All known champions quasihalt by becoming [[Translated Cycler|Translated Cyclers]], a property which is known to be weaker than the general quasihalting condition.<br />
<br />
Beeping booping busy beavers<br />
An extension devised by Bram Cohen goes as follows: a Turing machine has two special transitions, a beep transition and a boop transition, both of which repeat infinitely often. The machine outputs an integer sequence corresponding to the number of beeps between successive boops. The machine's number is the number of transitions it takes to finish the first output value that is repeated infinitely many times. These machines are considered equivalent to Turing machines with second-order oracles.<br />
<br />
== References ==<br />
<br />
[[category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Fast-Growing_Hierarchy&diff=3063Fast-Growing Hierarchy2025-08-13T16:45:56Z<p>Qwerpiw: </p>
<hr />
<div>A Fast-Growing Hierarchy (FGH) is an ordinal-indexed hierarchy of functions satisfying certain restrictions. FGHs are used for assigning growth rates to fast computable functions, and are useful for approximating scores and halting times of [[Turing machine|Turing machines]].<br />
[[Category:Functions]]<br />
== Definition ==<br />
<br />
A fundamental sequence for an ordinal <math>\alpha</math> is an increasing sequence of ordinals <math><\alpha</math> which is unbounded in <math>\alpha</math>. The <math>\beta</math>-th element of <math>\alpha</math>'s fundamental sequence is denoted by <math>\alpha[\beta]</math>. In the context of FGHs, there is usually a restriction that the sequence's length must be as small as possible (that is, the length is the [https://en.wikipedia.org/wiki/Cofinality cofinality] of <math>\alpha</math>). A system of fundamental sequences for a set of ordinals is a function which assigns a fundamental sequence to each ordinal in the set.<br />
<br />
Given a system of fundamental sequences for limit ordinals below <math>\lambda</math>, its corresponding FGH is defined by<br />
<br />
<math display="block">\begin{array}{l}<br />
f_0(n) & = & n+1 \\<br />
f_{\alpha+1}(n) & = & f_\alpha^n(n) & \text{for }\alpha<\lambda \\<br />
f_\alpha(n) & = & f_{\alpha[n]}(n) & \text{for limit ordinals }\alpha<\lambda<br />
\end{array}</math><br />
<br />
Most natural fundamental sequence systems almost exactly agree on the growth rates in their corresponding FGHs. Specifically, if <math>f,f'</math> are FGHs given by natural fundamental sequence systems, it is usually the case that <math>f_\alpha(n+1)>f'_\alpha(n)</math> and <math>f'_\alpha(n+1)>f_\alpha(n)</math> for all natural <math>n</math> and all successor ordinals <math>\alpha</math>. For this reason, the specific choice of a fundamental sequence system often doesn't matter for large ordinals. For small ordinals (below <math>\varepsilon_0</math>), a common choice of fundamental sequences is given by<br />
<br />
<math display="block">\begin{array}{l}<br />
(\alpha+\omega^{\beta+1})[n] & = & \alpha+\omega^\beta n & \text{if }\alpha\text{ is a multiple of }\omega^{\beta+1} \\<br />
(\alpha+\omega^\beta)[n] & = & \alpha+\omega^{\beta[n]} & \text{if }\alpha\text{ is a multiple of }\omega^\beta\text{ and }\beta\text{ is a limit ordinal}<br />
\end{array}</math><br />
<br />
The FGH given by these fundamental sequences is sometimes called the Wainer hierarchy. Above <math>\varepsilon_0</math>, a relatively elegant choice is the expansion associated to the [https://apeirology.com/wiki/Bashicu_matrix_system Bashicu matrix system], which has the [https://en.wikipedia.org/wiki/Fundamental_sequence_(set_theory)#Additional_conditions Bachmann property].</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=TMBR:_August_2025&diff=2902TMBR: August 20252025-08-10T16:44:46Z<p>Qwerpiw: </p>
<hr />
<div>{{Stub}} <br />
This month in busy beaver for August 2025.<br />
<br />
==Champions==<br />
<br />
==Holdouts==<br />
<br />
==BB Adjacent==<br />
*The function Tree Normal Form (TNF) for [[Instruction-Limited Busy Beaver|BBi]] was introduced.<br />
[[Category:This Month in Beaver Research]]<br />
<br />
==Blog Posts==<br />
<br />
==In the news==<br />
<br />
==Interesting TMs==<br />
<br />
[[Category:This Month in Beaver Research]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=TMBR:_August_2025&diff=2901TMBR: August 20252025-08-10T16:41:50Z<p>Qwerpiw: </p>
<hr />
<div>{{Stub}} <br />
This month in busy beaver for August 2025.<br />
<br />
==Champions==<br />
<br />
==Holdouts==<br />
<br />
==BB Adjacent==<br />
*The function Tree Normal Form (TNF) for [[Instruction-Limited Busy Beaver|BBi]] was introduced.<br />
[[Category:This Month in Beaver Research]]<br />
<br />
==Blog Posts==<br />
<br />
==In the news==<br />
<br />
==Interesting TMs==<br />
<br />
==Other==<br />
<br />
[[Category:This Month in Beaver Research]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=TMBR:_August_2025&diff=2900TMBR: August 20252025-08-10T16:38:33Z<p>Qwerpiw: </p>
<hr />
<div>{{Stub}} <br />
this month in busy beaver for August 2025.<br />
<br />
==BB Adjacent==<br />
*The function Tree Normal Form (TNF) for [[Instruction-Limited Busy Beaver|BBi]] was introduced.<br />
[[Category:This Month in Beaver Research]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Template:Stub&diff=2899Template:Stub2025-08-10T16:38:02Z<p>Qwerpiw: Created page with ":<div class="notice metadata plainlinks" id="stub">''This article is a stub. You can help the {{SITENAME}} by [{{fullurl:{{FULLPAGENAME}}|action=edit}} expanding it].''</div> <includeonly>Category:Stubs</includeonly><noinclude> ---- ''This template will categorize articles that include it into :Category:Stubs.'' </noinclude>"</p>
<hr />
<div>:<div class="notice metadata plainlinks" id="stub">''This article is a [[:Category:Article stubs|stub]]. You can help the {{SITENAME}} by [{{fullurl:{{FULLPAGENAME}}|action=edit}} expanding it].''</div><br />
<includeonly>[[Category:Stubs]]</includeonly><noinclude><br />
----<br />
''This template will categorize articles that include it into [[:Category:Stubs]].''<br />
</noinclude></div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Terminating_Turmite&diff=2816Terminating Turmite2025-08-07T01:53:21Z<p>Qwerpiw: </p>
<hr />
<div>A '''Terminating Turmite''' or '''Relative Movement Turing Machine''' is a 1 dimentional [[Turing machine]] which uses relative directions instead of absolute ones. So instead of moving (L)eft or (R)ight, it (P)roceeds forward (for one step in the same direction as last move or (T)urns-around (move one direction in the opposite direction). TT(n,k) is the maximum steps of all halting n-state, k-symbol Terminating Turmites when started on a blank tape.<br />
<br />
== History ==<br />
2D [[wikipedia:Turmite|Turmites]] also called '''turNing machines''' have been historically studied by Chris Langton in 1986 ([[wikipedia:Langton's_ant|Langton's ants]]), Allen Brady in 1988 (TurNing machines) and Greg Turk in 1989 (tur-mites). Until recently, it seems like much less investigation was put into 1D Turmites.<br />
<br />
==Values==<br />
<br />
== See Also ==<br />
* Google Sheet recording known values: https://docs.google.com/spreadsheets/d/18EXcLXM4Xb_qpKenV4oRGQQpCd45MJ4uawNWgmVvKTY/edit?gid=0#gid=0<br />
[[category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Talk:1RB1LE_1LC0RA_0RF0LD_1LE1LA_1RC0LB_---1RC&diff=2815Talk:1RB1LE 1LC0RA 0RF0LD 1LE1LA 1RC0LB ---1RC2025-08-07T01:51:59Z<p>Qwerpiw: Created page with "Turing machine for what function? ~~~~"</p>
<hr />
<div>Turing machine for what function?<br />
[[User:Qwerpiw|Qwerpiw]] ([[User talk:Qwerpiw|talk]]) 01:51, 7 August 2025 (UTC)</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=User:Qwerpiw/T%E2%82%98_function&diff=2808User:Qwerpiw/Tₘ function2025-08-06T19:07:20Z<p>Qwerpiw: </p>
<hr />
<div>{{DISPLAYTITLE:T<sub>M</sub> function}}<br />
<br />
Let M be a non-deterministic Turing machine which recognizes a language L, that is, for every input word u there is an accepting computation with input u if and only if u ∈ L. <br />
<br />
Let us assume that M terminates on every input. The simplest thing to assume is that if u ∈ L, the TM eventually gives "yes" and if u ∉ L, it gives "no". <br />
<br />
The smallest time (number of steps) of such a computation is denoted by T<sub>M</sub>(u) . For every n >= 1 we define T<sub>M</sub>(n) the maximum of all T<sub>M</sub>(u) for all accepted u of length <= n. Then T<sub>M</sub>(n): N → N is the time function of M. If M is a deterministic Turing machine, then its time function T(n) is [constructible][2] that is there is a deterministic Turing machine which computes values T(n) in time ≈ T(n$. <br />
<ref> https://mathoverflow.net/questions/307607/time-functions-of-non-deterministic-turing-machines-a-better-question/307614</ref>[[Category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=T_M_function&diff=2807T M function2025-08-06T19:04:59Z<p>Qwerpiw: Qwerpiw moved page T M function to Tₘ function</p>
<hr />
<div>#REDIRECT [[Tₘ function]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=User:Qwerpiw/T%E2%82%98_function&diff=2806User:Qwerpiw/Tₘ function2025-08-06T19:04:59Z<p>Qwerpiw: Qwerpiw moved page T M function to Tₘ function</p>
<hr />
<div>Let M be a non-deterministic Turing machine which recognizes a language L, that is, for every input word u there is an accepting computation with input u if and only if u ∈ L. <br />
<br />
Let us assume that M terminates on every input. The simplest thing to assume is that if u ∈ L, the TM eventually gives "yes" and if u ∉ L, it gives "no". <br />
<br />
The smallest time (number of steps) of such a computation is denoted by T<sub>M</sub>(u) . For every n >= 1 we define T<sub>M</sub>(n) the maximum of all T<sub>M</sub>(u) for all accepted u of length <= n. Then T<sub>M</sub>(n): N → N is the time function of M. If M is a deterministic Turing machine, then its time function T(n) is [constructible][2] that is there is a deterministic Turing machine which computes values T(n) in time ≈ T(n)$. <br />
<ref> https://mathoverflow.net/questions/307607/time-functions-of-non-deterministic-turing-machines-a-better-question/307614</ref>[[Category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=User:Qwerpiw/T%E2%82%98_function&diff=2805User:Qwerpiw/Tₘ function2025-08-06T18:43:46Z<p>Qwerpiw: Created page with "Let M be a non-deterministic Turing machine which recognizes a language L, that is, for every input word u there is an accepting computation with input u if and only if u ∈ L. Let us assume that M terminates on every input. The simplest thing to assume is that if u ∈ L, the TM eventually gives "yes" and if u ∉ L, it gives "no". The smallest time (number of steps) of such a computation is denoted by T<sub>M</sub>(u) . For every n >= 1 we define T<sub>M</sub>(..."</p>
<hr />
<div>Let M be a non-deterministic Turing machine which recognizes a language L, that is, for every input word u there is an accepting computation with input u if and only if u ∈ L. <br />
<br />
Let us assume that M terminates on every input. The simplest thing to assume is that if u ∈ L, the TM eventually gives "yes" and if u ∉ L, it gives "no". <br />
<br />
The smallest time (number of steps) of such a computation is denoted by T<sub>M</sub>(u) . For every n >= 1 we define T<sub>M</sub>(n) the maximum of all T<sub>M</sub>(u) for all accepted u of length <= n. Then T<sub>M</sub>(n): N → N is the time function of M. If M is a deterministic Turing machine, then its time function T(n) is [constructible][2] that is there is a deterministic Turing machine which computes values T(n) in time ≈ T(n)$. <br />
<ref> https://mathoverflow.net/questions/307607/time-functions-of-non-deterministic-turing-machines-a-better-question/307614</ref>[[Category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Sequences&diff=2804Sequences2025-08-06T18:25:22Z<p>Qwerpiw: </p>
<hr />
<div>This page lists sequences related to the Busy Beaver functions.<br />
<br />
These tables are incomplete, you can help by adding missing items. If you add a value, please add a reference to a paper or code with which it was computed/proved if possible.<br />
<br />
If the "canonical" values of a sequence are maintained on another Wiki page, please link to that, instead of replicating them here.<br />
<br />
=== Computable Sequences ===<br />
{| class="wikitable"<br />
!Sequence Name<br />
!Description<br />
!Values<br />
![[oeis:|OEIS]] sequence<br />
|-<br />
|2-symbol TM count<br />
|Number of n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) (halting or not) Turing machines.<br />
|<br />
|[[oeis:A052200|A052200]]<br />
|-<br />
|Number of n-state 2-symbol halt-free TMs<br />
|A Turing machine is halt-free if none of its instructions lead to the halt state.<br />
|<br />
|[[oeis:A337025|A337025]]<br />
|-<br />
|[[Lazy Beaver]]<br />
|The smallest positive number of steps a(n) such that no n-state Turing machine halts in exactly a(n) steps on an initially blank tape.<br />
|LB(1)=2, LB(2)=7, LB(3)=22, LB(4)=72, LB(5)=427<br />
|[[oeis:A337805|A337805]]<br />
|}<br />
<br />
=== Noncomputable Sequences ===<br />
The following sequences depend on the specific behavior of programs and are grouped by their position in the [[wikipedia:Arithmetical_hierarchy|arithmetical hierarchy]].<br />
<br />
Note that when the bbchallenge community refers to BB(n, m), we mean the Max Shift function S(n, m) defined below (if m is omitted, it is set to 2 by default). Some literature may refer to the Max Score function Σ(n, m) by BB(n, m) instead.<br />
<br />
==== Π1 ====<br />
{| class="wikitable"<br />
!Sequence Name<br />
!Symbol<br />
!Description<br />
!Values<br />
![[oeis:|OEIS]] sequence<br />
|-<br />
|[[Busy Beaver Functions#Max Shift Function S(n, m)|Max Shift Function]]<br />
|S(n, m)<br />
|The maximal number of steps that an n-state, m-symbol Turing machine can make on an initially blank tape before eventually halting.<br />
|[[Main Page|see the Main Page]]<br />
|[[oeis:A060843|A060843]]<br />
|-<br />
|[[Busy Beaver Functions#Max Score Function Σ(n, m)|Max Score Function]]<br />
|Σ(n, m)<br />
|Maximal number of 1's that an n-state, m-symbol Turing machine can print on an initially blank tape before halting.<br />
|<br />
|[[oeis:A028444|A028444]]<br />
|-<br />
|<br />
|BB_SPACE(n,m)<br />
|Maximum number of memory cells visited by a halting Turing machine with n states and m symbols starting from all-0 memory tape<br />
|BB_SPACE(1,2)=2, BB_SPACE(2,2)=4, BB_SPACE(3,2)=7, BB_SPACE(4,2)=16<br />
| -<br />
|-<br />
|<br />
|<br />
|Number of n-state Turing machines which halt.<br />
|<br />
|[[oeis:A004147|A004147]]<br />
|-<br />
|[https://nickdrozd.github.io/2021/02/14/blanking-beavers.html Blanking Beavers]<br />
|<br />
|The maximum number of steps that an n-state m-symbol Turing machine can make on an initially blank tape until it is blank again (halting or not)<br />
|<br />
| -<br />
|-<br />
|BB_clean<br />
|<br />
|The maximum number of steps that an n-state 2-symbol Turing machine can make on an initially blank tape until it halts on a blank tape<br />
|(see comments #75 and #77 [https://scottaaronson.blog/?p=5661 here])<br />
|<br />
|-<br />
|BB_ones<br />
|<br />
|The maximum number of 1's that an n-state 2-symbol Turing machine can make in a row, before halting on a 0 next to it<br />
|<br />
|<br />
|-<br />
|Size of the Runtime Spectrum<br />
|<math>R(n)</math><br />
|The number of distinct runtimes for a machine with a given number of symbols, for increasing number of states<br />
|see "The Spectrum of Runtimes" in "[https://www.scottaaronson.com/papers/bb.pdf The Busy Beaver Frontier]"<br />
|<br />
|-<br />
|<br />
|<br />
|The number of non-halting programs with n states which reach infinitely many tape cells<br />
|<br />
|-<br />
|[[Instruction-Limited Busy Beaver]]<br />
|BBi(n)<br />
|Maximum number of steps that an n-instruction Turing machine (allowing any number of states and symbols) can take on an initially blank tape before eventually halting.<br />
|<br />
|[[oeis:A384629|A384629]]<br />
|-<br />
|Instruction-Limited Symbol Busy Beaver<br />
|Σi(n)<br />
|Maximum number of non-blank symbols that an n-instruction Turing machine (allowing any number of states and symbols) can leave on an initially blank tape before eventually halting.<br />
|<br />
|[[oeis:A384766|A384766]]<br />
|-<br />
|}<br />
<br />
==== Π2 ====<br />
{| class="wikitable"<br />
!Sequence Name<br />
!Symbol<br />
!Description<br />
!Values<br />
![[oeis:|OEIS]] sequence<br />
|-<br />
|[[Beeping Busy Beaver]]<br />
|BBB(n)<br />
|The latest possible step that any 2-symbol TM with n states exits a chosen state finitely many times<br />
|see [[Beeping Busy Beaver#Results]]<br />
|-<br />
|Beeping booping busy beaver<br />
|BBBB(n)<br />
|<br />
|BBBB(1) = 1<br />
|}<br />
<br />
==== Yet ungrouped ====<br />
{| class="wikitable"<br />
!Sequence Name<br />
!Symbol<br />
!Description<br />
!Values<br />
![[oeis:|OEIS]] sequence<br />
|-<br />
|<br />
|#S(n, m)<br />
|The number of programs that halt after exactly S(n,m) steps ([[Busy Beaver Functions#Max Shift Function S(n, m)|Max Shift]]) for each n of a given m (including all equivalent transformations)<br />
|#S(1,2)=32, #S(2,2)=40, #S(3,2)=16<br />
| -<br />
|-<br />
|<br />
|#Σ(n, m)<br />
|The number of programs that halt with Σ(n, m) 1's on the tape ([[Busy Beaver Functions#Max Score Function Σ(n, m)|Max Score]]) for each n of a given m (including all equivalent transformations)<br />
|#Σ(1,2)=16, #Σ(2,2)=4, #Σ(3,2)=40<br />
| -<br />
|-<br />
|Maximum space<br />
|#BB_SPACE(n,m)<br />
|The number of programs that visited the most number of tape cells for a given (n,m) (including all equivalent transformations)<br />
|#BB_SPACE(1,2)=32, #BB_SPACE(2,2)=24, #BB_SPACE(3,2)=48<br />
| -<br />
|-<br />
|<br />
|<br />
|The average number of states that are reached infinitely many times, among all non-halting turing machines with n states<br />
|<br />
| -<br />
|}<br />
<br />
=== More possibilities ===<br />
<br />
* The number of distinct final tape states of halting machines with n states and m symbols, for some definition of "distinct"<br />
* Any of the above for machines with more than one tape, or tapes with more dimensions (2d grid, 3d, n-d...)<br />
* Machines with a finite tape, or a circular one of a certain length<br />
<br />
=== Further information ===<br />
For more information on sequences, see the [[oeis:wiki/Busy_Beaver_numbers|OEIS Wiki: Busy Beaver Numbers]], [https://oeis.org/search?q=busy+beaver OEIS search: "busy beaver"] and [[oeis:wiki/Index_to_OEIS:_Section_Br#beaver|OEIS Wiki: "related to busy beaver"]]<br />
[[Category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=TMBR:_August_2025&diff=2802TMBR: August 20252025-08-06T18:15:13Z<p>Qwerpiw: </p>
<hr />
<div>{{Stub}} this month in busy beaver for 2025 August<br />
<br />
==BB Adjacent==<br />
*The function Tree Normal Form (TNF) for [[Instruction-Limited Busy Beaver|BBi]] Was introduced.<br />
[[Category:This Month in Beaver Research]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=TMBR:_August_2025&diff=2801TMBR: August 20252025-08-06T18:14:55Z<p>Qwerpiw: </p>
<hr />
<div>{{Stub}} this month in busy beaver for 2025 August<br />
<br />
==BB Adjacent==<br />
*The function Tree Normal Form (TNF) for [[Instruction-Limited Busy Beaver|BBi]] Was introduced.</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Instruction-Limited_Busy_Beaver&diff=2800Instruction-Limited Busy Beaver2025-08-06T18:13:07Z<p>Qwerpiw: </p>
<hr />
<div>An '''n-instruction Turing machine''' is a [[Turing machine]] having an arbitrary number of states and symbols, but having only ''n'' defined transitions/instructions in its transition table (all others are undefined).<br />
<br />
An '''Instruction-Limited Busy Beaver''' is any n-instruction Turing machine taking the maximum number of steps ('''BBi(n)''') after starting from an initially blank tape before eventually halting, over all possible n-instruction Turing machines.<br />
<br />
Similarly, an '''Instruction-Limited Symbols Busy Beaver''' is any n-instruction Turing machine writing the most non-blank symbols ('''Σi(n)''') to the tape before halting, over all possible n-instruction Turing machines.<br />
<br />
An '''Instruction-Limited Busy Beaver Competition''' (or "game") is a contest to find, for a given n, the value of either BBi(n) or Σi(n).<br />
<br />
The '''Instruction-Limited Busy Beaver Sequences''' list the values for BBi(n) and Σi(n) for n=0, 1, 2, ....<br />
<br />
* The currently known values of BBi(n) for n>=0 are: 0, 1, 3, 5, 16, 37, 123, 3932963, .... BBi(8) is at least 6.889 x 10<sup>1565</sup>, which is the number of steps taken by the current 8-instruction champion machine, discovered by Nick Drozd.<br />
* The currently known values of Σi(n) for n>=0 are: 0, 1, 2, 4, 5, 9, 14, 2050, .... Σi(8) is at least 1.355 x 10<sup>783</sup>, which is the number of non-blank symbols written to tape by the same 8-instruction champion machine.<br />
<br />
As with the traditional Busy Beaver sequences, BBi(n) and Σi(n) are both uncomputable, with both growing faster than any computable function.<br />
<br />
A TM is considered to halt as soon as it reaches an undefined transition. This convention reduces the number of instructions for a BBi Turing machine. In the traditional BB(n,m) problem, there is no explicit instruction limit (albeit an upper bound of nm) and so it is advantageous to use an explicit halting instruction which allows the machine to take one additional step.<br />
<br />
== Motivation ==<br />
<br />
The goal of the original Busy Beaver contest, introduced by Tibor Radó, was to find a halting Turing machine of a given size that, when started on a blank tape, either runs for the longest number of steps ('''BB(n)'''), or which prints the largest number of 1’s to tape before halting ('''Σ(n)''') [1]. Originally, the contests considered only two-symbol Turing machines (0,1), so both the steps sequence (BB(1), BB(2), BB(3), ...) and the symbols sequence (Σ(1), Σ(2), Σ(3), ...) were functions of a single variable n, the number of states.<br />
<br />
The Busy Beaver contest was later generalized to m-symbol machines (0,1,2,…,m-1), so each contest for n states and m symbols has its own values for maximum steps ('''BB(n,m)'''), and for non-blank symbols written to tape ('''Σ(n,m)'''). While this adds more interesting individual contests, it does split the focus among different possible sequences. For example, it is natural to compare the original steps sequence (BB(n,2) for n=1, 2, 3, ...) with the steps sequence for 2-state, m-symbol Turing machines (BB(2,m) for m=1, 2, 3, ...).<br />
<br />
The Instruction-Limited Busy Beaver concept was primarily motivated by the goal of uniting the various Busy Beaver contests into a single sequence defined not by the maximum number of states and symbols ('''BB(n,m)'''), but rather by the number of instructions ('''BBi(n)'''). Furthermore, counting the number of instructions in a Turing machine is arguably a simpler way of defining a “machine of a given size” than is considering the numbers of states and symbols in its state table.<br />
<br />
A champion n-instruction Busy Beaver machine may lie within any a x b domain, and it may share the same number of steps and symbols written as a machine from a different domain altogether. For example, it was discovered that two different 7-instruction Turing machines take 3,932,963 steps and write 2,050 non-blank symbols, but one of these is a 2-state, 4-symbol machine with one undefined transition, while the other is a 3-state, 3-symbol machine with two undefined transitions.<br />
<br />
It is currently unknown what the state table shapes of BBi(n) champions for n>=8 will be. When n = a*b-1 for some a,b >=2, will BBi(n) be one less than one of the original values of BB(a,b)? Or will a more sparsely populated state table with a larger product of states and symbols be able to generate an even longer run time using n instructions? The current BBi(8) champion is a 3-state, 4-symbol machine, but this may still be surpassed by a 3-state, 3-symbol machine yet to be found.<br />
<br />
== Steps Champions ==<br />
{| class="wikitable"<br />
!n<br />
!BBi(n)<br />
!TNF Size<br />
!Champions<br />
!Notes<br />
!Reference<br />
|-<br />
| style="text-align: right;" | 1<br />
| style="text-align: right;" | '''1'''<br />
| style="text-align: right;" | 5<br />
|{{TM|0RH}} {{TM|1RH---}}<br />
|BB(1,2)<br />
|[[oeis:A384629|A384629]]<br />
|-<br />
| style="text-align: right;" | 2<br />
| style="text-align: right;" | '''3'''<br />
| style="text-align: right;" | 35<br />
|{{TM|0RB---_1LA---}}<br />
|<br />
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716114952818829 Shawn]<br />
|-<br />
| style="text-align: right;" | 3<br />
| style="text-align: right;" | '''5'''<br />
| style="text-align: right;" | 413<br />
|{{TM|1RB1LB_1LA---}} (and 13 others)<br />
|[[BB(2)|BB(2,2)]] - 1<br />
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716181214564353 Shawn]<br />
|-<br />
| style="text-align: right;" | 4<br />
| style="text-align: right;" | '''16'''<br />
| style="text-align: right;" | 8,053<br />
|{{TM|1RB---_0RC---_1LC0LA}}<br />
|<br />
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716260587700447 Shawn]<br />
|-<br />
| style="text-align: right;" | 5<br />
| style="text-align: right;" | '''37'''<br />
| style="text-align: right;" | 213,633<br />
|{{TM|1RB2LB---_2LA2RB1LB}}<br />
|[[BB(2,3)]] - 1<br />
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716514234040341 Shawn]<br />
|-<br />
| style="text-align: right;" | 6<br />
| style="text-align: right;" | '''123'''<br />
| style="text-align: right;" | 7,363,453<br />
|{{TM|1RB3LA1RA0LA_2LA------3RA}}<br />
|<br />
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393768821478785207 Shawn]<br />
|-<br />
| style="text-align: right;" | 7<br />
| style="text-align: right;" | '''3,932,963'''<br />
| style="text-align: right;" | 312,696,581<br />
|{{TM|1RB2LA1RA1RA_1LB1LA3RB---}}<br />
{{TM|1RB2LA1RA_1LC1LA2RB_---1LA---}}<br />
|[[BB(2,4)]] - 1, and <br />
A [[BB(3,3)]] high-ranking machine<br />
|[[oeis:A384629|A384629]] <br />
[https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/3x3 List of long-running BB(3,3) TMs]<br />
|-<br />
| style="text-align: right;" | 8<br />
| style="text-align: right;" | <math>> 6.889 \times 10^{1565}</math><br />
| style="text-align: right;" | 15,874,490,107<br />
|{{TM|1RB1LA------_1RC3LB1RB---_2LA2LC---0LC}}<br />
|Current Champion<br />
|[https://discord.com/channels/960643023006490684/1084047886494470185/1398753236835635252 nickdrozd] [https://discord.com/channels/960643023006490684/1084047886494470185/1398857599935578303 Shawn]<br />
|}<br />
<br />
== Symbols Champions ==<br />
{| class="wikitable"<br />
!n<br />
!'''Σ'''i(n)<br />
!TNF Size<br />
!Champions<br />
!Notes<br />
!Reference<br />
|-<br />
| style="text-align: right;" | 1<br />
| style="text-align: right;" | '''1'''<br />
| style="text-align: right;" | 5<br />
|{{TM|1RH---}}<br />
|Σ(1,2)<br />
|[[oeis:A384766|A384766]]<br />
|-<br />
| style="text-align: right;" | 2<br />
| style="text-align: right;" | '''2'''<br />
| style="text-align: right;" | 35<br />
|{{TM|1RB---_1LA---}} (and 7 others)<br />
|<br />
|[[oeis:A384766|A384766]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716114952818829 Shawn]<br />
|-<br />
| style="text-align: right;" | 3<br />
| style="text-align: right;" | '''4'''<br />
| style="text-align: right;" | 413<br />
|{{TM|1RB1LB_1LA---}} (and 4 others)<br />
|[[BB(2)|Σ(2,2)]]<br />
|[[oeis:A384766|A384766]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716181214564353 Shawn]<br />
|-<br />
| style="text-align: right;" | 4<br />
| style="text-align: right;" | '''5'''<br />
| style="text-align: right;" | 8,053<br />
|{{TM|1RB0LB---_1LA2RA---}} (and 40 others)<br />
|<br />
|[[oeis:A384766|A384766]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716260587700447 Shawn]<br />
|-<br />
| style="text-align: right;" | 5<br />
| style="text-align: right;" | '''9'''<br />
| style="text-align: right;" | 213,633<br />
|{{TM|1RB2LB---_2LA2RB1LB}}<br />
|Σ[[BB(2,3)|(2,3)]]<br />
|[[oeis:A384766|A384766]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716514234040341 Shawn]<br />
|-<br />
| style="text-align: right;" | 6<br />
| style="text-align: right;" | '''14'''<br />
| style="text-align: right;" | 7,363,453<br />
|{{TM|1RB3LA1RA0LA_2LA------3RA}}<br />
|<br />
|[[oeis:A384766|A384766]] [https://discord.com/channels/960643023006490684/960643023530762341/1393768821478785207 Shawn]<br />
|-<br />
| style="text-align: right;" | 7<br />
| style="text-align: right;" | '''2,050'''<br />
| style="text-align: right;" | 312,696,581<br />
|{{TM|1RB2LA1RA1RA_1LB1LA3RB---}}<br />
{{TM|1RB2LA1RA_1LC1LA2RB_---1LA---}}<br />
|Σ[[BB(2,4)|(2,4)]], and <br />
A Σ[[BB(3,3)|(3,3)]] high-ranking machine<br />
|[[oeis:A384766|A384766]] <br />
[https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/3x3 List of long-running BB(3,3) TMs]<br />
|-<br />
| style="text-align: right;" | 8<br />
| style="text-align: right;" | <math>> 1.355 \times 10^{783}</math><br />
| style="text-align: right;" | 15,874,490,107<br />
|{{TM|1RB1LA------_1RC3LB1RB---_2LA2LC---0LC}}<br />
|Current Champion<br />
|[https://discord.com/channels/960643023006490684/1084047886494470185/1398753236835635252 nickdrozd] [https://discord.com/channels/960643023006490684/1084047886494470185/1398857599935578303 Shawn]<br />
|}<br />
<br />
Notes:<br />
* Proven values for BBi(n) and Σi(n) are shown as bold in the above two tables.<br />
* Solving BBi(ab-1) requires solving BB(a,b) since all halting BB(a,b) TMs can be converted into halting (ab-1)-instruction TMs. Furthermore, <math>BBi(ab-1) \ge BB(a,b) - 1</math> (the -1 at the end is because in BB(a,b) the halting transition counts as a step, but in BBi(ab-1) the TM halts as soon as it reaches the undefined transition).<br />
** Thus solving BBi(8) will require solving [[BB(3,3)]] and in particular, it will require solving [[Bigfoot]], which is a [[Cryptids|Cryptid]].<br />
** So far, BBi(ab-1) champions are also classic BB(a,b) champions (but with the final halting transition removed) for all a,b ≥ 2 explored so far, but it is not known if this trend will continue.<br />
** Beyond the table above we have intrinsic lower bounds: BBi(9) ≥ BB(2,5)-1, BBi(11) ≥ max(BB(2,6),BB(3,4),BB(4,3),BB(6,2))-1.<br />
* TNF Size is the total number of TMs enumerated in [[TNF]] with n (or fewer) instructions defined.<br />
* BBi(n) ≥ n. A halting (n+1) x 1 TM that chains all its states together (A0 = 0RB, B0 = 0RC, C0 = 0RD, ...) through the penultimate TM state will take n steps to pass through all states exactly once (a repeat would guarantee non-halting). The penultimate state, the nth state, puts the TM into n+1st state, which is undefined and does not count as a step.<br />
* The convention for writing TMs in standard text format here is to include as many states and symbols as are referenced. So for example, we write {{TM|1RH---}} instead of {{TM|1RH}} since this TM references 2 symbols (including the implicit blank symbol 0).<br />
<br />
== Tree Normal Form (TNF) for BBi ==<br />
Shown below are the total number of n-instruction Turing machines for each number of instructions n>=0. The numbers of halting and non-halting machines for n=8 are not yet known. The function Tree Normal Form for BBi is denoted BBi<sub>TNF</sub>(n)<br />
{| class="wikitable"<br />
!n<br />
!All Machines<br />
!All Cumulative<br />
!Halting Machines<br />
!Halting Cumulative<br />
!Non-Halting Machines<br />
!Non-Halting Cumulative<br />
|-<br />
| style="text-align: right;" |0<br />
| style="text-align: right;" |1<br />
| style="text-align: right;" |1<br />
| style="text-align: right;" |1<br />
| style="text-align: right;" |1<br />
| style="text-align: right;" |0<br />
| style="text-align: right;" |0<br />
|-<br />
| style="text-align: right;" |1<br />
| style="text-align: right;" |4<br />
| style="text-align: right;" |5<br />
| style="text-align: right;" |2<br />
| style="text-align: right;" |3<br />
| style="text-align: right;" |2<br />
| style="text-align: right;" |2<br />
|-<br />
| style="text-align: right;" |2<br />
| style="text-align: right;" |30<br />
| style="text-align: right;" |35<br />
| style="text-align: right;" |17<br />
| style="text-align: right;" |20<br />
| style="text-align: right;" |13<br />
| style="text-align: right;" |15<br />
|-<br />
| style="text-align: right;" |3<br />
| style="text-align: right;" |378<br />
| style="text-align: right;" |413<br />
| style="text-align: right;" |260<br />
| style="text-align: right;" |280<br />
| style="text-align: right;" |118<br />
| style="text-align: right;" |133<br />
|-<br />
| style="text-align: right;" |4<br />
| style="text-align: right;" |7,640<br />
| style="text-align: right;" |8,053<br />
| style="text-align: right;" |5,581<br />
| style="text-align: right;" |5,861<br />
| style="text-align: right;" |2,059<br />
| style="text-align: right;" |2,192<br />
|-<br />
| style="text-align: right;" |5<br />
| style="text-align: right;" |205,580<br />
| style="text-align: right;" |213,633<br />
| style="text-align: right;" |160,952<br />
| style="text-align: right;" |166,813<br />
| style="text-align: right;" |44,628<br />
| style="text-align: right;" |46.820<br />
|-<br />
| style="text-align: right;" |6<br />
| style="text-align: right;" |7,149,820<br />
| style="text-align: right;" |7,363,453<br />
| style="text-align: right;" |5,843,696<br />
| style="text-align: right;" |6,010,509<br />
| style="text-align: right;" |1,306,124<br />
| style="text-align: right;" |1,352,944<br />
|-<br />
| style="text-align: right;" |7<br />
| style="text-align: right;" |305,333,128<br />
| style="text-align: right;" |312,696,581<br />
| style="text-align: right;" |258,044,501<br />
| style="text-align: right;" |264,055,010<br />
| style="text-align: right;" |47,288,627<br />
| style="text-align: right;" |48,641,571<br />
|-<br />
| style="text-align: right;" |8<br />
| style="text-align: right;" |15,561,793,526<br />
| style="text-align: right;" |15,874,490,107<br />
| style="text-align: center;" |?<br />
| style="text-align: center;" |?<br />
| style="text-align: center;" |?<br />
| style="text-align: center;" |?<br />
|}<br />
Enumeration of Turing machines in Tree Normal Form ([[TNF]]) for the Limited-Instruction Busy Beaver problem uses the following procedure:<br />
<br />
* The "null Turing machine" with 0 instructions is the root of the tree. This "machine" halts after 0 steps, writing no non-blank symbols to the tape.<br />
* The first instruction starts from A, the implied starting state, reads a 0 on the tape (which is blank at machine start) and must shift right (to avoid consideration of trivial mirror-image machines).<br />
** This allows the following four possibilities: A0→0RA, A0→0RB, A0→1RA, and A0→1RB. The two machines transitioning to state A never halt, while the two machines transitioning to state B halt. The two halting machines are next expecting an instruction for B0, but since no such instruction exists, the machines halt after a single step.<br />
* Following the enumeration of machines for each previous number of instructions, each of the halting machines is extended from the instruction at which it halted. For n=2, this instruction must be B0. (Non-halting machines cannot be extended since they can never reach a new instruction to be added.)<br />
* As per normal TNF procedure, the new instruction can write any symbol to tape, shift left or right, and transition to any state as long as:<br />
** The symbol written can be at most one greater than the highest symbol previously read or written, and<br />
** The state to which the instruction transitions can be at most one state greater than the current number of states.<br />
* For the BBi problem, any instruction that transitions to a "new" state (one not yet containing any instructions) can be interpreted as a "halting instruction". (e.g. The one-instruction machine A0→1RB is exactly the same as A0→1RH.) Similarly, this new state can be considered a "halt state", as there is functionally no difference between a halt state and an operational state having no instructions. (B = H.)<br />
** Unlike the traditional BB problem, where a halting instruction is normally used in the last remaining cell in an n x m transition table, it is necessary to consider all possible halting transitions for BBi, (not just those of the form →1RH), as this allows the most possible extensions of n-instruction machines to (n+1)-instruction machines.<br />
<br />
== See Also ==<br />
* OEIS list of BBi(n) values: https://oeis.org/A384629<br />
* OEIS list of Σi(n) values: https://oeis.org/A384766<br />
* Discussion on Discord: https://discord.com/channels/960643023006490684/960643023530762341/1393697378657374290<br />
<br />
[[category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=TMBR:_August_2025&diff=2709TMBR: August 20252025-08-02T16:01:49Z<p>Qwerpiw: Created page with "{{Stub}} this month in busy beaver for 2025 August"</p>
<hr />
<div>{{Stub}} this month in busy beaver for 2025 August</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Doodle_function&diff=2704Doodle function2025-07-31T21:50:37Z<p>Qwerpiw: </p>
<hr />
<div>The '''doodle function''' is a function made by Lawrence Hollom. It is a two-argument function.<ref>https://web.archive.org/web/20230901195926/https://sites.google.com/a/hollom.com/extremely-big-numbers/home/doodle-function</ref><br />
<br />
== Definition ==<br />
The function revolves around a specific type of one-dimensional cellular automaton, in which state of a cell is determined by its own state and state of the cell to its right at previous generation (Hollom's original explanation is slightly different, but equivalent to this one). The function doodle(c,n) is then defined to be the longest time an automaton can go on without repeating the state, if we are constrained to automata with c states and initial seed of length at most n (with blank cells between non-blank cells counted).<br />
<br />
== notation ==<br />
doodle(n) = doodle(n,2)<br />
== Known values ==<br />
doodle(1,n) = 1<br />
<br />
doodle(2,n) = n<br />
<br />
doodle(3,2) ≥ 487. Hollom checked every possible setup using a computer program and all others either looped in smaller number of steps, or haven't done so in 10,000 steps. He believes that 487 is the exact value of this function.<br />
<br />
They are no lower bounds for doodle(4,2), and doodle(5,2) yet.<br />
<br />
[[category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Doodle_function&diff=2703Doodle function2025-07-31T21:43:47Z<p>Qwerpiw: Created page with "The '''doodle function''' is a function made by Lawrence Hollom. It is a two-argument function.<ref>https://web.archive.org/web/20230901195926/https://sites.google.com/a/hollom.com/extremely-big-numbers/home/doodle-function</ref> == Definition == The function revolves around a specific type of one-dimensional cellular automaton, in which state of a cell is determined by its own state and state of the cell to its right at previous generation (Hollom's original explanatio..."</p>
<hr />
<div>The '''doodle function''' is a function made by Lawrence Hollom. It is a two-argument function.<ref>https://web.archive.org/web/20230901195926/https://sites.google.com/a/hollom.com/extremely-big-numbers/home/doodle-function</ref><br />
<br />
== Definition ==<br />
The function revolves around a specific type of one-dimensional cellular automaton, in which state of a cell is determined by its own state and state of the cell to its right at previous generation (Hollom's original explanation is slightly different, but equivalent to this one). The function doodle(c,n) is then defined to be the longest time an automaton can go on without repeating the state, if we are constrained to automata with c states and initial seed of length at most n (with blank cells between non-blank cells counted).<br />
<br />
== notation ==<br />
doodle(n) = doodle(n,2)<br />
== Known values ==<br />
doodle(1,n) = 1<br />
<br />
doodle(2,n) = n<br />
<br />
doodle(3,2) ≥ 487. Hollom checked every possible setup using a computer program and all others either looped in smaller number of steps, or haven't done so in 10,000 steps. He believes that 487 is the exact value of this function.<br />
<br />
[[category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=TMBR:_July_2025&diff=2702TMBR: July 20252025-07-31T21:27:50Z<p>Qwerpiw: </p>
<hr />
<div>[[File:Lovecraft beaver.png|alt=A monstrous beaver in the style of HP Lovecraft with pink tentacles coming out of its mouth, 5 red spider eyes, horns on its head, elbows and tail, moss colored fur, sharp purple claws and webbed feet.|thumb|Lovecraftian Beaver fan art made by Lauren]]<br />
The very first edition of [[:Category:This Month in Beaver Research|This Month in Beaver Research]] for July 2025.<br />
<br />
== Champions ==<br />
* (Late June) mxdys found a pair of new [[BB(6)]] champions pushing it into the pentational values: {{TM|1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE}} (scoring over 2↑↑2↑↑2↑↑10) and {{TM|1RB1LC_1LA1RE_0RD0LA_1RZ1LB_1LD0RF_0RD1RB}} (scoring over 10↑↑11010000).<br />
* mxdys confirms dyuan's [[BB(2,5)]] champion {{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ}}. [https://discord.com/channels/960643023006490684/1259770421046411285/1379877629288644722]<br />
* Nick Drozd discovered a [[Instruction-Limited Busy Beaver|BBi]](8) champion running <math>> 6.889 \times 10^{1565}</math> steps: {{TM|1RB1LA------_1RC3LB1RB---_2LA2LC---0LC}}. [https://discord.com/channels/960643023006490684/1084047886494470185/1398753236835635252]<br />
* Shawn Ligocki discovered a [[Reversible Turing Machine|BB<sub>rev</sub>(6)]] champion running 537,556 steps.<br />
<br />
== Holdout ==<br />
[[File:BB6 num holdouts over time.png|thumb|Number of [[BB(6)]] holdouts over time]]<br />
* mxdys announced that [[BB(6)]] is down to 2728 holdouts on 29 July. [https://discord.com/channels/960643023006490684/1239205785913790465/1399783936019664896]<br />
* A large group effort has enumerated [[BB(7)]] and filtered it down to less than 86 million holdouts. [https://discord.com/channels/960643023006490684/1369339127652159509/1399265628900294686]<br />
<br />
== BB Adjacent ==<br />
* [[Instruction-Limited Busy Beaver]] was introduced and calculated up to BBi(7).<br />
* [[Reversible Turing Machine]] Busy Beaver values were calculated up to BB_rev(5).<br />
* [[Terminating Turmite]]s (Relative Movement Turing Machines) was introduced.<br />
<br />
== In the News ==<br />
* 1 July 2025. The Quanta Podcast. [https://discord.com/channels/960643023006490684/1285212639399776256/1389643208811745310 How Amateurs Solved a Major Computer Science Puzzle].<br />
* 2 July 2025. Manon Bischoff. Spektrum. [https://www.spektrum.de/news/mathematik-die-sechste-fleissige-biber-zahl-ist-gigantisch/2274249 Wie der sechste Fleißige Biber die Mathematik an ihre Grenzen bringt].<br />
* 7 July 2025. Karmela Padavic-Callaghan. New Scientist. [https://www.newscientist.com/article/2487058-mathematicians-are-chasing-a-number-that-may-reveal-the-edge-of-maths/ Mathematicians are chasing a number that may reveal the edge of maths]. (Paywalled)<br />
* 11 July 2025. New Scientist podcast [https://www.newscientist.com/podcasts/how-geoengineering-could-save-us-from-climate-disaster-have-we-broken-mathematics-why-exercise-reduces-cancer-risk/ episode 311]. Discusses mxdys's [[BB(6)]] pentation result "We’re brushing up against the edge of mathematics".<br />
* 11 July 2025. Darren Orf. Popular Mechanics. [https://www.popularmechanics.com/science/math/a65357535/busy-beaver-six/ Mathematicians Say There’s a Number So Big, It’s Literally the Edge of Human Knowledge].<br />
* 18 July 2025 https://francis.naukas.com/2025/07/18/espeluznante-nueva-cota-inferior-para-la-funcion-castor-afanoso-bb6/<br />
<br />
== Interesting TMs ==<br />
* {{TM|1RB1LC_1LB0RA_0LD---_1LE0LA_0LF0RG_1LG0LG_0RB1RG}}: Tetrational [[Fractal]]<br />
* {{TM|1RB1RE_1LC0RA_0RF0LD_1LE1LC_1RA0RC_---0RB}}: Skeleton Finger<br />
* {{TM|1RB1RG_1LC1RA_0LD0LC_0RE0RB_1RE1RF_1LD0LC_0LE---}}: [[Bouncer]] that transitions into a [[Counter]]<br />
* {{TM|1RB1RE_0RC1RG_1LD0LA_0LE0LF_0RA1RC_1LC0LE_---1RE}}: Counter that transitions into a Bouncer<br />
* {{TM|1RB2LA2LC---_1LA2RB2RD---_3RB1LC1RD0LA_3LA1RD1LC0RB}}: Sneaky almost-Cryptid<br />
[[Category:This Month in Beaver Research|TMBR:2025-07]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=TMBR:_July_2025&diff=2701TMBR: July 20252025-07-31T21:26:26Z<p>Qwerpiw: </p>
<hr />
<div>[[File:Lovecraft beaver.png|alt=A monstrous beaver in the style of HP Lovecraft with pink tentacles coming out of its mouth, 5 red spider eyes, horns on its head, elbows and tail, moss colored fur, sharp purple claws and webbed feet.|thumb|Lovecraftian Beaver fan art made by Lauren]]<br />
The very first edition of [[:Category:This Month in Beaver Research|This Month in Beaver Research]] for July 2025.<br />
<br />
== Champions ==<br />
* (Late June) mxdys found a pair of new [[BB(6)]] champions pushing it into the pentational values: {{TM|1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE}} (scoring over 2↑↑2↑↑2↑↑10) and {{TM|1RB1LC_1LA1RE_0RD0LA_1RZ1LB_1LD0RF_0RD1RB}} (scoring over 10↑↑11010000).<br />
* mxdys confirms dyuan's [[BB(2,5)]] champion {{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ}}. [https://discord.com/channels/960643023006490684/1259770421046411285/1379877629288644722]<br />
* Nick Drozd discovered a [[Instruction-Limited Busy Beaver|BBi]](8) champion running <math>> 6.889 \times 10^{1565}</math> steps: {{TM|1RB1LA------_1RC3LB1RB---_2LA2LC---0LC}}. [https://discord.com/channels/960643023006490684/1084047886494470185/1398753236835635252]<br />
* a new [[Reversible Turing Machine|BB<sub>rev</sub>(6)]] champion has been found. it is equal to 537,556.<br />
<br />
== Holdout ==<br />
[[File:BB6 num holdouts over time.png|thumb|Number of [[BB(6)]] holdouts over time]]<br />
* mxdys announced that [[BB(6)]] is down to 2728 holdouts on 29 July. [https://discord.com/channels/960643023006490684/1239205785913790465/1399783936019664896]<br />
* A large group effort has enumerated [[BB(7)]] and filtered it down to less than 86 million holdouts. [https://discord.com/channels/960643023006490684/1369339127652159509/1399265628900294686]<br />
<br />
== BB Adjacent ==<br />
* [[Instruction-Limited Busy Beaver]] was introduced and calculated up to BBi(7).<br />
* [[Reversible Turing Machine]] Busy Beaver values were calculated up to BB_rev(5).<br />
* [[Terminating Turmite]]s (Relative Movement Turing Machines) was introduced.<br />
<br />
== In the News ==<br />
* 1 July 2025. The Quanta Podcast. [https://discord.com/channels/960643023006490684/1285212639399776256/1389643208811745310 How Amateurs Solved a Major Computer Science Puzzle].<br />
* 2 July 2025. Manon Bischoff. Spektrum. [https://www.spektrum.de/news/mathematik-die-sechste-fleissige-biber-zahl-ist-gigantisch/2274249 Wie der sechste Fleißige Biber die Mathematik an ihre Grenzen bringt].<br />
* 7 July 2025. Karmela Padavic-Callaghan. New Scientist. [https://www.newscientist.com/article/2487058-mathematicians-are-chasing-a-number-that-may-reveal-the-edge-of-maths/ Mathematicians are chasing a number that may reveal the edge of maths]. (Paywalled)<br />
* 11 July 2025. New Scientist podcast [https://www.newscientist.com/podcasts/how-geoengineering-could-save-us-from-climate-disaster-have-we-broken-mathematics-why-exercise-reduces-cancer-risk/ episode 311]. Discusses mxdys's [[BB(6)]] pentation result "We’re brushing up against the edge of mathematics".<br />
* 11 July 2025. Darren Orf. Popular Mechanics. [https://www.popularmechanics.com/science/math/a65357535/busy-beaver-six/ Mathematicians Say There’s a Number So Big, It’s Literally the Edge of Human Knowledge].<br />
* 18 July 2025 https://francis.naukas.com/2025/07/18/espeluznante-nueva-cota-inferior-para-la-funcion-castor-afanoso-bb6/<br />
<br />
== Interesting TMs ==<br />
* {{TM|1RB1LC_1LB0RA_0LD---_1LE0LA_0LF0RG_1LG0LG_0RB1RG}}: Tetrational [[Fractal]]<br />
* {{TM|1RB1RE_1LC0RA_0RF0LD_1LE1LC_1RA0RC_---0RB}}: Skeleton Finger<br />
* {{TM|1RB1RG_1LC1RA_0LD0LC_0RE0RB_1RE1RF_1LD0LC_0LE---}}: [[Bouncer]] that transitions into a [[Counter]]<br />
* {{TM|1RB1RE_0RC1RG_1LD0LA_0LE0LF_0RA1RC_1LC0LE_---1RE}}: Counter that transitions into a Bouncer<br />
* {{TM|1RB2LA2LC---_1LA2RB2RD---_3RB1LC1RD0LA_3LA1RD1LC0RB}}: Sneaky almost-Cryptid<br />
[[Category:This Month in Beaver Research|TMBR:2025-07]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Initial_Busy_Beaver&diff=2618Initial Busy Beaver2025-07-26T19:31:08Z<p>Qwerpiw: Referring to <math>BB_{init}(n, m, T)</math></p>
<hr />
<div>#redirect [[Least Busy Beaver]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Reversible_Turing_Machine&diff=2617Reversible Turing Machine2025-07-26T19:27:07Z<p>Qwerpiw: </p>
<hr />
<div>A '''Reversible Turing Machine''' (RTM) is a [[Turing machine]] for which the computation can always be run backwards from any step back to the previous configuration (and so forth all the way to the start of the computation). This property (called logical reversibility) has theoretical implications for the limits of computation. Specifically, non-reversible computation cannot scale beyond some limit due to the inherent energy cost whereas reversible computations may be able to.<br />
<br />
== History ==<br />
Charles Bennett described Reversible Turing Machines in a 1973 paper in which he proves that any standard TM can be simulated by a 3-tape quadruple RTM.<ref>C. H. Bennett, "[http://www.dna.caltech.edu/courses/cs191/paperscs191/bennett1973.pdf Logical reversibility of computation]", IBM Journal of Research and Development, vol. 17, no. 6, pp. 525–532, 1973</ref> He states that they can also be simulated by a 1-tape quadruple RTM, but with quadratic slowdown. It seems likely that a standard TM can also be simulated by a 1-tape quintuple RTM (the type considered in the rest of this article), however, that was not explicitly discussed in Bennett's paper.<br />
<br />
== Definition ==<br />
For 1-tape quintuple TMs, it is reversible if and only if:<br />
<br />
For all states, all transitions to that state:<br />
<br />
# Must move in the same direction<br />
# Must write different symbols<br />
Bruce Smith called this "microscopic reversibility"<ref>https://scottaaronson.blog/?p=4916#comment-1851339</ref><br />
<br />
The reversible Turing machine function is denoted BB<sub>rev</sub><br />
<br />
== Busy Beaver Champions ==<br />
We can restrict the Busy Beaver competition to only (1-tape) RTMs when doing that we get the following champions:<br />
{| class="wikitable"<br />
|+<br />
!Domain<br />
!Max Steps<br />
!TNF Size<br />
!Champion<br />
!Reference<br />
|-<br />
| [[BB(2)]]<br />
| style="text-align: right;" | 6<br />
| style="text-align: right;" | 21<br />
| {{TM|0RB1RZ_1LA1RB}}<br />
| [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki on Discord]<br />
|-<br />
| [[BB(3)]]<br />
| style="text-align: right;" | 17<br />
| style="text-align: right;" | 356<br />
| {{TM|0RB1RZ_0LC1RA_1RB1LC}}<br />
| [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki on Discord]<br />
|-<br />
| [[BB(4)]]<br />
| style="text-align: right;" | 48<br />
| style="text-align: right;" | 9,853<br />
| {{TM|1RB0LD_0LC0RB_1LA1LD_1LC1RZ}}<br />
| [https://discord.com/channels/960643023006490684/1243312334907375676/1389809599955210362 Matthew House] and [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki] on Discord<br />
|-<br />
| [[BB(5)]]<br />
| style="text-align: right;" | 388<br />
| style="text-align: right;" | 359,852<br />
| {{TM|1RB0RD_1RC0RB_1RD1RZ_1LE1LA_0LE0LA}}<br />
| [https://discord.com/channels/960643023006490684/1243312334907375676/1389817569342652578 Shawn Ligocki] and [https://discord.com/channels/960643023006490684/1243312334907375676/1389820614415618109 Matthew House] on Discord<br />
|-<br />
|[[BB(6)]]<br />
| style="text-align: right;" | ≥44,318<br />
| style="text-align: right;" | ≥9,931,603<br />
|{{TM|1RB0LA_1RC0RF_0LD1LE_1LD1LA_1RZ1RF_0RC0RB}}<br />
|[https://discord.com/channels/960643023006490684/1395095790443036682/1395097173879689226 Shawn Ligocki on Discord]<br />
|-<br />
|[[BB(7)]]<br />
| style="text-align: center;" | <math>> 10^{19}</math><br />
| style="text-align: right;" | ≥542,487,066<br />
|{{TM|1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB1RZ}}<br />
|(Early result from partial enumeration)<br />
|}<br />
<br />
== See Also ==<br />
<br />
* Discussion on Discord on 1 July 2025: https://discord.com/channels/960643023006490684/1243312334907375676/1389756466482647142<br />
<br />
== References ==<br />
<references /><br />
[[category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Lazy_Beaver&diff=2616Lazy Beaver2025-07-26T19:25:29Z<p>Qwerpiw: </p>
<hr />
<div>The '''Lazy Beaver''' function is a computable variation of the Busy Beaver function defined by Scott Aaronson in his 2020 review.<br />
<br />
LB(n, m) is the smallest k such that no n-state, m-symbol [[Turing machine]] halts in exactly k steps.<br />
<br />
== Computed Values ==<br />
Values found by Terry and [[User:Sligocki|Shawn Ligocki]] in 2021:<br />
{| class="wikitable"<br />
|+<br />
!<br />
!<br />
! colspan="5" |States<br />
|-<br />
!<br />
!<br />
!2<br />
!3<br />
!4<br />
!5<br />
!6<br />
|-<br />
| rowspan="5" |Symbols<br />
|2<br />
|7<br />
|22<br />
|72<br />
|427<br />
|8,407<br />
|-<br />
|3<br />
|23<br />
|351<br />
|189,270<br />
|<br />
|<br />
|-<br />
|4<br />
|93<br />
|242,789<br />
|<br />
|<br />
|<br />
|-<br />
|5<br />
|956<br />
|<br />
|<br />
|<br />
|<br />
|-<br />
|6<br />
|33,851<br />
|<br />
|<br />
|<br />
|<br />
|}<br />
<br />
== See Also ==<br />
<br />
[[category:Functions]]<br />
<br />
* https://oeis.org/A337805</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Hydra_function&diff=2615Hydra function2025-07-26T19:25:14Z<p>Qwerpiw: </p>
<hr />
<div>[[category:Functions]]<br />
[[File:Hydra Spiral.png|thumb|185px|A spiral-like figure that gives the first few terms of the Hydra sequences with initial values 2, 5, 8, 11, 14, and 17.]]<br />
The '''Hydra function''' is a [[Collatz-like]] function defined as:<br />
<math display="block">\textstyle H(n)\equiv n+\big\lfloor\frac{1}{2}n\big\rfloor=\Big\lfloor\frac{3}{2}n\Big\rfloor=\begin{cases}<br />
\frac{3n}{2}&\text{if }n\equiv0\pmod{2},\\<br />
\frac{3n-1}{2}&\text{if }n\equiv1\pmod{2}.\\<br />
\end{cases}</math><br />
It is named as such because of its connection to the unsolved halting problems for the [[Cryptids]] [[Hydra]] and [[Antihydra]]. Due to its simplicity, simulations for both of these [[Turing machines]] utilize this function instead of what can initially be proven.<br />
== Relationship to Hydra and Antihydra problems==<br />
Using the Hydra function, we can obtain simplified rules for Hydra and Antihydra:<br />
{|class="wikitable"<br />
! Hydra !! Antihydra<br />
|-align="center"<br />
|Let <math>C_H(a,b):=0^\infty\;\textrm{<A}\;2\;0^{3(a-2)}\;3^b\;2\;0^\infty</math>:<math display="block">\begin{array}{|lll|}\hline<br />
0^\infty\;\textrm{A>}\;0^\infty&\xrightarrow{20}&C_H(3,0),\\<br />
C_H(2a,0)&\xrightarrow{54a^2-48a-2}&0^\infty\;3^{9a-8}\;1\;\textrm{A>}\;2\;0^\infty,\\<br />
C_H(2a,b+1)&\xrightarrow{54a^2-39a-5}&C_H(3a,b),\\<br />
C_H(2a+1,b)&\xrightarrow{4b+54a^2-3a+4}&C_H(3a+1,b+2).\\\hline<br />
\end{array}</math><br />
|Let <math>A_H(a,b):=0^\infty\;1^a\;0\;1^{b-4}\;\textrm{E>}\;0^\infty</math>:<math display="block">\begin{array}{|lll|}\hline<br />
0^\infty\;\textrm{A>}\;0^\infty&\xrightarrow{11}&A_H(0,8),\\<br />
A_H(a,2b)& \xrightarrow{2a+3b^2-1}& A_H(a+2,3b),\\<br />
A_H(0,2b+1)&\xrightarrow{3b^2-3b-7}& 0^\infty\;\textrm{<F}\;110\;1^{3b-6}\;0^\infty,\\<br />
A_H(a+1,2b+1)&\xrightarrow{3b^2-7}& A_H(a,3b+1).\\\hline<br />
\end{array}</math><br />
|}<br />
<div class="toccolours mw-collapsible mw-collapsed">'''Proof'''<div class="mw-collapsible-content"><br />
Recall the high-level rules for Hydra and Antihydra:<br />
{|class="wikitable"<br />
! Hydra !! Antihydra<br />
|-align="center"<br />
|Let <math>C(a,b):=0^\infty\;\textrm{<A}\;2\;0^a\;3^b\;2\;0^\infty</math>:<math display="block">\begin{array}{|lll|}\hline<br />
0^\infty\;\textrm{A>}\;0^\infty&\xrightarrow{20}&C(3,0),\\<br />
C(2a,0)&\xrightarrow{6a^2+20a+4}&0^\infty\;3^{3a+1}\;1\;\textrm{A>}\;2\;0^\infty,\\<br />
C(2a,b+1)&\xrightarrow{6a^2+23a+10}&C(3a+3,b),\\<br />
C(2a+1,b)&\xrightarrow{4b+6a^2+23a+26}&C(3a+3,b+2).\\\hline<br />
\end{array}</math><br />
|Let <math>A(a,b):=0^\infty\;1^a\;0\;1^b\;\textrm{E>}\;0^\infty</math>:<math display="block">\begin{array}{|lll|}\hline<br />
0^\infty\;\textrm{A>}\;0^\infty&\xrightarrow{11}&A(0,4),\\<br />
A(a,2b)& \xrightarrow{2a+3b^2+12b+11}& A(a+2,3b+2),\\<br />
A(0,2b+1)&\xrightarrow{3b^2+9b-1}& 0^\infty\;\textrm{<F}\;110\;1^{3b}\;0^\infty,\\<br />
A(a+1,2b+1)&\xrightarrow{3b^2+12b+5}& A(a,3b+3).\\\hline<br />
\end{array}</math><br />
|}<br />
Already, both machines appear to be very similar. They have one parameter that increases exponentially with growth factor <math display="inline">\frac{3}{2}</math> and another that takes a pseudo-random walk. Below, the exponentially increasing variables are described by integer sequences:<br />
{|class="wikitable"<br />
! Hydra !! Antihydra<br />
|-align="center"<br />
|<math display="block">a_0=3,a_{n+1}=\begin{cases}\frac{3a_n+6}{2}&\text{if }a_n\equiv0\pmod{2}\\\frac{3a_n+3}{2}&\text{if }a_n\equiv1\pmod{2}\end{cases}</math><br />
|<math display="block">a_0=4,a_{n+1}=\begin{cases}\frac{3a_n+4}{2}&\text{if }a_n\equiv0\pmod{2}\\\frac{3a_n+3}{2}&\text{if }a_n\equiv1\pmod{2}\end{cases}</math><br />
|}<br />
This will make demonstrating the transformation easier. Now we will define a new integer sequence based on the old one and discover the recursive rules for that sequence. This new sequence is <math display="inline">b_n=\frac{1}{3}a_n+2</math> and <math>b_n=a_n+4</math> for Hydra and Antihydra respectively. We start by using <math>b_{n+1}</math> instead and substituting <math>a_{n+1}</math> for its recursive formula. By doing so, we get:<br />
{|class="wikitable"<br />
! Hydra !! Antihydra<br />
|-align="center"<br />
|<math display="block">b_0=3,b_{n+1}=\begin{cases}\frac{a_n+6}{2}&\text{if }a_n\equiv0\pmod{2}\\\frac{a_n+5}{2}&\text{if }a_n\equiv1\pmod{2}\end{cases}</math><br />
|<math display="block">b_0=8,b_{n+1}=\begin{cases}\frac{3a_n+12}{2}&\text{if }a_n\equiv0\pmod{2}\\\frac{3a_n+11}{2}&\text{if }a_n\equiv1\pmod{2}\end{cases}</math><br />
|}<br />
After that, we can substitute <math>a_n</math> for its solution in terms of <math>b_n</math>. What results is the following:<br />
{|class="wikitable"<br />
! Hydra !! Antihydra<br />
|-align="center"<br />
|<math display="block">b_0=3,b_{n+1}=\begin{cases}\frac{3(b_n-2)+6}{2}&\text{if }3(b_n-2)\equiv0\pmod{2}\\\frac{3(b_n-2)+5}{2}&\text{if }3(b_n-2)\equiv1\pmod{2}\end{cases}</math><br />
|<math display="block">b_0=8,b_{n+1}=\begin{cases}\frac{3(b_n-4)+12}{2}&\text{if }b_n-4\equiv0\pmod{2}\\\frac{3(b_n-4)+11}{2}&\text{if }b_n-4\equiv1\pmod{2}\end{cases}</math><br />
|}<br />
The <math>\text{if}</math> statements amount to checking if <math>b_n</math> is even or odd. After simplifying, we are done:<br />
{|class="wikitable"<br />
! Hydra !! Antihydra<br />
|-align="center"<br />
|<math display="block">b_0=3,b_{n+1}=\begin{cases}\frac{3b_n}{2}&\text{if }b_n\equiv0\pmod{2}\\\frac{3b_n-1}{2}&\text{if }b_n\equiv1\pmod{2}\end{cases}</math><br />
|<math display="block">b_0=8,b_{n+1}=\begin{cases}\frac{3b_n}{2}&\text{if }b_n\equiv0\pmod{2}\\\frac{3b_n-1}{2}&\text{if }b_n\equiv1\pmod{2}\end{cases}</math><br />
|}<br />
Now that we have demonstrated a strong similarity in the behaviour of both Turing machines, we can return to using the high-level rules. Doing that while considering the step counts yields the final result.<br />
</div></div><br />
Under these rules, the halting problem for Hydra is about whether repeatedly applying the function <math>H(n)</math>, starting with <math>n=3</math>, will eventually generate more even terms than twice the number of odd terms. Similarly, Antihydra halts if and only if repeatedly applying <math>H(n)</math>, starting with <math>n=8</math>, will eventually generate more odd terms than twice the number of even terms.<br />
<br />
=== Coding the Hydra and Antihydra problems using the Hydra function ===<br />
Paired with the corresponding even/odd criterion as loop halting condition (implemented as a counter variable) and initial Hydra function value, the Hydra function definition can be used to write computer programs that simulate the abstracted behavior of the Hydra and Antihydra Turing machines. The following Python program is a Hydra simulator:<br />
<syntaxhighlight lang="python" line="1"><br />
# 'a' and 'b' fulfill the same purpose as in the Hydra rules:<br />
# The current hydra function value<br />
a = 3<br />
# The even/odd condition counter<br />
b = 0<br />
# As long as Hydra has not halted, 'b' remains greater than -1.<br />
while b != -1:<br />
# If 'a' is even, decrement 'b', otherwise increase 'b' by 2.<br />
if a % 2 == 0:<br />
b -= 1<br />
else:<br />
b += 2<br />
# This performs one step of the Hydra function H(a) = a + floor(a/2).<br />
# Note that integer division by 2 is equivalent to one bit shift to the right (a >> 1)<br />
a += a//2<br />
</syntaxhighlight><br />
Replacing <code>a = 3</code> with <code>a = 8</code> and swapping <code>b -= 1</code> with <code>b += 2</code> turns this program into an Antihydra simulator.<br />
<br />
Determining whether these programs halt or not (and if so, after how many loop iterations) would resolve these open problems.<br />
==Properties==<br />
The Hydra function can be rewritten as follows:<br />
<math display="block">\begin{array}{l}<br />
H(2n)&=&3n,\\<br />
H(2n+1)&=&3n+1.\\<br />
\end{array}</math><br />
Now assume that for some positive integer <math>s</math> and every odd integer <math>t</math>, <math>H^s(2^st)=3^st</math> and <math>H^s(2^st+1)=3^st+1</math>, where <math>H^i(n)</math> is function iteration. Notice that we can write <math>2^{s+1}t=2\cdot2^st</math> and <math>2^{s+1}t+1=2\cdot2^st+1</math>, so if we apply <math>H</math> to these numbers, we get <math>H(2\cdot2^st)=3\cdot 2^st</math> and <math>H(2\cdot2^st+1)=3\cdot2^st+1</math>. Now, if we apply <math>H</math> to these numbers <math>s</math> times, we get <math>H^{s+1}\big(2^{s+1}t\big)=H^s(2^s\cdot3t)=3^{s+1}t</math> and <math>H^{s+1}\big(2^{s+1}t+1\big)=H^s(2^s\cdot3t+1)=3^{s+1}t+1</math>. Therefore, by mathematical induction we have proved the following formulas:<br />
<math display="block">\begin{array}{l}<br />
H^s(2^st)&=&3^st,\\<br />
H^s(2^st+1)&=&3^st+1.\\<br />
\end{array}</math><br />
This optimization can be directly applied to the high-level rules for Hydra and Antihydra, producing this result:<br />
{|class="wikitable"<br />
! Hydra !! Antihydra<br />
|-align="center"<br />
|Let <math>C_H(a,b):=0^\infty\;\textrm{<A}\;2\;0^{3(a-2)}\;3^b\;2\;0^\infty</math>:<br />
<math display="block">\begin{array}{|lll|}\hline<br />
C_H(2^st,b+s)&\xrightarrow{f_1(s,t)}&C_H(3^st,b),\\<br />
C_H(2^st+1,b)&\xrightarrow{f_2(s,t,b)}&C_H(3^st+1,b+2s),\\\hline<br />
\end{array}</math><br />
where <math display="inline">f_1(s,t)=\frac{3t(3^s-2^s)(18(3^s+2^s)t-65)}{5}-5s</math> and <math display="inline">f_2(s,t,b)=(b+s)4s+\frac{3t(3^s-2^s)(18(3^s+2^s)t-5)}{5}</math>.<br />
|Let <math>A_H(a,b):=0^\infty\;1^a\;0\;1^{b-4}\;\textrm{E>}\;0^\infty</math>:<math display="block">\begin{array}{|lll|}\hline<br />
A_H(a,2^st)& \xrightarrow{f_3(s,t,a)}& A_H(a+2s,3^st),\\<br />
A_H(a+s,2^st+1)&\xrightarrow{f_4(s,t)}& A_H(a,3^st+1),\\\hline<br />
\end{array}</math><br />
where <math display="inline">f_3(s,t,a)=(2a-3+2s)s+\frac{3t^2(9^s-4^s)}{5}</math> and <math display="inline">f_4(s,t)=\frac{3t^2(9^s-4^s)}{5}-7s</math>.<br />
|}<br />
== Visualizations ==<br />
The four images below depict the first 1000 values of four Hydra sequences with different initial values. Each row of pixels shows a number in binary on the right and its parity on the left (blue for even, red for odd):<br />
<gallery mode="packed" heights="250"><br />
File:HydraFunction-StartingValue2.png|Starting value 2. There are 492 even numbers and 508 odd numbers.<br />
File:HydraFunction-StartingValue5.png|Starting value 5. There are 497 even numbers and 503 odd numbers.<br />
File:Antihydra increasing value.png|Starting value 8. There are 499 even numbers and 501 odd numbers.<br />
File:HydraFunction-StartingValue11.png|Starting value 11. There are 481 even numbers and 519 odd numbers.<br />
</gallery></div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Maximum_Consecutive_Ones_Function&diff=2614Maximum Consecutive Ones Function2025-07-26T19:23:58Z<p>Qwerpiw: </p>
<hr />
<div>The '''Maximum Consecutive Ones''' function (named <math>num(n)</math> by Ben-Amram, Julstrom and Zwick)<ref>Ben-Amram A.M., Julstrom B.A. and Zwick U. (1996). [http://dx.doi.org/10.1007/BF01192693 A note on busy beavers and other creatures]. ''Mathematical Systems Theory'' '''29''' (4), July-August 1996, 375-386.</ref> is a [[Busy Beaver function]] which measures the maximum number of consecutive 1s left on the tape at halt across all n-state 2-symbol [[Turing machine]]s which leave all their 1s consecutively. Unlike <math>\Sigma(n)</math>, this allows some amount of order over the "API" of these TMs, so that their output can be used as inputs to another TM in some deterministic fashion. Note however, that this definition does not stipulate where the TM head must be positioned relative to the sequence of consecutive ones, so it is not completely trivial to use these results as input to a second TM.<br />
<br />
This function is only defined for 2-symbol TMs. It is not entirely clear how best to extend it to multi-symbol TMs. One option would be to keep the definition the same, so only TMs which halt with all 1s on the tape would qualify. Another would be to allow any symbols as long as all non-0 symbols were in one contiguous chunk on the tape.<br />
<br />
== Champions ==<br />
<br />
{| class="wikitable"<br />
|+ Known Values of num(n) function<br />
|-<br />
! Domain !! <math>num(n)</math> !! Champion TM !! Halting Config<br />
!Source<br />
|-<br />
| [[BB(1)]]|| 1 || {{TM|1RZ---}} || <math>0^\infty \; 1 \; \textrm{Z>} \; 0^\infty</math><br />
|Ben-Amram, Julstrom and Zwick (1996)<br />
|-<br />
|[[BB(2)]]<br />
|4<br />
|{{TM|1RB1LB_1LA1LZ}}<br />
|<math>0^\infty \; 1 \; \textrm{<Z} \; 1^3 \; 0^\infty</math><br />
|Ben-Amram, Julstrom and Zwick (1996)<br />
|-<br />
|[[BB(3)]]<br />
|6<br />
|{{TM|1RB1LC_1RC1LZ_1LA0LB}} and 3 others<br />
|<math>0^\infty \; 1 \; \textrm{<Z} \; 1^5 \; 0^\infty</math><br />
|Ben-Amram, Julstrom and Zwick (1996)<br />
|-<br />
|[[BB(4)]]<br />
|12<br />
|{{TM|1RB0LA_1RC1LB_1LB1RD_1RZ0RA}}<br />
|<math>0^\infty \; 1^{12} \; \textrm{Z>} \; 0^\infty</math><br />
|Ben-Amram, Julstrom and Zwick (1996)<br />
|-<br />
|[[BB(5)]]<br />
|165<br />
|{{TM|1RB1LA_1RC1LE_1RD1RE_0LA1RC_1RZ0LB}}<br />
|<math>0^\infty \; 1^{165} \; \textrm{Z>} \; 0^\infty</math><br />
|[https://groups.google.com/g/busy-beaver-discuss/c/pvtXPmuMsAg/m/UP0xcmwoEAAJ Announcement] by Andrés Sancho in Feb 2025<br />
|}<br />
Note: All TMs here are listed in [[TNF-1RB]] format with the exception that sometimes the halt transition is chosen to be <code>1LZ</code> when that leads to a "simpler" halting configuration.<br />
<br />
For BB(3), there are actually 4 champion machines that all leave exactly 6 1s: {{TM|1RB1RZ_0RC1RB_1LC1LA}}, {{TM|1RB1LC_1LA1RB_1LB1RZ}}, {{TM|1RB1RA_1LC1RZ_1RA1LB}}, {{TM|1RB1LC_1RC1RZ_1LA0LB}}.<br />
<br />
== References ==<br />
<references /><br />
[[category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Busy_Beaver_for_lambda_calculus&diff=2613Busy Beaver for lambda calculus2025-07-26T19:23:21Z<p>Qwerpiw: </p>
<hr />
<div>'''Busy Beaver for lambda calculus''' ('''BBλ''') is a variation of the [[Busy Beaver]] problem for [https://en.wikipedia.org/wiki/Lambda_calculus lambda calculus] invented by John Tromp. BBλ(n) = the maximum normal form size of any closed lambda term of size n. Like the traditional Busy Beaver functions, it is uncomputable (and in fact grows faster than any computable function). If you are not familiar with lambda calculus and beta-reduction, I recommend starting with that article.<br />
<br />
Size is measured in bits using [https://tromp.github.io/cl/Binary_lambda_calculus.html Binary Lambda Calculus] which is a binary prefix-free encoding for all closed lambda calculus terms.<br />
<br />
== Analogy to Turing machines ==<br />
We evaluate terms by applying ''beta-reductions'' until they reach a ''normal form''. As an analogy to [[Turing machines]]:<br />
* ''Lambda terms'' are like TM configurations (tape + state + position).<br />
* Applying ''beta-reduction'' to a term is like taking a TM step.<br />
* A term is in ''normal form'' if no beta-reductions can be applied. This is like saying the term has halted.<br />
* A term may or may not be reducible to a normal form. If it is, this is like saying the term halts.<br />
* Determining whether a term is reducible to a normal form is an undecidable problem equivalent to the halting problem.<br />
<br />
Note: That unlike for Turing machines, evaluating lambda terms is non-deterministic. Specifically, there may be multiple beta-reductions possible in a given term. However, if a term can be reduced to a normal form, that normal form is unique. It is not possible to reduce the original term to any different normal form. A term is '''strongly normalizing''' if any choice of beta-reductions will lead to this normal form and '''weakly normalizing''' if there exist divergent reduction paths which never reach the normal form.<br />
<br />
== Proof of Uncomputability ==<br />
The proof that BBλ(n) is uncomputable is very similar to Radó's original proof that Σ(n) is uncomputable. Proof by contradiction:<br />
<br />
Assume BBλ is computable and so there exists a term ''f'' which computes it on [[wikipedia:Church_encoding|Church numerals]]. In other words: for all <math>n \in \N</math>: <math>(f \; C_n)</math> beta reduces to normal form <math>C_{BB\lambda(n)}</math> (where <math>C_n</math> denotes the Church numeral ''n''). Denote the binary lambda encoded size of ''f'' as ''k''. Consider the term <math>f \; (C_2 \; C_n)</math> which has size <math>5n + k + 26</math> bits. This term reduces to <math>C_{BB\lambda(n^2)}</math> which has size <math>5 \cdot BB\lambda(n^2) + 6</math> bits. But for sufficiently large n, <math>n^2 > 5n + k + 26</math> and so <math>5 \cdot BB\lambda(n^2) + 6 > BB\lambda(5n + k + 26)</math>. But this is a contradiction, we've found a <math>5n + k + 26</math> bit term which reduces to a normal form larger than <math>BB\lambda(5n + k + 26)</math>.<br />
<br />
Thus BBλ(n) is uncomputable. A variation of this argument shows that BBλ(n) eventually dominates all computable functions.<br />
<br />
== Binary Lambda Encoding ==<br />
A lambda term using [https://en.wikipedia.org/wiki/De_Bruijn_indices De Bruijn indexes] is defined inductively as:<br />
* Variables: For any <math>n \in \mathbb{Z}^+</math>, Var(''n'') is a term. It represents a variable bound by the lambda expression ''n'' above this one (the De Bruijn index). It is typically written simply as <code>n</code>.<br />
* Lambdas: For any term ''T'', Lam(''T'') is a term. It represents a unary function with function body ''T''. It is typically written <math>\lambda T</math> or <code>\T</code>.<br />
* Applications: For any terms ''T, U'', App(''T, U'') is a term. It represents applying function ''T'' to argument ''U''. It is typically written <code>(T U)</code>.<br />
<br />
We can think of this as a tree where each variable is a leaf, a lambda is a node with one child and applications are nodes with 2 children. A term is '''closed''' if every variable is bound. In other words, for every Var(''n'') leaf node, there exists ''n'' Lam() nodes above it in the tree of the term.<br />
<br />
Encoding (''blc()'') is defined recursively:<br />
<math display="block">\begin{array}{l}<br />
blc(Var(n)) & = & 1^n 0 \\<br />
blc(Lam(T)) & = & 00 \; blc(T) \\<br />
blc(App(T, U)) & = & 01 \; blc(T) \; blc(U) \\<br />
\end{array}</math><br />
<br />
For example, the [https://en.wikipedia.org/wiki/Church_encoding#Church_numerals Church numeral] 2: <math>\lambda f x. (f \; (f \; x))</math> = <code>\\(2 (2 1))</code> = <code>Lam(Lam(App(Var(2), App(Var(2), Var(1))))</code> is encoded as <code>00 00 01 110 01 110 10</code> or simply <code>0000011100111010</code> (spaces are not part of the encoding, only used for demonstration purposes) and thus has size 16 bits.<br />
<br />
== Text Encoding conventions ==<br />
For human readability, a text encoding and set of conventions is used in this article. As described earlier we encode a lambda term as:<br />
* Var(''n'') -> <code>n</code><br />
* Lam(''T'') -> <code>(\T)</code><br />
* App(''T, U'') -> <code>(T U)</code><br />
<br />
However, parentheses are also dropped in certain cases by convention:<br />
* The outermost parentheses are dropped: <code>Lam(1)</code> -> <code>\1</code> and <code>App(1, 2)</code> -> <code>1 2</code>.<br />
* Parentheses are dropped immediately inside a Lam: <code>Lam(Lam(1))</code> -> <code>\\1</code> and <code>Lam(App(1, 1))</code> -> <code>\1 1</code>.<br />
* Parentheses are dropped in nested Apps using left associativity: <code>App(App(1, 2), 3)</code> -> <code>1 2 3</code>. (Note: parentheses are still required for <code>App(1, App(2, 3))</code> -> <code>1 (2 3)</code>).<br />
<br />
This is the convention used in John Tromp's code and so is used here for consistency.<br />
<br />
== Champions ==<br />
There are no closed lambda terms of size 0, 1, 2, 3 or 5 and so BBλ(n) is not defined for those values. The smallest closed lambda term is <code>\1</code> which has size 4.<br />
<br />
For the rest of n ≤ 20: BBλ(n) = n is trivial and can be achieved via picking any n bit term already in normal form. For example <code>\\...\1</code> and <code>\\...\2</code> with k lambdas has size 2k+2 and 2k+3 respectively (for k ≥ 1 and k ≥ 2 respectively).<br />
<br />
{| class="wikitable"<br />
|+<br />
!n<br />
!BBλ(n)<br />
!Champion<br />
!# Beta reductions<br />
!Normal form<br />
!Discovered By<br />
|-<br />
|21 || = 22 || <code>\(\1 1) (1 (\2))</code><br />
|1|| <code>\(1 (\2)) (1 (\2))</code> || John Tromp & Bertram Felgenhauer<br />
|-<br />
|22 || = 24 || <code>\(\1 1) (1 (\\1))</code><code>\(\1 1 1) (1 1)</code><br />
|1<br />
1<br />
| <code>\(1 (\\1)) (1 (\\1))</code> <code>\(1 1) (1 1) (1 1)</code>||John Tromp & Bertram Felgenhauer<br />
|-<br />
|23 || = 26 || <code>\(\1 1) (1 (\\2))</code><br />
|1|| <code>\(1 (\\2)) (1 (\\2))</code> || John Tromp & Bertram Felgenhauer<br />
|-<br />
|24 || = 30 || <code>\(\1 1 1) (1 (\1))</code><br />
|1|| <code>\(1 (\1)) (1 (\1)) (1 (\1))</code> || John Tromp & Bertram Felgenhauer<br />
|-<br />
|25 || = 42 || <code>\(\1 1) (\1 (2 1))</code> <br />
|3|| <code>\1 (\1 (2 1)) (1 (1 (\1 (2 1))))</code> || John Tromp & Bertram Felgenhauer<br />
|-<br />
|26 || = 52 || <code>(\1 1) (\\2 (1 2))</code> <br />
|3|| <code>\\2 (\\2 (1 2)) (1 (2 (\\2 (1 2))))</code> || John Tromp & Bertram Felgenhauer<br />
|-<br />
|27 || = 44 || <code>\\(\1 1) (\1 (2 1))</code> <br />
|3|| <code>\\1 (\1 (2 1)) (1 (1 (\1 (2 1))))</code> || John Tromp & Bertram Felgenhauer<br />
|-<br />
|28 || = 58 || <code>\(\1 1) (\1 (2 (\2))))</code> <br />
|3|| <code>\1 (\\1 (3 (\2))) (1 (\2 (\\1 (4 (\2)))))</code>|| John Tromp & Bertram Felgenhauer<br />
|-<br />
| 29 || = 223|| <code>\(\1 1) (\1 (1 (2 1)))</code><br />
|4|| <pre><br />
\B (B (1 B))<br />
where:<br />
B = (A (A (1 A)))<br />
A = (1 (\1 (1 (2 1))))<br />
</pre>||John Tromp & Bertram Felgenhauer<br />
|-<br />
|30<br />
|= 160<br />
|<code>(\1 1 1) (\\2 (1 2))</code> and<br />
<code>(\1 (1 1)) (\\2 (1 2))</code><br />
|7<br />
5<br />
|<pre><br />
\\2 B A (1 (2 B A))<br />
where:<br />
B = (\\2 A (1 (2 A)))<br />
A = (\\2 (1 2))<br />
</pre><br />
|John Tromp & Bertram Felgenhauer<br />
|-<br />
|31<br />
|= 267<br />
|<code>(\1 1) (\\2 (2 (1 2)))</code><br />
|6<br />
|<pre><br />
\\2 A (2 A (C (2 A)))<br />
where:<br />
C = (2 A (2 A (1 B (2 A))))<br />
B = (\3 A (3 A (1 (3 A))))<br />
A = (\\2 (2 (1 2)))<br />
</pre><br />
|John Tromp & Bertram Felgenhauer<br />
|-<br />
|32<br />
|= 298<br />
|<code>\(\1 1) (\1 (1 (2 (\2))))</code><br />
|<br />
|<br />
|John Tromp & Bertram Felgenhauer<br />
|-<br />
|33<br />
|= 1812<br />
|<code>\(\1 1) (\1 (1 (1 (2 1))))</code><br />
|5<br />
|<pre><br />
\C (C (C (1 C)))<br />
where:<br />
C = (B (B (B (1 B)))<br />
B = (A (A (A (1 A)))<br />
A = (1 (\1 (1 (1 (2 1)))))<br />
</pre><br />
|John Tromp & Bertram Felgenhauer<br />
|-<br />
|34 || <math>= \ 5 \left(2^{2^{2^2}}\right) + 6 = 327\,686</math><br />
| <code>(\1 1 1 1) (\\2 (2 1))</code> and<br />
<code>(\1 (1 1) 1) (\\2 (2 1))</code><br />
| || <math>C(2^{2^{2^2}})</math> || John Tromp & Bertram Felgenhauer<br />
|-<br />
|35 || <math>= 5 \left(3^{3^3}\right) + 6 > 3.8 \times 10^{13}</math><br />
| <code>(\1 1 1) (\\2 (2 (2 1)))</code> <br />
| || <math>C(3^{3^3})</math> || John Tromp & Bertram Felgenhauer<br />
|-<br />
|36 || <math>= 5 \left(2^{2^{2^3}}\right) + 6 > 5.7 \times 10^{77}</math><br />
| <code>(\1 1) (\1 (1 (\\2 (2 1))))</code><br />
| || <math>C(2^{2^{2^3}})</math>|| John Tromp & Bertram Felgenhauer<br />
|-<br />
|37 || <math> = BB\lambda(35)+2</math><br />
| <code>\(\1 1 1) (\\2 (2 (2 1)))</code><br />
| || <math>\lambda x. C(3^{3^3})</math>||mxdys, tromp, dyuan, sligocki<br />
|-<br />
|38 || <math>\ge 5 \left(2^{2^{2^{2^2}}}\right) + 6 > 10^{10^4}</math><br />
| <code>(\1 1 1 1 1) (\\2 (2 1))</code> and<br />
<code>(\1 (1 1) 1 1) (\\2 (2 1))</code><br />
| || <math>C(2^{2^{2^{2^2}}})</math> || John Tromp & Bertram Felgenhauer<br />
|-<br />
|39 || <math>\ge 5 \left(3^{3^{3^3}}\right) + 6 > 10^{10^{12}}</math><br />
| <code>(\1 1 1 1) (\\2 (2 (2 1)))</code> <br />
| || <math>C(3^{3^{3^3}})</math> || John Tromp & Bertram Felgenhauer<br />
|-<br />
|40 || <math> > (2\uparrow\uparrow)^{15} 33 > 10 \uparrow\uparrow\uparrow 16</math><br />
| <code>(\1 1 1) (\1 (\\2 (2 1)) 1)</code><br />
| || <math>\lambda x.T(k)</math> where <math>T(0)=x,\;T(n+1)=T(n)\;C(2)\;T(n)</math> and <math>k > (2\uparrow\uparrow)^{15} 33</math> || mxdys and racheline<br />
|-<br />
|41 || <math>\ge 5 \left(3^{3^{85}}\right) + 6 > 10^{10^{40}}</math><br />
| <code>(\1 (\1 1) 1) (\\2 (2 (2 1)))</code><br />
| || <math>C(3^{3^{85}})</math>||mxdys<br />
|-<br />
|42 ||<math> \ge BB\lambda(40)+2</math><br />
|<code>\(\1 1 1) (\1 (\\2 (2 1)) 1)</code><br />
| || ||<br />
|-<br />
|43 ||<math> > 2 \uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow 2 \uparrow\uparrow 8</math><br />
|<code>(\1 1) (\1 (\1 (\\2 (2 1)) 2))</code><br />
| || <math>\lambda x.T(k)</math> where <math>T(0)=x,\;T(n+1)=T(n)\;(\lambda y.y\;C(2)\;T(n))</math> and <math>k > 2 \uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow 2 \uparrow\uparrow 8</math>||mxdys<br />
|-<br />
|44 || <math> > 10 \uparrow\uparrow\uparrow 10 \uparrow\uparrow\uparrow 16</math><br />
| <code>(\1 1 1 1) (\1 (\\2 (2 1)) 1)</code> <br />
| || <math>\lambda x.T(k)</math> where <math>T(0)=x,\;T(n+1)=T(n)\;C(2)\;T(n)</math> and <math>k > (2\uparrow\uparrow)^{(2\uparrow\uparrow)^{15} 33 - 1} 33</math> ||<br />
|-<br />
|45 || <math> \ge BB\lambda(43)+2</math><br />
| <code>\(\1 1) (\1 (\1 (\\2 (2 1)) 2))</code><br />
| || ||<br />
|-<br />
|46 || <math> \ge BB\lambda(44)+2</math><br />
| <code>\(\1 1 1 1) (\1 (\\2 (2 1)) 1)</code><br />
| || ||<br />
|-<br />
|47 || <br />
| <br />
| || ||<br />
|-<br />
|48 || <math> > 10 \uparrow\uparrow\uparrow 10 \uparrow\uparrow\uparrow 10 \uparrow\uparrow\uparrow 16</math><br />
| <code>(\1 1 1 1 1) (\1 (\\2 (2 1)) 1)</code> <br />
| || <math>\lambda x.T(k)</math> where <math>T(0)=x,\;T(n+1)=T(n)\;C(2)\;T(n)</math> and <math>k > (2\uparrow\uparrow)^{(2\uparrow\uparrow)^{(2\uparrow\uparrow)^{15} 33 - 1} 33 - 1} 33</math> ||<br />
|-<br />
|49<br />
|<math>> f_{\omega+1}\left(\frac{2 \uparrow\uparrow 6}{2}\right) > \text{Graham's number}</math><br />
|<code>(\1 1) (\1 (1 (\\1 2 (\\2 (2 1)))))</code><br />
|<br />
|<math>C(N) \text{ for } N \approx f_{\omega+1}\left(\frac{2 \uparrow\uparrow 6}{2}\right)</math><br />
|[https://github.com/tromp/AIT/blob/master/fast_growing_and_conjectures/melo.lam Gustavo Melo]<br />
|-<br />
|...<br />
|<br />
|<br />
|<br />
|<br />
|<br />
|-<br />
|1850<br />
|> Loader's number<br />
|<code>too large to show</code><br />
|<br />
|<br />
|[https://codegolf.stackexchange.com/questions/176966/golf-a-number-bigger-than-loaders-number/274634#274634 John Tromp]<br />
|}<br />
<br />
Where <math>C(n)</math> represents the Church numeral ''n'' (<math>\lambda f x. f^n(x)</math>) written as <code>\\2 (2 ... (2 1)...)</code> with ''n'' 2s in this text representation.<br />
<br />
== See Also ==<br />
<br />
* https://oeis.org/A333479<br />
* [https://tromp.github.io/blog/2023/11/24/largest-number The largest number representable in 64 bits]. 24 Nov 2023. John Tromp.<br />
* [https://tromp.github.io/cl/Binary_lambda_calculus.html Binary Lambda Calculus]. John Tromp.<br />
* https://github.com/tromp/AIT/tree/master/BB<br />
[[category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Least_Busy_Beaver&diff=2612Least Busy Beaver2025-07-26T19:22:35Z<p>Qwerpiw: </p>
<hr />
<div>The '''least busy beaver''' <math>BB^-(n, m)</math> problem is a variation of the busy beaver problem which considers TM behavior across all starting tapes (not just blank tapes like the traditional BB problem) discovered by Racheline on 15 Feb 2025.<br />
<br />
== Definition ==<br />
Let <math>BB_{init}(n, m, T)</math> be the longest runtime for all n-state m-symbol TMs which halt when started on tape configuration T (where T is allowed to be any infinite tape configuration, including ones with an infinite number of non-zero values). Then<br />
<br />
<math display="block">BB^-(n, m) = min_T BB_{init}(n, m, T)</math><br />
<br />
In other words, the minimal value across all possible starting tapes. This minimum must exist because the values of <math>BB_{init}(n, m, T)</math> are all positive integers and thus well ordered.<br />
<br />
Note that <math>BB_{init}(n, m, B) = BB(n, m)</math> where B is the blank (all-zeros) tape. Therefore,<br />
<br />
<math display="block">BB^-(n, m) \le BB(n, m)</math><br />
<br />
We have not yet found an example where we can prove that <math>BB^-(n, m) \ne BB(n, m)</math>.<br />
<br />
== Known Results ==<br />
Clearly, <math>BB^-(1, m) = 1</math> for all positive integers <math>m</math>, since <math>BB_{init}(n, m, T)</math> is always at least <math>1</math> so we have <math>1\le BB^-(1,m)\le BB(1,m) = 1</math>.<br />
<br />
{| class="wikitable"<br />
|+ Small least busy beaver values <br />
|- <br />
| || 2-state || 3-state || 4-state <br />
|- <br />
| 2-symbol <br />
| <math>BB^-(2) = 6</math><br />
| <math>BB^-(3) = 21</math><br />
| <math>BB^-(4) = 107</math><br />
|-<br />
| 3-symbol <br />
| <math>BB^-(2, 3) = 38</math><br />
| <br />
| <br />
|}<br />
<br />
Racheline proved by hand that <math>BB^-(2, 2) = 6</math><ref><math>BB^-(2, 2) = 6</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340062334952935594 Link to first Discord message]</ref>, and with the help of computer searches, she proved <math>BB^-(3, 2) = 21</math><ref><math>BB^-(3, 2) = 21</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340098138924515458 Link to first Discord message]</ref>. She later made a program that automatically tries to confirm lower bounds <math>BB^-(n, m)\ge t</math>, by covering the set of all initial tapes with a family of sets, where each set of the family contains tapes that agree in a given radius around the starting position, such that a single TM halts in <math>\ge t</math> steps without leaving that shared part of the tapes (and therefore halts in <math>\ge t</math> steps on all of those tapes with the same transition history). This program verified her previous results<ref><math>BB^-(2, 2) = 6</math> and <math>BB^-(3, 2) = 21</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340790512160084130 Discord message link]</ref> and produced the results <math>BB^-(2, 3) = BB(2, 3) = 38</math><ref><math>BB^-(2, 3) = 38</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340773779198185607 Discord message link]</ref>, and later <math>BB^-(4, 2) = 107</math><ref><math>BB^-(4, 2) = 107</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340827079012384911 Discord message link]</ref> using Shawn Ligocki's idea to speed up the process by first using TMs that are likely to halt late (such as the TMs listed in [[BB(4)]]) to filter out most tapes. None of this has been formally verified as of 16 Feb 2025.<br><br />
Certificate of <math>BB^-(2, 2) = BB(2, 2) = 6</math>:<pre><br />
(0, 0, 0) 1RB1RZ_0LB1LA 6<br />
(0, 0, 1) 0LB1RZ_1RA0RB 6<br />
(0, 1, 0, 1, 0) 0RA0RB_0LB1RZ 6<br />
(0, 1, 0, 1, 1) 0LA0LB_0RB1RZ 6<br />
(1, 1, 0, 1, 1) 0RB1RZ_0LB0LA 7<br />
</pre><br />
Certificate of <math>BB^-(3, 2) = BB(3, 2) = 21</math>:<pre><br />
(0, 0, 0, 0, 1) 0LB0LC_1RB1LC_1RZ1RA 21<br />
(0, 0, 0, 1, 1) 1RB0LB_1RZ1LC_1RC1RA 22<br />
(0, 1, 0, 1, 1) 1RB0RC_1RC0LB_0LA1RZ 21<br />
(1, 0, 0, 0, 1) 0RA1LB_0LB0RC_1RA1RZ 23<br />
(1, 0, 0, 1, 0) 1LA1RB_0LC0RB_0LA1RZ 23<br />
(1, 0, 0, 1, 1) 0LB1RC_1LA1RZ_0RC0LA 21<br />
(1, 1, 0, 1, 1) 0RB0LB_1RZ1LC_1RA0RC 21<br />
(0, 0, 0, 0, 0, 0, 0) 1RB1RZ_1LB0RC_1LC1LA 21<br />
(0, 0, 0, 0, 0, 0, 1) 0LB1RZ_0LC1RB_1RA0RC 24<br />
(0, 0, 0, 0, 1, 0, 0) 0LB0RB_1RB1LC_1RZ0LA 22<br />
(0, 0, 0, 0, 1, 0, 1) 0LB0RB_1RB1LC_1RZ0LA 22<br />
(0, 0, 1, 0, 1, 0, 0) 0RA0RB_1LB1LC_1RA1RZ 21<br />
(0, 0, 1, 0, 1, 0, 1) 0LA0LB_1RB1RC_1LA1RZ 21<br />
(1, 0, 0, 0, 0, 0, 1) 0RA0LB_1LC1RZ_0LC1RA 40<br />
(1, 0, 0, 0, 1, 0, 0) 0LA1RB_0RB0LC_1LA1RZ 24<br />
(1, 0, 0, 0, 1, 0, 1) 0LA1RB_0RB0LC_1LA1RZ 24<br />
(1, 0, 1, 0, 1, 0, 1) 0RB1RZ_0LC0LB_1RA0LA 21<br />
</pre><br />
<br />
==Notes==<br />
<references /><br />
[[category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Terminating_Turmite&diff=2611Terminating Turmite2025-07-26T19:22:09Z<p>Qwerpiw: </p>
<hr />
<div>A '''Terminating Turmite''' or '''Relative Movement Turing Machine''' is a 1 dimentional [[Turing machine]] which uses relative directions instead of absolute ones. So instead of moving (L)eft or (R)ight, it (P)roceeds forward (for one step in the same direction as last move or (T)urns-around (move one direction in the opposite direction). TT(n,k) is the maximum steps of all halting n-state, k-symbol Terminating Turmites when started on a blank tape.<br />
<br />
== History ==<br />
2D [[wikipedia:Turmite|Turmites]] also called '''turNing machines''' have been historically studied by Chris Langton in 1986 ([[wikipedia:Langton's_ant|Langton's ants]]), Allen Brady in 1988 (TurNing machines) and Greg Turk in 1989 (tur-mites). Until recently, it seems like much less investigation was put into 1D Turmites.<br />
<br />
== See Also ==<br />
* Google Sheet recording known values: https://docs.google.com/spreadsheets/d/18EXcLXM4Xb_qpKenV4oRGQQpCd45MJ4uawNWgmVvKTY/edit?gid=0#gid=0<br />
[[category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Busy_Beaver_Functions&diff=2610Busy Beaver Functions2025-07-26T19:21:47Z<p>Qwerpiw: </p>
<hr />
<div>The Busy Beaver Game is the search for [[Turing machine|Turing machines]] which maximize various '''Busy Beaver Functions'''. All Busy Beaver functions are non-computable. There are several, related functions with different authors referring to one or the other as "the Busy Beaver function". Therefore, it is recommended that you use a more specific designation when referring to one specific Busy Beaver function.<br />
<br />
The two most commonly used Busy Beaver functions are:<br />
<br />
* The Maximum Shift function <math>S(n, m)</math> which is the most commonly used Busy Beaver function by [[Bbchallenge.org|bbchallenge]] and is generally called <math>BB(n, m)</math> here.<br />
* The Maximum Score function <math>\Sigma(n, m)</math> which is Tibor Radó's original Busy Beaver function.<br />
where <math>n</math> denotes the number of states and <math>m</math> the number of symbols.<br />
<br />
== Max Shift Function S(n, m) ==<br />
The Maximum Shift or Maximum Step function is the largest number of steps (or shifts) that any Turing machine (of a certain size, and starting with a blank tape) takes before halting. It was introduced by Tibor Radó in his seminal Busy Beaver paper.<ref>Tibor Radó (May 1962). "[https://computation4cognitivescientists.weebly.com/uploads/6/2/8/3/6283774/rado-on_non-computable_functions.pdf On non-computable functions]" (PDF). ''Bell System Technical Journal''. '''41''' (3): 877–884. https://doi.org/10.1002%2Fj.1538-7305.1962.tb00480.x</ref> He used the notation <math>S(n)</math> to define it for Turing machines with <math>n</math> states and 2 symbols. This was later extended to <math>S(n, m)</math> for <math>n</math> states and <math>m</math> symbols. Notably, the halting transition counts as a step, so the TM with rule <code>A0 -> 1RZ</code> halts in 1 step.<br />
<br />
Ben-Amram calls this the <math>time(n)</math> function.<ref name=":0">Ben-Amram A.M., Julstrom B.A. and Zwick U. (1996). [http://dx.doi.org/10.1007/BF01192693 A note on busy beavers and other creatures]. ''Mathematical Systems Theory'' '''29''' (4), July-August 1996, 375-386.</ref> Harland calls it the "frantic frog" function <math>ff(n)</math>.<ref name=":1">James Harland. [https://dl.acm.org/doi/pdf/10.5555/1151785.1151794 The Busy Beaver, the Placid Platypus and other Crazy Creatures]. 2006.</ref> <br />
<br />
In his 2020 [[Busy Beaver Frontier]] survey, Scott Aaronson used the notation <math>BB(n, m)</math> for the Max Shift function and referred to it as "the" Busy Beaver function.<ref name=":2">Scott Aaronson. [https://scottaaronson.blog/?p=4916 The Busy Beaver Frontier]. 2020.</ref><br />
<br />
== Max Score Function Σ(n, m) ==<br />
The Maximum Score function is the largest number of ones (or non-zero symbols in general) left on the tape by any halting Turing machine (of a certain size, and starting with a blank tape) at the moment it halts. It was also introduced by Tibor Radó in his seminal paper. He called it the "score" of the Turing machine. He used the notation <math>\Sigma(n)</math> to define it for Turing machines with <math>n</math> states and 2 symbols. This was later extended to <math>\Sigma(n, m)</math> for <math>n</math> states and <math>m</math> symbols.<br />
<br />
Ben-Amram calls this the <math>ones(n)</math> function.<ref name=":0" /> Harland calls it the "busy beaver" function <math>bb(n)</math>.<ref name=":1" /> Before Aaronson's survey, this was the function that most people called "the" Busy Beaver function.<br />
<br />
== Other Busy Beaver functions ==<br />
In addition to the above functions, there are a couple of others that have appeared in the literature:<br />
<br />
* Maximum space: Ben-Amram call this <math>space(n)</math><ref name=":0" />, bbchallenge calls it <code>BB_SPACE(n)</code> or <math>BB_{space}(n)</math>. This is the total number of tape cells read before halting. According to Ben-Amram, it includes the starting cell, but not necessarily the cell the halting transition moves to.<ref name=":0" /><br />
* [[Maximum Consecutive Ones Function|Maximum consecutive ones]]: Ben-Amram calls this <math>num(n)</math>.<ref name=":0" /> A TM only qualifies if it halts with all ones consecutive on tape.<br />
* <math>N_e</math> function: Radó formulated the number of halting machines in terms of the set of all valid busy beaver entries <math>M,s</math> where <math>M</math> is the Turing machine, and <math>s</math> is the exact number of steps the halting Turing machine took. The set of all halting <math>n</math>-card machines is denoted <math>E_n</math>, and the cardinality of this set is denoted <math>N_e(n)</math> The number of <math>n</math>-card Turing machines that halt after exactly or not more than s steps are respectively denoted <math>N(s,n)</math> and <math>G(s,n)</math>.<br />
* Blanking busy beaver: <math>BLB(n,m)</math> is the largest of steps done by any Turing machine with n states and m symbols before blanking the tape.<br />
* [[Beeping Busy Beaver|Beeping busy beaver]]: <math>BBB(n,m)</math> is the largest of steps done by any Turing machine with ''n'' states and ''m'' symbols before [[Quasihalt|quasihalting]].<br />
* Busy periodic beaver: <math>BBP(n,m)</math> is the largest period of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.<br />
* Busy preperiodic beaver: <math>BBS(n,m)</math> is the largest preperiod of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.<br />
* Higher order busy beaver functions:<br />
*BB<sub>L</sub>(n) (busy beaver for L programs):People have also studied variants with a 2-dimensional tape, or where the tape head is allowed to stay still in addition to moving left or right, etc. More broadly, given any programming language L, whose programs consist of bit-strings, one can define a Busy Beaver function for L-programs:BB<sub>L</sub>(n) := max<sub>P∈L∩{0,1}</sub><sup>≤n</sup><sub>: s(P)<∞</sub>s(P) where s(P) is the number of steps taken by P on a blank input. Alternatively, some people define a “Busy Beaver function for L-programs” using Kolmogorov complexity. That is, they let BB’<sub>L</sub>(n) be the largest integer m such that K<sub>L</sub> (m) ≤ n, where K<sub>L</sub>(m) is the length of the shortest L-program whose output is m on a blank input.<ref name=":3">[https://www.scottaaronson.com/papers/bb.pdf Scott Aaronson - The Busy Beaver frontier]</ref><br />
*<math>R(n)</math> (The runtime spectrum function): <math>T(n)</math> is the set of <math>n</math>-state Turing machines, and <math>s(M)</math> is the running time of machine <math>M</math> on an all-0 input tape. Let <math>R(n)</math> be the spectrum of possible runtimes of <math>n</math>-state machines on the all-0 input<math> R(n) := \lbrace k \in \natnums : s(M) = k \, \textrm{for} \, \textrm{some} \, M \in T(n) \rbrace</math>.<ref name=":3" /><br />
*[[Instruction-Limited Busy Beaver]] Function: <math> BBi(n)</math> is the longest runtime for all halting n-instruction (allowing any states and symbols) TMs when started on a blank tape.<br />
<br />
== References ==<br />
<references /><br />
[[category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=Instruction-Limited_Busy_Beaver&diff=2609Instruction-Limited Busy Beaver2025-07-26T19:21:24Z<p>Qwerpiw: </p>
<hr />
<div>An '''n-instruction Turing machine''' is a [[Turing machine]] with an arbitrary number of states and symbols, but only ''n'' defined transitions/instructions in its transition table (all others are undefined). The '''Instruction-Limited Busy Beaver''' (BBi(n)) problem is the Busy Beaver problem limited to n-instruction TMs. BBi(n) is the longest runtime for all halting n-instruction TMs when started on a blank tape and Σi(n) is the maximum number of non-blank symbols written by an n-instruction TM when halting and when started on a blank tape.<br />
<br />
A TM is considered to halt as soon as it reaches an undefined transition. This convention reduces the number of instructions for a BBi Turing machine. In the traditional BB(n,m) problem, there is no explicit instruction limit (albeit an upper bound of nm) and so it is advantageous to use an explicit halting instruction which allows the machine to take one additional step.<br />
<br />
== Motivation ==<br />
<br />
The goal of the original Busy Beaver contest, introduced by Tibor Radó, was to find a halting Turing machine of a given size that, when started on a blank tape, either runs for the longest number of steps ('''BB(n)'''), or which prints the largest number of 1’s to tape before halting ('''Σ(n)''') [1]. Originally, the contests considered only two-symbol Turing machines (0,1), so both the steps sequence (BB(1), BB(2), BB(3), ...) and the symbols sequence (Σ(1), Σ(2), Σ(3), ...) were functions of a single variable n, the number of states.<br />
<br />
The Busy Beaver contest was later generalized to m-symbol machines (0,1,2,…,m-1), so each contest for n states and m symbols has its own values for maximum steps ('''BB(n,m)'''), and for non-blank symbols written to tape ('''Σ(n,m)'''). While this adds more interesting individual contests, it does split the focus among different possible sequences. For example, it is natural to compare the original steps sequence (BB(n,2) for n=1, 2, 3, ...) with the steps sequence for 2-state, m-symbol Turing machines (BB(2,m) for m=1, 2, 3, ...).<br />
<br />
The Instruction-Limited Busy Beaver concept was primarily motivated by the goal of uniting the various Busy Beaver contests into a single sequence defined not by the maximum number of states and symbols ('''BB(n,m)'''), but rather by the number of instructions ('''BBi(n)'''). Furthermore, counting the number of instructions in a Turing machine is arguably a simpler way of defining a “machine of a given size” than is considering the numbers of states and symbols in its state table.<br />
<br />
A champion n-instruction Busy Beaver machine may lie within any a x b domain, and it may share the same number of steps and symbols written as a machine from a different domain altogether. For example, it was discovered that two different 7-instruction Turing machines take 3,932,963 steps and write 2,050 non-blank symbols, but one of these is a 2-state, 4-symbol machine with one undefined transition, while the other is a 3-state, 3-symbol machine with two undefined transitions.<br />
<br />
It is currently unknown what the state table shapes of BBi(n) champions for n>=8 will be. When n = a*b-1 for some a,b >=2, will BBi(n) be one less than one of the original values of BB(a,b)? Or will a more sparsely populated state table with a larger product of states and symbols be able to generate an even longer run time using n instructions? This is just one of the many questions that motivated the instruction-limited Busy Beaver contest.<br />
<br />
== Champions ==<br />
{| class="wikitable"<br />
!n<br />
!BBi(n)<br />
!TNF Size<br />
!Champions<br />
!Notes<br />
!Reference<br />
|-<br />
| style="text-align: right;" | 1<br />
| style="text-align: right;" | 1<br />
| style="text-align: right;" | 5<br />
|{{TM|0RB_---}} {{TM|1RB---_------}}<br />
|<br />
|[[oeis:A384629|A384629]]<br />
|-<br />
| style="text-align: right;" | 2<br />
| style="text-align: right;" | 3<br />
| style="text-align: right;" | 35<br />
|{{TM|0RB---_1LA---}}<br />
|<br />
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716114952818829 Shawn]<br />
|-<br />
| style="text-align: right;" | 3<br />
| style="text-align: right;" | 5<br />
| style="text-align: right;" | 413<br />
|{{TM|1RB1LB_1LA---}} (and 13 others)<br />
|[[BB(2)]] champion<br />
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716181214564353 Shawn]<br />
|-<br />
| style="text-align: right;" | 4<br />
| style="text-align: right;" | 16<br />
| style="text-align: right;" | 8,053<br />
|{{TM|1RB---_0RC---_1LC0LA}}<br />
|<br />
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716260587700447 Shawn]<br />
|-<br />
| style="text-align: right;" | 5<br />
| style="text-align: right;" | 37<br />
| style="text-align: right;" | 213,633<br />
|{{TM|1RB2LB---_2LA2RB1LB}}<br />
|[[BB(2,3)]] champion<br />
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716514234040341 Shawn]<br />
|-<br />
| style="text-align: right;" | 6<br />
| style="text-align: right;" | 123<br />
| style="text-align: right;" | 7,363,453<br />
|{{TM|1RB3LA1RA0LA_2LA------3RA}}<br />
|<br />
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393768821478785207 Shawn]<br />
|-<br />
| style="text-align: right;" | 7<br />
| style="text-align: right;" | 3,932,963<br />
| style="text-align: right;" | 312,696,581<br />
|{{TM|1RB2LA1RA1RA_1LB1LA3RB---}}<br />
{{TM|1RB2LA1RA_1LC1LA2RB_---1LA---}}<br />
|[[BB(2,4)]] champion and <br />
its [[BB(3,3)]] doppelganger<br />
|[[oeis:A384629|A384629]] <br />
[https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/3x3 List of longrunning BB(3,3) TMs]<br />
|-<br />
| style="text-align: right;" | 8<br />
| style="text-align: right;" | >=119,112,334,170,342,540<br />
| style="text-align: right;" | 15,874,490,107<br />
|{{TM|0RB2LA1RA_1LA2RB1RC_---1LB1LC}}<br />
|Current [[BB(3,3)]] champion<br />
|A384629<br />
|}<br />
<br />
Notes:<br />
* Solving BBi(ab-1) requires solving BB(a,b) since all halting BB(a,b) TMs can be converted into halting (ab-1)-instruction TMs. Furthermore, <math>BBi(ab-1) \ge BB(a,b) - 1</math> (the -1 at the end is because in BB(a,b) the halting transition counts as a step, but in BBi(ab-1) the TM halts as soon as it reaches the undefined transition).<br />
** Thus solving BBi(8) will require solving [[BB(3,3)]] and in particular, it will require solving [[Bigfoot]], which is a [[Cryptids|Cryptid]].<br />
** So far, BBi(ab-1) champions are also classic BB(a,b) champions (but with the final halting transition removed) for all a,b ≥ 2 explored so far, but it is not known if this trend will continue.<br />
** Beyond the table above we have intrinsic lower bounds: BBi(9) ≥ BB(2,5)-1, BBi(11) ≥ max(BB(2,6),BB(3,4),BB(4,3),BB(6,2))-1.<br />
* TNF Size is the total number of TMs enumerated in [[TNF]] with n (or fewer) instructions defined.<br />
* BBi(n) ≥ n. A halting (n+1) x 1 TM that chains all its states together (A0 = 0RB, B0 = 0RC, C0 = 0RD, ...) through the penultimate TM state will take n steps to pass through all states exactly once (a repeat would guarantee nonhalting). The penultimate state, the nth state, puts the TM into n+1st state, which is undefined and does not count as a step.<br />
<br />
== See Also ==<br />
* OEIS list of BBi(n) values: https://oeis.org/A384629<br />
* OEIS list of Σi(n) values: https://oeis.org/A384766<br />
* Discussion on Discord: https://discord.com/channels/960643023006490684/960643023530762341/1393697378657374290<br />
<br />
[[category:Functions]]</div>Qwerpiwhttps://wiki.bbchallenge.org/w/index.php?title=%CE%A3i&diff=2608Σi2025-07-26T19:20:58Z<p>Qwerpiw: Changed redirect target from Instruction-limited busy beaver to Instruction-Limited Busy Beaver</p>
<hr />
<div>#redirect [[instruction-Limited Busy Beaver]]</div>Qwerpiw