BusyBeaverWiki - User contributions [en]

TMBR: October 2025

2025-10-24T08:06:20Z

Racheline: added correct pronouns

{{TMBRnav|September 2025|November 2025}}''This edition of TMBR is in progress and has not yet been released. Please add any notes you think may be relevant (including in the form a of a TODO with a link to any relevant Discord discussion).''
[[File:Nico-BB-vs-Antihydra.jpg|thumb|A brave busy beaver confronts the dreaded Antihydra. Copyright [https://www.nicoroper.com/ Nico Roper].]]

== Misc ==
TODO: Add the mechanical Turing Machine. discord source: https://discord.com/channels/960643023006490684/1362008236118511758/1425889021653160026 and onwards

TODO: Add the method used by @Bricks to measure susceptibility to block-analysis. discord source: https://discord.com/channels/960643023006490684/1239205785913790465/1430227817957953638 also results: https://docs.google.com/spreadsheets/d/1j00LBxxp9W7uz1wZdMIvDCZ56eReuH0IGO9Z8-yybcQ/edit?usp=sharing[[File:Wily Coyote Roadrunner Naming.png|thumb|[[Wily Coyote]], a [[BB(3,3)]] holdout]]

== Blog Posts ==

* 22 Oct 2025. Ben Brubaker. [https://benbrubaker.com/why-busy-beaver-hunters-fear-the-antihydra/ Why Busy Beaver Hunters Fear the Antihydra].
* ? Oct 2025. Katelyn Doucette. [https://katelyndoucette.com/articles/building-the-busy-beaver-ladder Building the Busy Beaver Ladder].

== Champions ==

* [[BB(4,3)|BB(4,3):]]
**Polygon analysed the remaining "potential champions" discovered by Pavel Kropitz in May 2024, discovering that {{TM|1RB1RD1LC_2LB1RB1LC_1RZ1LA1LD_0RB2RA2RD|halt}} is the new BB(4,3) champion with a score of over <math>2 \uparrow^{4} 5</math>.

== Holdouts ==

* [[BB(6)|BB(6):]]
** @mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1429892916763033601 shared a new holdouts list on October 20th,] consisting of 1618 machines up to equivalence, or 3067 individual machines. This means 73 machines newly solved, a 4% reduction.
** @Bricks [https://discord.com/channels/960643023006490684/1239205785913790465/1430227817957953638 shared a machine] which they thought could be susceptible to [[Block Analysis|block-analysis]] based on a [[TMBR: October 2025#Misc|method they call Subtabe Saturation Heuristic.]] [[1RB1RF 0LC1RC 1RD1LC ---0RE 1RA1LF 1RA0LE|Shawn Ligocki's analysis]], simulated by @Bricks showed the machine to halt with sigma score of 4,419,340,317.
* [[BB(7)|BB(7):]]
** Andrew Ducharme has continued reducing the [[BB(7)#Phase 2|number of holdouts]] with Stage 4 of Phase 2. Initially, in the beginning of the month there were 22,801,601 holdouts, and 22,721,168 holdouts remain. (0.35% reduction)
*[[BB(3,4)|BB(3,4):]]
**[[User:XnoobSpeakable|XnoobSpeakable]] and [[User:WarpedWartWars|Lúkos]] are running filters in the domain under [[BB(3,4)#Phase 2|Phase 2]], reducing the holdout count from 434,787,751 to 17,983,810. (95.86% reduction)
*[[BB(4,3)|BB(4,3):]]
**Terry Ligocki has begun [[BB(4,3)#Stage 2|phase 2 of holdout reduction,]] reducing the number of holdouts from 460,916,384 to 9,401,447. (97.96% reduction)
*[[BB(2,6)|BB(2,6):]]
**Andrew Ducharme has completed [[BB(2,6)#Stage 3|stage 3 of phase 2]], reducing the number of holdouts from 873,469 to 870,085. (0.39% reduction)

== Theory ==
TODO: Update this section after studying existing literature a bit more.

[[Linear-Inequality Affine Transformation Automata]] (LIATA) were introduced as a generalization of the [[BMO1]] rules:

* @Bard proved that 3 dimension LIATA are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1420457986564030641]
* @star proved that 2 dimension LIATA are Turing complete: [https://discord.com/channels/960643023006490684/1239205785913790465/1421271424588451915]
* BMO1 is a 2d-LIATA so this provides some sense for the difficulty of the problem.

== Programming ==
TODO: Add -d's cpp quick_sim project. Discord source: https://discord.com/channels/960643023006490684/1226543091264126976/1426265937455222794

TODO: Add Katelyn's inductive project. Discord source:https://discord.com/channels/960643023006490684/1369339127652159509/1419016459560161280 https://discord.com/channels/960643023006490684/1095740122139480195/1427714010697961534
[[Category:This Month in Beaver Research|2025-10]]

Beeping Busy Beaver

2025-09-17T15:00:47Z

Racheline: /* Beeping Booping Busy Beavers */ mentioned three specific models of BBBB, and included the values for 1-state and 2-state (2-symbol) BBBB

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.

== Definition ==
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. 2020. [https://nickdrozd.github.io/2020/08/13/beeping-busy-beavers.html Beeping Busy Beavers].</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

<math display="block">\operatorname{BBB}(n) := \max_{{M \in T(n)\ :\ b(M) < \infty}} b(M)</math>

where <math>T(n)</math> is the set of Turing machines with <math>n</math> states and two symbols.

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.

== Significance ==

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.

In fact, BBB grows much faster than BB. BBB eventually dominates any computable function augmented with an oracle for computing BB. So, for example, there exists some N such that for all n > N:

* <math>BBB(n) > BB(BB(n))</math>
* <math>BBB(n) > BB^n(n)</math>, where <math>BB^k</math> represents k iterations of BB
* <math>BBB(n) > BB^{BB(n)}(n)</math>

etc.

== Results ==

* BBB(1) = 1<ref name=":0" />
* BBB(2) = 6<ref name=":0" /> by {{TM|1RB1LB_1LB1LA}}
* BBB(3) = 55 by {{TM|1LB0RB_1RA0LC_1RC1RA}}
* BBB(4) ≥ 32,779,478 by {{TM|1RB1LD_1RC1RB_1LC1LA_0RC0RD}}
* BBB(5) ≥ 1014,006<ref>Nick Drozd. https://scottaaronson.blog/?p=8088#comment-1981333</ref> by {{TM|1RB1LE_0LC0LB_0LD1LC_1RD1RA_0RC0LA}} and probably <math>BBB(5) \ge 10^{10^{10^5}}</math> due to four "[[probviously]]" quasihalting [[Cryptids]].<ref>Shawn Ligocki. 2022. [https://www.sligocki.com/2022/04/03/mother-of-giants.html Mother of Giants].</ref>

*BBB(2,3) = 59<ref>Nick Drozd. "[https://nickdrozd.github.io/2025/03/24/bbb-3-3.html BBB(3,3) > 10↑↑6]". Accessed 15 August 2025.</ref>
*BBB(3,3) ≥ 10↑↑6<ref>https://groups.google.com/g/busy-beaver-discuss/c/EuIXSir4Eps</ref> by {{TM|1RB0LB2LA_1LA0RC0LB_2RC2RB0LC}}
*BBB(2,4) > <math>2 \times 10^{23}</math><ref>Nick Drozd. "[https://nickdrozd.github.io/2022/02/11/latest-beeping-busy-beaver-results.html Latest Beeping Busy Beaver Results]". Accessed 15 August 2025.</ref> by {{TM|1RB2LA1RA1LB_0LB2RB3RB1LA}}

All known champions quasihalt by becoming [[Translated Cycler|Translated Cyclers]], a property which is known to be weaker than the general quasihalting condition.

==Beeping Booping Busy Beavers==
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.<ref>Bram Cohen. 2023. [https://bramcohen.com/p/beeping-booping-busy-beavers Beeping Booping Busy Beavers].</ref>

There are multiple models to choose from, depending on whether one allows multiple beep transitions and multiple boop transitions, or only one of each, or only one boop transition while making every transition a beep transition. All of these models have the same computational strength and corresponding growth rate, but each has its own advantages. The first is the most general, including all machines from the other two, and in that sense it is more natural, but that makes the space of candidate machines to search through significantly larger. The second is the original definition and it is relatively simple. The third is equivalent to simply considering the amount of time between successive boops, instead of the number of beeps between successive boops, and has the smallest space of candidate machines. It is not yet decided which of these models (or perhaps a model different from all three) should be chosen for "the" BBBB function.

It is known that for all three of these models, BBBB(1) = 2 and BBBB(2) = 17.<ref>[https://discord.com/channels/960643023006490684/1243312334907375676/1417836470793670697 Discord message]</ref>

== References ==

[[category:Functions]]

Lucy's Moonlight

2025-04-22T11:39:07Z

Racheline:

{{machine|1RB0RD_0RC1RE_1RD0LA_1LE1LC_1RF0LD_---0RA}}{{TM|1RB0RD_0RC1RE_1RD0LA_1LE1LC_1RF0LD_---0RA}}

'''Lucy's Moonlight''' is a [[probviously]] halting tetrational [[BB(6)]] [[Cryptid]] found by Racheline on 1 Mar 2025 ([https://discord.com/channels/960643023006490684/1239205785913790465/1345551751016878272 Discord link]). It has a 5% chance of beating the current BB(6) champion (if we treat Collatz-like behavior as random).

== Analysis by Racheline ==
https://discord.com/channels/960643023006490684/1345810396136865822/1345820781363597312<pre>
A(x,y) := 0^inf (1011)^x 10 <A (01)^y 0^inf
B(x) := 0^inf 1^x B> 0^inf

A(x+1,3y) -> A(x,8y+3)
A(x+2,3y+1) -> A(x,8y+11)
A(x+2,3y+2) -> A(x,8y+12)
A(0,y) -> B(2y+1)
A(1,3y+1) -> A(4y+4,4)
A(1,3y+2) -> halt
B(3y) -> B(8y-2)
B(3y+1) -> A(2y,4)
B(3y+2) -> B(8y+6)

a is the sequence such that A(x,a_n) goes to A(x',a_(n+1)) in one step assuming x>=2
b is the sequence such that A(x,a_0) goes to A(x-b_n,a_n) in n rules (without using the A(0,y) or A(1,y) rules) assuming x>=b_n
c is the sequence such that A(c_n,a_0) goes to A(c_(n+1),a_0) after only one application of the A(0,y) or A(1,y) rules

f(3n) = 8n+3
f(3n+1) = 8n+11
f(3n+2) = 8n+12
a_0 = 4
a_(n+1) = f(a_n)
b_0 = 0
b_(n+1) = b_n+(1 if 3|a_n else 2)

g(n) = 8ceil(n/3)-2 (i.e. g(3n) = 8n-2 and g(3n+2) = 8n+6)
h(n) = largest i such that b_i <= n
c_0 = 14
if b_h(c_n) = c_n, then c_(n+1) = 2m where m is minimal such that 3m+1 = g^k(2a_h(c_n)+1) for some k
otherwise if a_h(c_n) = 3m+1, then c_(n+1) = 4m+4
otherwise halt after roughly (8/3)^(6c_n/5) steps
</pre>

== Analysis by Shawn Ligocki ==
https://discord.com/channels/960643023006490684/1345810396136865822/1346329322851401868<pre>
1RB0RD_0RC1RE_1RD0LA_1LE1LC_1RF0LD_---0RA

C(a, b, c) = 0^inf 1011^a 1^b 10^c C> 0^inf
C(a, b) = C(a, b, 1) = 0^inf 1011^a 1^b 10 C> 0^inf

C(a+1, 3k) --> C(a, 8k+6)
C(a+2, 3k+1) --> C(a, 8k+16)
C(a+2, 3k+2) --> C(a, 8k+22)

C(0, 3k) --> C(2k, 8)
C(0, 3k+1) --> C(0, 8k+5)
C(1, 3k+1) --> Halt(6k+14)
C(0, 3k+2) --> C(0, 8k+5)
C(1, 3k+2) --> C(2k+4, 8)

Start --(2)--> C(0, 0)
</pre>Racheline's <math>c_n</math> values correspond to the values at which we get configs <math>C(c_n, 8)</math> in my analysis. The first three are:

* <math>c_0 = 14</math>
* <math>c_1 = 11\,292</math>
* <math>c_2 = </math> 8 282 581 182 265 963 777 660 116 067 041 084 396 825 871 729 769 475 063 015 437 507 606 888 488 657 640 984 741 410 755 868 651 202 413 557 949 100 792 150 345 468 805 096 096 950 985 621 014 344 543 514 277 244 259 988 659 130 143 328 155 990 590 108 709 713 794 583 253 323 686 355 356 512 219 061 229 636 197 885 927 258 835 226 571 319 297 308 352 230 934 484 006 197 639 625 592 087 971 234 386 001 742 614 119 317 946 288 524 516 349 575 343 597 522 485 283 906 000 542 032 088 582 043 646 950 532 639 630 385 985 319 217 159 379 913 000 142 879 141 905 099 969 565 530 694 702 807 960 713 276 894 845 659 927 803 312 770 155 623 893 892 127 451 599 296 902 730 174 376 009 710 735 758 161 389 656 270 797 836 582 256 488 031 353 066 716 635 172 987 950 448 854 471 226 597 449 927 236 184 172 841 640 111 209 332 317 049 722 869 659 569 874 196 714 141 959 835 401 796 418 444 068 891 026 981 841 656 732 128 708 017 637 486 218 786 090 173 524 036 425 924 718 502 564 851 924 717 340 390 259 248 282 032 112 075 387 681 859 362 344 399 913 313 735 645 684 525 131 229 468 282 784 360 728 881 748 147 372 112 747 036 418 378 308 364 410 128 040 328 676 209 420 026 633 482 346 143 509 117 105 276 670 245 493 297 604 407 287 182 199 289 609 254 900 080 171 095 368 953 306 931 467 191 729 590 199 363 109 109 618 828 683 456 945 716 771 345 293 252 204 756 902 270 830 478 266 505 243 340 324 828 877 091 406 917 371 244 363 787 314 164 920 400 219 556 757 173 398 748 668 149 395 792 060 530 400 633 872 912 079 249 392 256 126 285 748 793 796 259 657 854 699 829 517 626 609 309 417 076 213 461 174 150 922 612 299 942 658 509 909 739 815 101 078 137 303 456 289 178 147 820 849 027 886 955 738 533 503 625 157 087 287 391 831 669 455 397 075 444 062 908 165 633 623 616 230 849 011 917 173 994 535 718 598 409 770 737 638 239 724 998 256 861 644 166 630 982 723 063 781 225 891 358 955 048 633 229 232 741 851 699 498 876 266 677 026 907 578 098 686 784 323 407 335 765 343 701 077 746 445 802 114 304 942 791 377 887 303 588 107 097 550 867 703 017 440 867 027 391 593 474 985 628 594 939 344 739 091 341 577 631 399 711 011 114 031 231 392 355 268 858 286 239 590 222 739 798 802 836 719 470 359 138 334 346 097 704 505 528 574 751 020 940 898 407 003 617 333 219 550 156 008 932 231 022 648 658 161 473 903 774 681 072 952 056 320 551 244 912 271 864 381 014 835 634 282 966 523 463 985 953 949 176 576 786 408 020 337 836 220 233 538 960 379 978 664 849 564 796 907 967 238 406 785 655 383 464 715 057 232 716 549 617 630 853 473 306 701 852 904 885 606 863 527 445 121 198 511 795 947 547 473 084 736 520 465 867 328 457 114 967 373 145 664 842 684 299 186 357 472 668 934 663 435 131 859 827 025 004 311 417 517 867 339 721 854 899 421 107 496 540 906 158 691 502 108 225 108 606 878 323 722 157 711 420 937 080 640 504 487 833 073 951 122 223 191 857 376 281 164 771 129 574 147 051 021 933 227 085 689 827 336 672 385 780 462 357 440 219 398 403 103 894 053 177 742 661 833 002 598 347 813 276 596 599 779 500 262 101 470 481 321 560 131 349 255 581 918 937 061 811 724 247 415 920 101 784 002 187 650 019 023 113 164 778 491 907 065 101 691 880 663 970 914 566 257 787 660 257 139 627 941 284 081 248 034 057 979 564 419 991 961 345 637 080 391 063 343 278 659 875 006 722 945 435 258 511 750 736 395 209 297 602 991 695 886 580 794 249 759 902 536 380 055 710 080 977 728 337 952 498 718 259 606 078 790 355 738 625 858 597 516 649 364 990 083 397 742 948 406 390 695 711 840 139 170 928 984 527 396 432 236 103 181 667 418 006 635 667 189 873 871 634 905 950 683 958 299 923 219 653 264 060 399 588 571 782 767 511 747 924 043 969 623 045 308 763 567 170 166 295 093 013 227 497 346 173 854 101 964 306 147 690 034 349 284 712 163 842 269 859 435 320 408 715 901 523 168 064 489 459 605 434 861 066 611 056 209 626 985 578 507 010 825 633 753 454 <math>\approx 10^{2901.92}</math>

[[Category:Cryptids]]

User talk:MrSolis

2025-04-22T11:38:19Z

Racheline: /* Deleting large amounts of content */ new section

== Antihydra ==
Hi, I rolled back your recent change to [[Antihydra]] because it seems like you removed a ton of content there. Feel free to add your proofs if you'd like, but no need to remove the transition table and so much of the description. [[User:Sligocki|Sligocki]] ([[User talk:Sligocki|talk]]) 03:35, 17 February 2025 (UTC)
== Explaining Myself ==
[[User:Sligocki|Sligocki]]
Hello,

I appreciate your criticisms of the changes I have made to one of your pages. I would like to explain my thought process behind the changes so that we may come to an agreement on what should and should not be changed. I will review each section of your article to explain why I did what I did.

1. The lead section: I wanted to be brief. Perhaps I was being too brief.

2. Turing Machine: ''No'' other individual Turing Machine page has a transition ''table'', only its inline form. If you look at the pages for the 5-state busy beaver winner and Hydra, the other two TM pages that I have made significant changes to, you can infer that I intend for these to be the ''final'' (or semi-final, for unsolved machines) versions of these pages. That means I want consistency across every individual Turing Machine page and a clear structure. If you prefer that I not edit the table out, let me know so that I can add one to the 5-state busy beaver winner and Hydra (and any other TM pages I decide to modify) pages. I also omitted the names mxdys and Racheline in my version. Is that a problem? I did not think that was a problem because I had cited your blog post where they ''are'' mentioned. If it is a problem, I will not omit their names in my second edit to the page.

3. Analysis: You will notice that I did not use the preferred and more useful rules in my version. That is intentional. I noticed that the page "Hydra function" just says "The Hydra function is Collatz-like function whose behavior is connected to the the unsolved halting problems for the Cryptids Hydra and Antihydra". Aside from the obvious grammatical errors, this article does not explain ''how'' the function H(n) = floor((3*n)/2) is connected to Hydra and Antihydra except for the name, which feels circular. It also does not explain why that matters. After Antihydra, I was planning on changing that article so that these questions could be answered.

4. Biased Random Walk: I have two separate points on why I changed it.

The first and more important one, is that the probability analysis is simply '''incorrect.''' The probability of the random walker ''b'' going down from ''n'' to -1 is '''not''' (1/2)^(n+1). The simple argument for why is that (1/2)^(n+1) is the probability that the random coin lands on the same face n+1 times ''in a row''. Consider the situation where ''b'' = 5, and you are given a coin to flip. It if lands on heads, ''b'' increases by 2; if tails, decreases by 1. If you had to get ''b'' to -1 without getting heads a single time, then the probability ''would'' be (1/2)^6 (assuming independent random flips where heads and tails each have a 1/2 probability). However, if you just had to get b to -1 you could still win if you get heads on your first flip and then get eight tails in a row. You could win even if ''b'' rose to 10^(20) if you are lucky enough. These situations are not very likely to happen, but they make a non-zero difference.

My second point is that I did not entirely remove this section from the wiki; I had ''moved'' it to the Hydra page in the Trajectory section and corrected it, along with giving a proof for why my analysis is true there. I did not want to include basically the same thing in two separate pages, so in my Antihydra edit I basically just said "read the Hydra article".

If you still do not believe me when I say that (1/2)^(n+1) is incorrect, I would like you to make and run a program based on this pseudocode:

<pre>
trials = [some large integer]
fakeInfinity = [some other large integer]

integer reachedMinusOneCount = 0
integer startingValue = 1 // THIS IS N

for (integer i = 0; i < trials; i++)
integer walk = startingValue

while(walk > -1 AND walk < fakeInfinity)
integer flip = [either 0 or 1, chosen randomly]
if (flip equals 0)
walk = walk - 1 // Getting a 0 is tails here
else
walk = walk + 2 // Getting a 1 is heads here

if (walk equals -1)
increment reachedMinusOneCount

probability = (reachedMinusOneCount)/(trials)
output(probability)</pre>
If you alter startingValue and run the program, you will find that probability is greater than (1/2)^(n+1) and closer to what I got.

5. Simulation: I included the part where after 2^(31) rule steps we have b = 1073720884 in my Trajectory section. I thought that if the average uninformed reader was curious about the "20940 (0.002%)" error, they could check for themselves, so I removed that part. Again, the same problematic (1/2)^(n+1) probability shows up, which I saw no issue with removing.

I sincerely apologize for making drastic changes to your article and not elaborating on why before I did that. I would like for you to respond with what precisely I did wrong so that I do not make unwanted changes in the future.
[[User:MrSolis|MrSolis]] ([[User talk:MrSolis|talk]]) 15:30, 17 February 2025 (UTC)

: Thanks for your efforts in improving the wiki! Are you on the discord server? It might be easier to discuss wiki changes there since that's where most people are active. [[User:Peacemaker II|Peacemaker II]] ([[User talk:Peacemaker II|talk]]) 17:00, 17 February 2025 (UTC)

::[[User:Peacemaker II]], No, I am simply curious as to exactly where I went too far. [[User:MrSolis|MrSolis]] ([[User talk:MrSolis|talk]]) 17:05, 17 February 2025 (UTC)

::: Personally, I liked how the previous version of the article followed Shawn's blog post, which I think is a good explanation of the machine for most readers. Good job on writing down proofs, but I think the majority of readers will only be interested in the high level rules, not a detailed explanation of the Turing machine behavior. Adequately explaining the Turing machine behavior can be cumbersome and readers can get easily lost with the details. IMO, there is little gain in understanding the derivation rather than just knowing the high-level rules. Perhaps we can find another place for the detailed proofs? If you want to discuss further, it'll be easier to talk on the discord server: https://discord.com/invite/3uqtPJA9Uv [[User:Peacemaker II|Peacemaker II]] ([[User talk:Peacemaker II|talk]]) 17:19, 17 February 2025 (UTC)

: Hi [[User:MrSolis|MrSolis]], I also want to thank you for contributing to the wiki! I think many of your changes sound great to me, I just want to talk through it a bit :)
:
: First of all: Your comments about the halting probability are 100% correct. Thank you! I updated my blog post on Hydra today to fix that! (as well as the wiki Antihydra page).
:
: Broadly speaking, I think my preference is that people add content boldly and remove content sparingly and perhaps with a bit more discussion (say on the talk pages). I had expanded [[Antihydra]] at some point in the past to its current state and was very proud of it. I'm certainly open to the idea that there is too much detail (or redundancy), but I think it should only be removed with care.
:
: Regarding TM page cohesiveness, I can generally see the value in making these pages a bit more standard, but also don't feel like it's the most important. If we had infinite time and effort, I think I'd like to have a fully written out transition table, narrative description and attribution on every TM page. At one point I tried to create a template to automatically convert a TM string into a transition table ... but I could not figure out how to do it ... if you have any experience, that would be lovely to have! and would make it much easier to include on all TM pages.
:
: So, in conclusion, I would be glad if you wanted to add a section where you prove the Antihydra transition rules. Given the size of the proof and the fact that many people might be coming to this page to read about Antihydra, I think that could either go at the end or in a collapsible div or something like that. Likewise, I'm reasonably happy if you want to move some of these things to a centralized location (on [[Antihydra]], [[Hydra]] or [[Hydra function]]). In this case, although Hydra is the original TM like this, I think it might actually make a bit more sense to have Antihydra be the main article with most of the content since it seems to be of much broader interest (being in the standard 2-symbol BB variation). [[User:Sligocki|Sligocki]] ([[User talk:Sligocki|talk]]) 21:39, 17 February 2025 (UTC)

== Deleting large amounts of content ==

Please stop. I'm not sure which part of "preferably outside of this page" was unclear, so you can use this talk page to ask about the details of what i meant and maybe i can clarify, but for now, leave lucy's moonlight alone. please.
 You can talk about the reasons for your edits here, but do it before editing the page. I agree with the consensus that information should be added, not removed. If harm is not your intention, then please try to learn how to not remove content. I'm not sure how to help with that because i don't understand what causes you to remove it in the first place (and honestly i just don't have time for this), but i'm sure you can find someone who can help you if you need that. [[User:Racheline|Racheline]] ([[User talk:Racheline|talk]]) 11:38, 22 April 2025 (UTC)

Lucy's Moonlight

2025-04-21T22:46:41Z

Racheline: reverting to a stable version until the mess is resolved (preferably outside of this page)

Busy Beaver for lambda calculus

2025-04-11T09:15:36Z

Racheline: updated champions from 40 to 48

'''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. If you are not familiar with lambda calculus and beta-reduction, I recommend starting with that article.

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.

== Analogy to Turing machines ==
We evaluate terms by applying ''beta-reductions'' until they reach a ''normal form''. As an analogy to [[Turing machines]]:
* ''Lambda terms'' are like TM configurations (tape + state + position).
* Applying ''beta-reduction'' to a term is like taking a TM step.
* A term is in ''normal form'' if no beta-reductions can be applied. This is like saying the term has halted.
* A term may or may not be reducible to a normal form. If it is, this is like saying the term halts.
* Determining whether a term is reducible to a normal form is an undecidable problem equivalent to the halting problem.

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.

== Binary Lambda Encoding ==
A lambda term using [https://en.wikipedia.org/wiki/De_Bruijn_indices De Bruijn indexes] is defined inductively as:
* 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>.
* 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>.
* 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>.

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.

Encoding (''blc()'') is defined recursively:
<math display="block">\begin{array}{l}
blc(Var(n)) & = & 1^n 0 \\
blc(Lam(T)) & = & 00 \; blc(T) \\
blc(App(T, U)) & = & 01 \; blc(T) \; blc(U) \\
\end{array}</math>

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.

== Text Encoding conventions ==
For human readability, a text encoding and set of conventions is used in this article. As described earlier we encode a lambda term as:
* Var(''n'') -> <code>n</code>
* Lam(''T'') -> <code>(\T)</code>
* App(''T, U'') -> <code>(T U)</code>

However, parentheses are also dropped in certain cases by convention:
* The outermost parentheses are dropped: <code>Lam(1)</code> -> <code>\1</code> and <code>App(1, 2)</code> -> <code>1 2</code>.
* 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>.
* 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>).

This is the convention used in John Tromp's code and so is used here for consistency.

== Champions ==
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.

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

{| class="wikitable"
|+
!n
!BBλ(n)
!Champion
!# Beta reductions
!Normal form
!Discovered By
|-
|21 || = 22 || <code>\(\1 1) (1 (\2))</code>
|1|| <code>\(1 (\2)) (1 (\2))</code> || John Tromp & Bertram Felgenhauer
|-
|22 || = 24 || <code>\(\1 1) (1 (\\1))</code>
|1|| <code>\(1 (\\1)) (1 (\\1))</code> ||Shawn Ligocki
|-
| || || <code>\(\1 1 1) (1 1)</code>
|1|| <code>\(1 1) (1 1) (1 1)</code> || John Tromp & Bertram Felgenhauer
|-
|23 || = 26 || <code>\(\1 1) (1 (\\2))</code>
|1|| <code>\(1 (\\2)) (1 (\\2))</code> || John Tromp & Bertram Felgenhauer
|-
|24 || = 30 || <code>\(\1 1 1) (1 (\1))</code>
|1|| <code>\(1 (\1)) (1 (\1)) (1 (\1))</code> || John Tromp & Bertram Felgenhauer
|-
|25 || = 42 || <code>\(\1 1) (\1 (2 1))</code>
|3|| <code>\1 (\1 (2 1)) (1 (1 (\1 (2 1))))</code> || John Tromp & Bertram Felgenhauer
|-
|26 || = 52 || <code>(\1 1) (\\2 (1 2))</code>
|3|| <code>\\2 (\\2 (1 2)) (1 (2 (\\2 (1 2))))</code> || John Tromp & Bertram Felgenhauer
|-
|27 || = 44 || <code>\\(\1 1) (\1 (2 1))</code>
|3|| <code>\\1 (\1 (2 1)) (1 (1 (\1 (2 1))))</code> || John Tromp & Bertram Felgenhauer
|-
|28 || = 58 || <code>\(\1 1) (\1 (2 (\2))))</code>
|3|| <code>\1 (\\1 (3 (\2))) (1 (\2 (\\1 (4 (\2)))))</code>|| John Tromp & Bertram Felgenhauer
|-
| 29 || = 223|| <code>\(\1 1) (\1 (1 (2 1)))</code>
|4|| <pre>
\B (B (1 B))
where:
B = (A (A (1 A)))
A = (1 (\1 (1 (2 1))))
</pre>||John Tromp & Bertram Felgenhauer
|-
|30
|= 160
|<code>(\1 1 1) (\\2 (1 2))</code>
|7
|<pre>
\\2 B A (1 (2 B A))
where:
B = (\\2 A (1 (2 A)))
A = (\\2 (1 2))
</pre>
|John Tromp & Bertram Felgenhauer
|-
|
|
|<code>(\1 (1 1)) (\\2 (1 2))</code>
|5
|Same as above
|Shawn Ligocki
|-
|31
|= 267
|<code>(\1 1) (\\2 (2 (1 2)))</code>
|6
|<pre>
\\2 A (2 A (C (2 A)))
where:
C = (2 A (2 A (1 B (2 A))))
B = (\3 A (3 A (1 (3 A))))
A = (\\2 (2 (1 2)))
</pre>
|John Tromp & Bertram Felgenhauer
|-
|32
|= 298
|<code>\(\1 1) (\1 (1 (2 (\2))))</code>
|
|
|John Tromp & Bertram Felgenhauer
|-
|33
|= 1812
|<code>\(\1 1) (\1 (1 (1 (2 1))))</code>
|5
|<pre>
\C (C (C (1 C)))
where:
C = (B (B (B (1 B)))
B = (A (A (A (1 A)))
A = (1 (\1 (1 (1 (2 1)))))
</pre>
|John Tromp & Bertram Felgenhauer
|-
|34 || <math>= \ 5 \left(2^{2^{2^2}}\right) + 6 = 327\,686</math>
| <code>(\1 1 1 1) (\\2 (2 1))</code>
| || <math>C(2^{2^{2^2}})</math> || John Tromp & Bertram Felgenhauer
|-
|35 || <math>\ge 5 \left(3^{3^3}\right) + 6 > 3.8 \times 10^{13}</math>
| <code>(\1 1 1) (\\2 (2 (2 1)))</code>
| || <math>C(3^{3^3})</math> || John Tromp & Bertram Felgenhauer
|-
|36 || <math>\ge 5 \left(2^{2^{2^3}}\right) + 6 > 5.7 \times 10^{77}</math>
| <code>(\1 1) (\1 (1 (\\2 (2 1))))</code>
| || <math>C(2^{2^{2^3}})</math>|| John Tromp & Bertram Felgenhauer
|-
|37 ||
|
| || ||
|-
|38 || <math>\ge 5 \left(2^{2^{2^{2^2}}}\right) + 6 > 10^{10^4}</math>
| <code>(\1 1 1 1 1) (\\2 (2 1))</code>
| || <math>C(2^{2^{2^{2^2}}})</math> || John Tromp & Bertram Felgenhauer
|-
|39 || <math>\ge 5 \left(3^{3^{3^3}}\right) + 6 > 10^{10^{12}}</math>
| <code>(\1 1 1 1) (\\2 (2 (2 1)))</code>
| || <math>C(3^{3^{3^3}})</math> || John Tromp & Bertram Felgenhauer
|-
|40 || <math> > (2\uparrow\uparrow)^{15} 33 > 10 \uparrow\uparrow\uparrow 16</math>
| <code>(\1 1 1) (\1 (\\2 (2 1)) 1)</code>
| || <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
|-
|41 ||
|
| || ||
|-
|42 ||
|
| || ||
|-
|43 ||
|
| || ||
|-
|44 || <math> > 10 \uparrow\uparrow\uparrow 10 \uparrow\uparrow\uparrow 16</math>
| <code>(\1 1 1 1) (\1 (\\2 (2 1)) 1)</code>
| || <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> ||
|-
|45 || <math> > 3 \uparrow\uparrow\uparrow (3 \uparrow\uparrow 3) > 10 \uparrow\uparrow\uparrow (7.6 \times 10^{12})</math>
| <code>(\1 1 1) (\1 (\\2 (2 (2 1))) 1)</code>
| || <math>\lambda x.T(k)</math> where <math>T(0)=x,\;T(n+1)=T(n)\;C(3)\;T(n)</math> and <math>k > 3 \uparrow\uparrow\uparrow (3 \uparrow\uparrow 3)</math> ||
|-
|46 ||
|
| || ||
|-
|47 ||
|
| || ||
|-
|48 || <math> > 10 \uparrow\uparrow\uparrow 10 \uparrow\uparrow\uparrow 10 \uparrow\uparrow\uparrow 16</math>
| <code>(\1 1 1 1 1) (\1 (\\2 (2 1)) 1)</code>
| || <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> ||
|-
|49
|<math>> f_{\omega+1}\left(\frac{2 \uparrow\uparrow 6}{2}\right) > \text{Graham's number}</math>
|<code>(\1 1) (\1 (1 (\\1 2 (\\2 (2 1)))))</code>
|
|<math>C(N) \text{ for } N \approx f_{\omega+1}\left(\frac{2 \uparrow\uparrow 6}{2}\right)</math>
|[https://github.com/tromp/AIT/blob/master/fast_growing_and_conjectures/melo.lam Gustavo Melo]
|-
|...
|
|
|
|
|
|-
|1850
|> Loader's number
|<code>too large to show</code>
|
|
|[https://codegolf.stackexchange.com/questions/176966/golf-a-number-bigger-than-loaders-number/274634#274634 John Tromp]
|}

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.

== See Also ==

* https://oeis.org/A333479
* [https://tromp.github.io/blog/2023/11/24/largest-number The largest number representable in 64 bits]. 24 Nov 2023. John Tromp.
* [https://tromp.github.io/cl/Binary_lambda_calculus.html Binary Lambda Calculus]. John Tromp.
* https://github.com/tromp/AIT/tree/master/BB

Busy Beaver for lambda calculus

2025-03-29T11:36:24Z

Racheline: added some more values, fixed bounds, and removed my name because i dont feel comfortable being credited for trivial things like that. also since the 37 row is empty, i don't understand what it would mean to credit someone for it, so maybe we should remove that too?

'''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. If you are not familiar with lambda calculus and beta-reduction, I recommend starting with that article.

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.

== Analogy to Turing machines ==
We evaluate terms by applying ''beta-reductions'' until they reach a ''normal form''. As an analogy to [[Turing machines]]:
* ''Lambda terms'' are like TM configurations (tape + state + position).
* Applying ''beta-reduction'' to a term is like taking a TM step.
* A term is in ''normal form'' if no beta-reductions can be applied. This is like saying the term has halted.
* A term may or may not be reducible to a normal form. If it is, this is like saying the term halts.
* Determining whether a term is reducible to a normal form is an undecidable problem equivalent to the halting problem.

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.

== Binary Lambda Encoding ==
A lambda term using [https://en.wikipedia.org/wiki/De_Bruijn_indices De Bruijn indexes] is defined inductively as:
* 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>.
* 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>.
* 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>.

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.

Encoding (''blc()'') is defined recursively:
<math display="block">\begin{array}{l}
blc(Var(n)) & = & 1^n 0 \\
blc(Lam(T)) & = & 00 \; blc(T) \\
blc(App(T, U)) & = & 01 \; blc(T) \; blc(U) \\
\end{array}</math>

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.

== Text Encoding conventions ==
For human readability, a text encoding and set of conventions is used in this article. As described earlier we encode a lambda term as:
* Var(''n'') -> <code>n</code>
* Lam(''T'') -> <code>(\T)</code>
* App(''T, U'') -> <code>(T U)</code>

However, parentheses are also dropped in certain cases by convention:
* The outermost parentheses are dropped: <code>Lam(1)</code> -> <code>\1</code> and <code>App(1, 2)</code> -> <code>1 2</code>.
* 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>.
* 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>).

This is the convention used in John Tromp's code and so is used here for consistency.

== Champions ==
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.

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

{| class="wikitable"
|+
!n
!BBλ(n)
!Champion
!Normal form
!Discovered By
|-
|21 || = 22 || <code>(\1 1) (1 (\2))</code> || <code>(1 (\2)) (1 (\2))</code> || John Tromp & Bertram Felgenhauer
|-
|22 || = 24 || <code>(\1 1) (1 (\\1))</code> || <code>(1 (\\1)) (1 (\\1))</code> || John Tromp & Bertram Felgenhauer
|-
| || || <code>(\1 1 1) (1 1)</code> || <code>(1 1) (1 1) (1 1)</code> || John Tromp & Bertram Felgenhauer
|-
|23 || = 26 || <code>(\1 1) (1 (\\2))</code> || <code>(1 (\\2)) (1 (\\2))</code> || John Tromp & Bertram Felgenhauer
|-
|24 || = 30 || <code>(\1 1 1) (1 (\1))</code> || <code>(1 (\1)) (1 (\1)) (1 (\1))</code> || John Tromp & Bertram Felgenhauer
|-
|25 || = 42 || <code>\(\1 1) (\1 (2 1))</code> || <code>\1 (\1 (2 1)) (1 (1 (\1 (2 1))))</code> || John Tromp & Bertram Felgenhauer
|-
|26 || = 52 || <code>(\1 1) (\\2 (1 2))</code> || <code>\\2 (\\2 (1 2)) (1 (2 (\\2 (1 2))))</code> || John Tromp & Bertram Felgenhauer
|-
|27 || = 44 || <code>\\(\1 1) (\1 (2 1))</code> || <code>\\1 (\1 (2 1)) (1 (1 (\1 (2 1))))</code> || John Tromp & Bertram Felgenhauer
|-
|28 || = 58 || <code>\(\1 1) (\1 (2 (\2))))</code> || || John Tromp & Bertram Felgenhauer
|-
| 29 || = 223|| <code>\(\1 1) (\1 (1 (2 1)))</code>|| ||John Tromp & Bertram Felgenhauer
|-
|30
|= 160
|<code>(\1 1 1) (\\2 (1 2))</code>
|
|John Tromp & Bertram Felgenhauer
|-
|31
|≥ 267
|<code>(\1 1) (\\2 (2 (1 2)))</code>
|
|John Tromp & Bertram Felgenhauer
|-
|32
|≥ 298
|<code>\(\1 1) (\1 (1 (2 (\2))))</code>
|
|John Tromp & Bertram Felgenhauer
|-
|33
|≥ 1812
|<code>\(\1 1) (\1 (1 (1 (2 1))))</code>
|
|John Tromp & Bertram Felgenhauer
|-
|34 || <math>\ge 5 \left(2^{2^{2^2}}\right) + 6 = 327\,686</math>
| <code>(\1 1 1 1) (\\2 (2 1))</code> || <math>C(2^{2^{2^2}})</math> || John Tromp & Bertram Felgenhauer
|-
|35 || <math>\ge 5 \left(3^{3^3}\right) + 6 > 3.8 \times 10^{13}</math>
| <code>(\1 1 1) (\\2 (2 (2 1)))</code> || <math>C(3^{3^3})</math> || John Tromp & Bertram Felgenhauer
|-
|36 || <math>\ge 5 \left(2^{2^{2^3}}\right) + 6 > 5.7 \times 10^{77}</math>
| <code>(\1 1 1 1) (\\2 (2 1))</code> || <math>C(2^{2^{2^2}})</math> || John Tromp & Bertram Felgenhauer
|-
|37 ||
| || || John Tromp & Bertram Felgenhauer
|-
|38 || <math>\ge 5 \left(2^{2^{2^{2^2}}}\right) + 6 > 10^{10^4}</math>
| <code>(\1 1 1 1 1) (\\2 (2 1))</code> || <math>C(2^{2^{2^{2^2}}})</math> || John Tromp & Bertram Felgenhauer
|-
|39 || <math>\ge 5 \left(3^{3^{3^3}}\right) + 6 > 10^{10^{12}}</math>
| <code>(\1 1 1 1) (\\2 (2 (2 1)))</code> || <math>C(3^{3^{3^3}})</math> || John Tromp & Bertram Felgenhauer
|-
|40 || <math> > 5 \left(2^{2^{2059}}\right) + 6 > 10^{10^{619}}</math>
| <code>(\1 1 (\1 1) 1) (\\2 (2 1))</code> || <math>C(2^{2^{2059}})</math> ||
|-
|41 ||
| || ||
|-
|42 || <math>\ge 5 \left(2 \uparrow\uparrow 6\right) + 6 > 10^{10^{10^4}}</math>
| <code>(\1 1 1 1 1 1) (\\2 (2 1))</code> || <math>C(2 \uparrow\uparrow 6)</math> ||
|-
|43 || <math>\ge 5 \left(3 \uparrow\uparrow 5\right) + 6 > 10^{10^{10^{12}}}</math>
| <code>(\1 1 1 1 1) (\\2 (2 (2 1)))</code> || <math>C(3 \uparrow\uparrow 5)</math> ||
|-
|44 || <math> > (2\uparrow)^{14} 2059 > 10 \uparrow\uparrow 15</math>
| <code>(\1 1 1 (\1 1) 1) (\\2 (2 1))</code> || <math>C((\lambda x.x^x)^{16}(2))</math> ||
|-
|45 || <math> > 3 \uparrow\uparrow 28 > 10 \uparrow\uparrow 27</math>
| <code>(\1 1 (\1 1) 1) (\\2 (2 (2 1)))</code> || <math>C((\lambda x.x^x)^{27}(3))</math> ||
|-
|46 || <math> > 256 \uparrow\uparrow 257 > 10 \uparrow\uparrow 257</math>
| <code>(\1 (\1 (\1 1) 1) 1) (\\2 (2 1))</code> || <math>C((\lambda x.x^x)^{256}(256))</math> ||
|-
|47 ||
| || ||
|-
|48 || <math> > (2\uparrow)^{65534} 2059 > 10 \uparrow\uparrow 65535</math>
| <code>(\1 1 1 1 (\1 1) 1) (\\2 (2 1))</code> || <math>C((\lambda x.x^x)^{65536}(2))</math> ||
|-
|49
|> Graham's number
|<code>(\1 1) (\1 (1 (\\1 2 (\\2 (2 1)))))</code>
|
|[https://codegolf.stackexchange.com/questions/6430/shortest-terminating-program-whose-output-size-exceeds-grahams-number/219734#comment533337_219734 Patcail & 2014MELO03]
|-
|...
|
|
|
|
|-
|1850
|> Loader's number
|<code>too large to show</code>
|
|[https://codegolf.stackexchange.com/questions/176966/golf-a-number-bigger-than-loaders-number/274634#274634 John Tromp]
|}

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.

== See Also ==

* https://oeis.org/A333479
* [https://tromp.github.io/blog/2023/11/24/largest-number The largest number representable in 64 bits]. 24 Nov 2023. John Tromp.
* [https://tromp.github.io/cl/Binary_lambda_calculus.html Binary Lambda Calculus]. John Tromp.
* https://github.com/tromp/AIT/tree/master/BB

Lucy's Moonlight

2025-03-06T09:29:26Z

Racheline: updated analysis

Lucy's Moonlight

2025-03-06T09:08:46Z

Racheline:

Lucy's Moonlight

2025-03-06T09:07:48Z

Racheline: fixed newline

{{machine|1RB0RD_0RC1RE_1RD0LA_1LE1LC_1RF0LD_---0RA}}{{TM|1RB0RD_0RC1RE_1RD0LA_1LE1LC_1RF0LD_---0RA}}

Lucy's Moonlight is a [[probviously]] halting tetrational [[BB(6)]] [[Cryptid]] found by Racheline on 1 Mar 2025 ([https://discord.com/channels/960643023006490684/1239205785913790465/1345551751016878272 Discord link]).

== Analysis by Racheline ==
https://discord.com/channels/960643023006490684/1345810396136865822/1345820781363597312<pre>
A(x,y) := 0^inf (1011)^x 10 <A (01)^y 0^inf
B(x) := 0^inf 1^x B> 0^inf

A(x+1,3y) -> A(x,8y+3)
A(x+2,3y+1) -> A(x,8y+11)
A(x+2,3y+2) -> A(x,8y+12)
A(0,y) -> B(2y+1)
A(1,3y+1) -> A(4y+4,4)
A(1,3y+2) -> halt
B(3y) -> B(8y-2)
B(3y+1) -> A(2y,4)
B(3y+2) -> B(8y+6)

a is the sequence such that A(x,a_n) goes to A(x',a_(n+1)) in one step assuming x>=2
b is the sequence such that A(x,a_0) goes to A(x-b_n,a_n) in n rules (without using the A(0,y) or A(1,y) rules) assuming x>=b_n
c is the sequence such that A(c_n,a_0) goes to A(c_(n+1),a_0) after only one application of the A(0,y) or A(1,y) rules

f(3n) = 8n+3
f(3n+1) = 8n+11
f(3n+2) = 8n+12
a_0 = 4
a_(n+1) = f(a_n)
b_0 = 0
b_(n+1) = b_n+(1 if 3|a_n else 2)
c_0 = 14
c_(n+1) = idk i'll finish this later but it's somewhere around a_(largest i such that b_i<=c_n)
</pre>

[[Category:Cryptids]]

Lucy's Moonlight

2025-03-06T09:07:29Z

Racheline:

{{machine|1RB0RD_0RC1RE_1RD0LA_1LE1LC_1RF0LD_---0RA}}{{TM|1RB0RD_0RC1RE_1RD0LA_1LE1LC_1RF0LD_---0RA}}
Lucy's Moonlight is a [[probviously]] halting tetrational [[BB(6)]] [[Cryptid]] found by Racheline on 1 Mar 2025 ([https://discord.com/channels/960643023006490684/1239205785913790465/1345551751016878272 Discord link]).

== Analysis by Racheline ==
https://discord.com/channels/960643023006490684/1345810396136865822/1345820781363597312<pre>
A(x,y) := 0^inf (1011)^x 10 <A (01)^y 0^inf
B(x) := 0^inf 1^x B> 0^inf

A(x+1,3y) -> A(x,8y+3)
A(x+2,3y+1) -> A(x,8y+11)
A(x+2,3y+2) -> A(x,8y+12)
A(0,y) -> B(2y+1)
A(1,3y+1) -> A(4y+4,4)
A(1,3y+2) -> halt
B(3y) -> B(8y-2)
B(3y+1) -> A(2y,4)
B(3y+2) -> B(8y+6)

a is the sequence such that A(x,a_n) goes to A(x',a_(n+1)) in one step assuming x>=2
b is the sequence such that A(x,a_0) goes to A(x-b_n,a_n) in n rules (without using the A(0,y) or A(1,y) rules) assuming x>=b_n
c is the sequence such that A(c_n,a_0) goes to A(c_(n+1),a_0) after only one application of the A(0,y) or A(1,y) rules

f(3n) = 8n+3
f(3n+1) = 8n+11
f(3n+2) = 8n+12
a_0 = 4
a_(n+1) = f(a_n)
b_0 = 0
b_(n+1) = b_n+(1 if 3|a_n else 2)
c_0 = 14
c_(n+1) = idk i'll finish this later but it's somewhere around a_(largest i such that b_i<=c_n)
</pre>

[[Category:Cryptids]]

1RB0RD 0RC1RE 1RD0LA 1LE1LC 1RF0LD ---0RA

2025-03-06T09:04:12Z

Racheline: Racheline moved page 1RB0RD 0RC1RE 1RD0LA 1LE1LC 1RF0LD ---0RA to Lucy's Moonlight: it got named

#REDIRECT [[Lucy's Moonlight]]

Lucy's Moonlight

2025-03-06T09:04:12Z

Racheline: Racheline moved page 1RB0RD 0RC1RE 1RD0LA 1LE1LC 1RF0LD ---0RA to Lucy's Moonlight: it got named

{{machine|1RB0RD_0RC1RE_1RD0LA_1LE1LC_1RF0LD_---0RA}}
{{TM|1RB0RD_0RC1RE_1RD0LA_1LE1LC_1RF0LD_---0RA}} is a [[probviously]] halting tetrational [[BB(6)]] [[Cryptid]] found by Racheline on 1 Mar 2025 ([https://discord.com/channels/960643023006490684/1239205785913790465/1345551751016878272 Discord link]).

== Analysis by Racheline ==
https://discord.com/channels/960643023006490684/1345810396136865822/1345820781363597312<pre>
A(x,y) := 0^inf (1011)^x 10 <A (01)^y 0^inf
B(x) := 0^inf 1^x B> 0^inf

A(x+1,3y) -> A(x,8y+3)
A(x+2,3y+1) -> A(x,8y+11)
A(x+2,3y+2) -> A(x,8y+12)
A(0,y) -> B(2y+1)
A(1,3y+1) -> A(4y+4,4)
A(1,3y+2) -> halt
B(3y) -> B(8y-2)
B(3y+1) -> A(2y,4)
B(3y+2) -> B(8y+6)

a is the sequence such that A(x,a_n) goes to A(x',a_(n+1)) in one step assuming x>=2
b is the sequence such that A(x,a_0) goes to A(x-b_n,a_n) in n rules (without using the A(0,y) or A(1,y) rules) assuming x>=b_n
c is the sequence such that A(c_n,a_0) goes to A(c_(n+1),a_0) after only one application of the A(0,y) or A(1,y) rules

f(3n) = 8n+3
f(3n+1) = 8n+11
f(3n+2) = 8n+12
a_0 = 4
a_(n+1) = f(a_n)
b_0 = 0
b_(n+1) = b_n+(1 if 3|a_n else 2)
c_0 = 14
c_(n+1) = idk i'll finish this later but it's somewhere around a_(largest i such that b_i<=c_n)
</pre>

[[Category:Cryptids]]

Antihydra

2025-03-05T11:29:09Z

Racheline: added source for etymology to prevent people from unnecessarily reverting the previous edit for lack of certainty

{{machine|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA}}{{unsolved|Does Antihydra run forever?}}{{TM|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA|undecided}}
[[File:Antihydra-depiction.png|right|thumb|200px|Artistic depiction of Antihydra by Jadeix]]
'''Antihydra''' is the first [[BB(6)]] [[Cryptid]] to be identified. It operates by repeatedly applying the function <math display="inline">H(n)=\Big\lfloor\frac{3}{2}n\Big\rfloor</math>, starting with <math>n=8</math>. Determining whether this [[Turing machine]] halts requires solving a [[Collatz-like ]] mathematical problem. Specifically, one must establish a significant result regarding the frequency of odd versus even numbers generated throughout the sequence. While probabilistic arguments based on random walks suggest Antihydra [[probviously]] runs indefinitely, proving this remains challenging. The difficulty stems from both the lack of an exploitable pattern in the sequence’s parities and the inherent complexity of Collatz-like problems.
== Description ==
[[File:Antihydra TransitionTable.png|right|150px|thumb|The transition table of Antihydra.]]
Antihydra basically repeatedly modifies the integer ordered pair <math>(x,y)</math> starting at <math>(0,4)</math>, which is represented on the tape as <math>x</math> consecutive <math>1</math>s and <math>y</math> consecutive <math>1</math>s, separated by a single <math>0</math>. It does this by "borrowing" a <math>0</math> from the right side and, through a series of back-and-forth head movements, "moves" this <math>0</math> toward the one separating <math>x</math> and <math>y</math>, two units at a time. As this happens, the head visits new cells on the right, which has the effect of there being about <math display="inline">\frac{3}{2}</math> times as many <math>1</math>s on the tape when the distance has been closed. After that, <math>x</math> and <math>y</math> are updated. If the previous value of <math>x</math> was even, then <math>y</math> becomes <math>y+2</math>. Otherwise, <math>y</math> becomes <math>y-1</math> or Antihydra halts if <math>y</math> was 0.

Let <math display="inline">H(n)=\Big\lfloor\frac{3}{2}n\Big\rfloor</math>, and <math>a_k</math> and <math>b_k</math> be integer sequences defined below:
<math display="block">\begin{array}{l}
a_0=0,&a_{k+1} = \begin{cases}a_k + 2 & \text{if } b_k\equiv0\pmod{2}\\a_k - 1 & \text{if }b_k\equiv1\pmod{2} \\\end{cases},&b_0=8,&b_{k+1}=H(b_k).\end{array}</math>
Antihydra halts if and only if there exists any number <math>i</math> for which <math>a_i<0</math>.
=== Attributions ===
Antihydra and its pseudo-random behaviour were reported [https://discord.com/channels/960643023006490684/1026577255754903572/1256223215206924318 on Discord] by mxdys on 28 June 2024, and Racheline discovered the high-level rules soon after, where it was found to be closely related to [[Hydra]]. The "anti-" in the name is due to the fact that the roles of even and odd numbers are switched compared to the behavior of Hydra <ref>[https://discord.com/channels/960643023006490684/960643023530762341/1257053002859286701 Discord conversation where the machine was named]</ref>.

== Analysis ==
Let <math>A(a,b):=0^\infty\;1^a\;0\;1^b\;\textrm{E>}\;0^\infty</math>. Then,<ref name="bl">S. Ligocki, "[https://www.sligocki.com/2024/07/06/bb-6-2-is-hard.html BB(6) is Hard (Antihydra)]" (2024). Accessed 22 July 2024.</ref>
<math display="block">\begin{array}{|lll|}\hline
A(a,2b)& \xrightarrow{2a+3b^2+12b+11}& A(a+2,3b+2),\\
A(0,2b+1)&\xrightarrow{3b^2+9b-1}& 0^\infty\;\textrm{<F}\;110\;1^{3b}\;0^\infty,\\
A(a+1,2b+1)&\xrightarrow{3b^2+12b+5}& A(a,3b+3).\\\hline
\end{array}</math>
<div class="toccolours mw-collapsible mw-collapsed">'''Proof'''<div class="mw-collapsible-content">
Consider the partial configuration <math>P(m,n):=0\;1^m\;\textrm{E>}\;0\;1^n\;0^\infty</math>. The configuration after two steps is <math>0\;1^{m-1}\;0\;\textrm{A>}\;1^{n+1}\;0^\infty</math>. We note the following shift rule:
<math display="block">\begin{array}{|c|}\hline\textrm{A>}\;1^s\xrightarrow{s}1^s\;\textrm{A>}\\\hline\end{array}</math>
As a result, we get <math>0\;1^{m-1}\;0\;1^{n+1}\;\textrm{A>}\;0^\infty</math> after <math>n+1</math> steps. Advancing two steps produces <math>0\;1^{m-1}\;0\;1^{n+2}\;\textrm{<C}\;0^\infty</math>. A second shift rule is useful here:
<math display="block">\begin{array}{|c|}\hline1^s\;\textrm{<C}\xrightarrow{s}\textrm{<C}\;1^s\\\hline\end{array}</math>
This allows us to reach <math>0\;1^{m-1}\;0\;\textrm{<C}\;1^{n+2}\;0^\infty</math> in <math>n+2</math> steps. Moving five more steps gets us to <math>0\;1^{m-2}\;\textrm{E>}\;0\;1^{n+3}\;0^\infty</math>, which is the same configuration as <math>P(m-2,n+3)</math>. Accounting for the head movement creates the condition that <math>m\ge 4</math>. In summary:
<math display="block">\begin{array}{|c|}\hline P(m,n)\xrightarrow{2n+12}P(m-2,n+3)\text{ if }m\ge 4.\\\hline\end{array}</math>
With <math>A(a,b)</math> we have <math>P(b,0)</math>. As a result, we can apply this rule <math display="inline>\big\lfloor\frac{1}{2}b\big\rfloor-1</math> times (assuming <math>b\ge 4</math>), which creates two possible scenarios:
#If <math>b\equiv0\ (\operatorname{mod}2)</math>, then in <math>\sum_{i=0}^{(b/2)-2}(2\times 3i+12)=\textstyle\frac{3}{4}b^2+\frac{3}{2}b-6</math> steps we arrive at <math display="inline">P\Big(2,\frac{3}{2}b-3\Big)</math>. The matching complete configuration is <math>0^\infty\;1^a\;011\;\textrm{E>}\;0\;1^{(3b)/2-3}\;0^\infty</math>. After <math>3b+4</math> steps this is <math>0^\infty\;1^a\;\textrm{<C}\;00\;1^{(3b)/2}\;0^\infty</math>, which then leads to <math>0^\infty\;\textrm{<C}\;1^a\;00\;1^{(3b)/2}\;0^\infty</math> in <math>a</math> steps. After five more steps, we reach <math>0^\infty\;1\;\textrm{E>}\;1^{a+2}\;00\;1^{(3b)/2}\;0^\infty</math>, from which another shift rule must be applied:<math display="block">\begin{array}{|c|}\hline\textrm{E>}\;1^s\xrightarrow{s}1^s\;\textrm{E>}\\\hline\end{array}</math>Doing so allows us to get the configuration <math>0^\infty\;1^{a+3}\;\textrm{E>}\;00\;1^{(3b)/2}\;0^\infty</math> in <math>a+2</math> steps. In six steps we have <math>0^\infty\;1^{a+2}\;011\;\textrm{E>}\;1^{(3b)/2}\;0^\infty</math>, so we use the shift rule again, ending at <math>0^\infty\;1^{a+2}\;0\;1^{(3b)/2+2}\;\textrm{E>}\;0^\infty</math>, equal to <math display="inline">A\Big(a+2,\frac{3}{2}b+2\Big)</math>, <math display="inline">\frac{3}{2}b</math> steps later. This gives a total of <math display="inline">2a+\frac{3}{4}b^2+6b+11</math> steps.
#If <math>b\equiv1\ (\operatorname{mod}2)</math>, then in <math display="inline">\frac{3}{4}b^2-\frac{27}{4}</math> steps we arrive at <math display="inline">P\Big(3,\frac{3b-9}{2}\Big)</math>. The matching complete configuration is <math>0^\infty\;1^a\;0111\;\textrm{E>}\;0\;1^{(3b-9)/2}\;0^\infty</math>. After <math>3b+2</math> steps this becomes <math>0^\infty\;1^a\;\textrm{<F}\;110\;1^{(3b-3)/2}\;0^\infty</math>. If <math>a=0</math> then we have reached the undefined <code>F0</code> transition with a total of <math display="inline">\frac{3}{4}b^2+3b-\frac{19}{4}</math> steps. Otherwise, continuing for six steps gives us <math>0^\infty\;1^{a-1}\;0111\;\textrm{E>}\;1^{(3b-3)/2}\;0^\infty</math>. We conclude with the configuration <math>0^\infty\;1^{a-1}\;0\;1^{(3b+3)/2}\;\textrm{E>}\;0^\infty</math>, equal to <math display="inline">A\Big(a-1,\frac{3b+3}{2}\Big)</math>, in <math display="inline">\frac{3b-3}{2}</math> steps. This gives a total of <math display="inline">\frac{3}{4}b^2+\frac{9}{2}b-\frac{1}{4}</math> steps.
The information above can be summarized as
<math display="block">A(a,b)\rightarrow\begin{cases}A\Big(a+2,\frac{3}{2}b+2\Big)&\text{if }b\ge 2,b\equiv0\pmod{2};\\0^\infty\;\textrm{<F}\;110\;1^{(3b-3)/2}\;0^\infty&\text{if }b\ge3,b\equiv1\pmod{2},\text{ and }a=0;\\A\Big(a-1,\frac{3b+3}{2}\Big)&\text{if }b\ge3,b\equiv1\pmod{2},\text{ and }a>0.\end{cases}</math>
Substituting <math>b\leftarrow 2b</math> for the first case and <math>b\leftarrow 2b+1</math> for the other two yields the final result.
</div></div>
The page [[Hydra function]] shows how these rules can be simplified to use that function instead, along with Hydra.
== Trajectory ==
11 steps are required to enter the configuration <math>A(0, 4)</math> before the rules are repeatedly applied. So far, Antihydra has been simulated to <math>2^{31}</math> rule steps, at which point <math>b=1073720884</math>. Here are the first few:
<math display="block">\begin{array}{|c|}\hline A(0,4)\xrightarrow{47}A(2,8)\xrightarrow{111}A(4,14)\xrightarrow{250}A(6,23)\xrightarrow{500}A(5,36)\xrightarrow{1209}A(7,56)\xrightarrow{2713}A(9,86)\rightarrow\cdots\\\hline\end{array}</math>
===A heuristic nonhalting argument===
[[File:Antihydra increasing value.png|thumb|200px|A binary representation of the first 1000 steps of the evolution of the exponentially increasing variable of the Antihydra iteration (a = a + a//2). The colored background indicates whether the value is even or odd with blue and red, respectively.]]
The trajectory of <math>b</math> values can be approximated by a random walk in which the walker can only move in step sizes +2 or -1 with equal probability, starting at position 0. If <math>P(n)</math> is the probability that the walker will reach position -1 from position <math>n</math>, then it can be seen that <math display="inline">P(n)=\frac{1}{2}P(n-1)+\frac{1}{2}P(n+2)</math>. Solutions to this recurrence relation come in the form <math display="inline"> P(n)=c_0{\left(\frac{\sqrt{5}-1}{2}\right)}^n+c_1+c_2{\left(-\frac{1+\sqrt{5}}{2}\right)}^n</math>, which after applying the appropriate boundary conditions reduces to <math display="inline">P(n)={\left(\frac{\sqrt{5}-1}{2}\right)}^{n+1}</math>. This means that if walker were to get to position 1073720884 then the probability of it ever reaching position -1 is <math display="inline">{\left(\frac{\sqrt{5}-1}{2}\right)}^{1073720885}\approx 4.841\times 10^{-224394395}</math>. This combined with the fact that the expected position of the walker after <math>k</math> steps is <math display="inline">\frac{1}{2}k</math> strongly suggests Antihydra will not halt.

''To view an animation of the blank tape becoming <math>A(6,23)</math> in 419 steps, click [https://wiki.bbchallenge.org/w/images/3/36/AHydra_0-419.gif here].''
==References==
[[Category:Individual machines]]
[[Category:Cryptids]]

Least Busy Beaver

2025-02-16T23:36:25Z

Racheline:

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.

== Definition ==
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

<math display="block">BB^-(n, m) = min_T BB_{init}(n, m, T)</math>

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.

Note that <math>BB_{init}(n, m, B) = BB(n, m)</math> where B is the blank (all-zeros) tape. Therefore,

<math display="block">BB^-(n, m) \le BB(n, m)</math>

We have not yet found an example where we can prove that <math>BB^-(n, m) \ne BB(n, m)</math>.

== Known Results ==
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>.

{| class="wikitable"
|+ Small least busy beaver values
|-
| || 2-state || 3-state || 4-state
|-
| 2-symbol
| <math>BB^-(2) = 6</math>
| <math>BB^-(3) = 21</math>
| <math>BB^-(4) = 107</math>
|-
| 3-symbol
| <math>BB^-(2, 3) = 38</math>
|
|
|}

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. 
Certificate of <math>BB^-(2, 2) = BB(2, 2) = 6</math>:<pre>
(0, 0, 0) 1RB1RZ_0LB1LA 6
(0, 0, 1) 0LB1RZ_1RA0RB 6
(0, 1, 0, 1, 0) 0RA0RB_0LB1RZ 6
(0, 1, 0, 1, 1) 0LA0LB_0RB1RZ 6
(1, 1, 0, 1, 1) 0RB1RZ_0LB0LA 7
</pre>
Certificate of <math>BB^-(3, 2) = BB(3, 2) = 21</math>:<pre>
(0, 0, 0, 0, 1) 0LB0LC_1RB1LC_1RZ1RA 21
(0, 0, 0, 1, 1) 1RB0LB_1RZ1LC_1RC1RA 22
(0, 1, 0, 1, 1) 1RB0RC_1RC0LB_0LA1RZ 21
(1, 0, 0, 0, 1) 0RA1LB_0LB0RC_1RA1RZ 23
(1, 0, 0, 1, 0) 1LA1RB_0LC0RB_0LA1RZ 23
(1, 0, 0, 1, 1) 0LB1RC_1LA1RZ_0RC0LA 21
(1, 1, 0, 1, 1) 0RB0LB_1RZ1LC_1RA0RC 21
(0, 0, 0, 0, 0, 0, 0) 1RB1RZ_1LB0RC_1LC1LA 21
(0, 0, 0, 0, 0, 0, 1) 0LB1RZ_0LC1RB_1RA0RC 24
(0, 0, 0, 0, 1, 0, 0) 0LB0RB_1RB1LC_1RZ0LA 22
(0, 0, 0, 0, 1, 0, 1) 0LB0RB_1RB1LC_1RZ0LA 22
(0, 0, 1, 0, 1, 0, 0) 0RA0RB_1LB1LC_1RA1RZ 21
(0, 0, 1, 0, 1, 0, 1) 0LA0LB_1RB1RC_1LA1RZ 21
(1, 0, 0, 0, 0, 0, 1) 0RA0LB_1LC1RZ_0LC1RA 40
(1, 0, 0, 0, 1, 0, 0) 0LA1RB_0RB0LC_1LA1RZ 24
(1, 0, 0, 0, 1, 0, 1) 0LA1RB_0RB0LC_1LA1RZ 24
(1, 0, 1, 0, 1, 0, 1) 0RB1RZ_0LC0LB_1RA0LA 21
</pre>

==Notes==
<references />

Least Busy Beaver

2025-02-16T23:32:28Z

Racheline: BB^-(4) = 107

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.

== Definition ==
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

<math display="block">BB^-(n, m) = min_T BB_{init}(n, m, T)</math>

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.

Note that <math>BB_{init}(n, m, B) = BB(n, m)</math> where B is the blank (all-zeros) tape. Therefore,

<math display="block">BB^-(n, m) \le BB(n, m)</math>

We have not yet found an example where we can prove that <math>BB^-(n, m) \ne BB(n, m)</math>.

== Known Results ==
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>.

{| class="wikitable"
|+ Small least busy beaver values
|-
| || 2-state || 3-state || 4-state
|-
| 2-symbol
| <math>BB^-(2) = 6</math>
| <math>BB^-(3) = 21</math>
| <math>BB^-(4) = 107</math>
|-
| 3-symbol
| <math>BB^-(2, 3) = 38</math>
|
|
|}

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 <math>BB^-(4, 2) = 107</math><ref><math>BB^-(4, 2) = 107</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340827079012384911 Discord message link]</ref>. None of this has been formally verified as of 16 Feb 2025. 
Certificate of <math>BB^-(2, 2) = BB(2, 2) = 6</math>:<pre>
(0, 0, 0) 1RB1RZ_0LB1LA 6
(0, 0, 1) 0LB1RZ_1RA0RB 6
(0, 1, 0, 1, 0) 0RA0RB_0LB1RZ 6
(0, 1, 0, 1, 1) 0LA0LB_0RB1RZ 6
(1, 1, 0, 1, 1) 0RB1RZ_0LB0LA 7
</pre>
Certificate of <math>BB^-(3, 2) = BB(3, 2) = 21</math>:<pre>
(0, 0, 0, 0, 1) 0LB0LC_1RB1LC_1RZ1RA 21
(0, 0, 0, 1, 1) 1RB0LB_1RZ1LC_1RC1RA 22
(0, 1, 0, 1, 1) 1RB0RC_1RC0LB_0LA1RZ 21
(1, 0, 0, 0, 1) 0RA1LB_0LB0RC_1RA1RZ 23
(1, 0, 0, 1, 0) 1LA1RB_0LC0RB_0LA1RZ 23
(1, 0, 0, 1, 1) 0LB1RC_1LA1RZ_0RC0LA 21
(1, 1, 0, 1, 1) 0RB0LB_1RZ1LC_1RA0RC 21
(0, 0, 0, 0, 0, 0, 0) 1RB1RZ_1LB0RC_1LC1LA 21
(0, 0, 0, 0, 0, 0, 1) 0LB1RZ_0LC1RB_1RA0RC 24
(0, 0, 0, 0, 1, 0, 0) 0LB0RB_1RB1LC_1RZ0LA 22
(0, 0, 0, 0, 1, 0, 1) 0LB0RB_1RB1LC_1RZ0LA 22
(0, 0, 1, 0, 1, 0, 0) 0RA0RB_1LB1LC_1RA1RZ 21
(0, 0, 1, 0, 1, 0, 1) 0LA0LB_1RB1RC_1LA1RZ 21
(1, 0, 0, 0, 0, 0, 1) 0RA0LB_1LC1RZ_0LC1RA 40
(1, 0, 0, 0, 1, 0, 0) 0LA1RB_0RB0LC_1LA1RZ 24
(1, 0, 0, 0, 1, 0, 1) 0LA1RB_0RB0LC_1LA1RZ 24
(1, 0, 1, 0, 1, 0, 1) 0RB1RZ_0LC0LB_1RA0LA 21
</pre>

==Notes==
<references />

Least Busy Beaver

2025-02-16T21:32:55Z

Racheline:

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.

== Definition ==
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

<math display="block">BB^-(n, m) = min_T BB_{init}(n, m, T)</math>

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.

Note that <math>BB_{init}(n, m, B) = BB(n, m)</math> where B is the blank (all-zeros) tape. Therefore,

<math display="block">BB^-(n, m) \le BB(n, m)</math>

We have not yet found an example where we can prove that <math>BB^-(n, m) \ne BB(n, m)</math>.

== Known Results ==
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>.

{| class="wikitable"
|+ Small least busy beaver values
|-
| || 2-state || 3-state || 4-state
|-
| 2-symbol
| <math>BB^-(2) = 6</math>
| <math>BB^-(3) = 21</math>
| <math>50\le BB^-(4)\le 107</math>
|-
| 3-symbol
| <math>BB^-(2, 3) = 38</math>
|
|
|}

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 <math>BB^-(4, 2)\ge 50</math><ref><math>BB^-(4, 2)\ge 50</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340783571501187142 Discord message link]</ref>. None of this has been formally verified as of 16 Feb 2025. 
Certificate of <math>BB^-(2, 2) = BB(2, 2) = 6</math>:<pre>
(0, 0, 0) 1RB1RZ_0LB1LA 6
(0, 0, 1) 0LB1RZ_1RA0RB 6
(0, 1, 0, 1, 0) 0RA0RB_0LB1RZ 6
(0, 1, 0, 1, 1) 0LA0LB_0RB1RZ 6
(1, 1, 0, 1, 1) 0RB1RZ_0LB0LA 7
</pre>
Certificate of <math>BB^-(3, 2) = BB(3, 2) = 21</math>:<pre>
(0, 0, 0, 0, 1) 0LB0LC_1RB1LC_1RZ1RA 21
(0, 0, 0, 1, 1) 1RB0LB_1RZ1LC_1RC1RA 22
(0, 1, 0, 1, 1) 1RB0RC_1RC0LB_0LA1RZ 21
(1, 0, 0, 0, 1) 0RA1LB_0LB0RC_1RA1RZ 23
(1, 0, 0, 1, 0) 1LA1RB_0LC0RB_0LA1RZ 23
(1, 0, 0, 1, 1) 0LB1RC_1LA1RZ_0RC0LA 21
(1, 1, 0, 1, 1) 0RB0LB_1RZ1LC_1RA0RC 21
(0, 0, 0, 0, 0, 0, 0) 1RB1RZ_1LB0RC_1LC1LA 21
(0, 0, 0, 0, 0, 0, 1) 0LB1RZ_0LC1RB_1RA0RC 24
(0, 0, 0, 0, 1, 0, 0) 0LB0RB_1RB1LC_1RZ0LA 22
(0, 0, 0, 0, 1, 0, 1) 0LB0RB_1RB1LC_1RZ0LA 22
(0, 0, 1, 0, 1, 0, 0) 0RA0RB_1LB1LC_1RA1RZ 21
(0, 0, 1, 0, 1, 0, 1) 0LA0LB_1RB1RC_1LA1RZ 21
(1, 0, 0, 0, 0, 0, 1) 0RA0LB_1LC1RZ_0LC1RA 40
(1, 0, 0, 0, 1, 0, 0) 0LA1RB_0RB0LC_1LA1RZ 24
(1, 0, 0, 0, 1, 0, 1) 0LA1RB_0RB0LC_1LA1RZ 24
(1, 0, 1, 0, 1, 0, 1) 0RB1RZ_0LC0LB_1RA0LA 21
</pre>

==Notes==
<references />

Least Busy Beaver

2025-02-16T18:24:58Z

Racheline:

Least busy beaver

2025-02-16T18:22:02Z

Racheline: Racheline moved page Least busy beaver to Least Busy Beaver: consistency

#REDIRECT [[Least Busy Beaver]]

Least Busy Beaver

2025-02-16T18:22:02Z

Racheline: Racheline moved page Least busy beaver to Least Busy Beaver: consistency

Talk:Champions

2025-02-13T18:56:34Z

Racheline:

== Self-Reporting and Verification ==
This champions page has ended up with a lot of self reported and (I assume) not independently verified champions. I'm conflicted about this: On the one hand I want this wiki to have an encyclopedic/Wikipedia style: it would include things which are known, established and verified. On the other hand, I don't want to stifle innovation or gatekeep what counts as proper verification. As a compromise I have updated the table to add a "Verification" column. The idea here is to indicate which results have been independently verified by another contributor. My idea is that that verification should include some sort of write-up (wiki page, blog post, etc) describing the TM and how it is known to run this long. I have linked to examples of my own for Pavel's BB(6) and Daniel's BB(16) champions. I would love to see some independent analyses of other TMs here (especially smaller ones like Racheline's BB(14) > Graham champion). [[User:Sligocki|Sligocki]] ([[User talk:Sligocki|talk]]) 16:19, 10 December 2024 (UTC)
:Particularly interesting is Racheline's BB(14) > Graham champion. --[[User:Konkhra|Konkhra]] ([[User talk:Konkhra|talk]]) 01:53, 12 December 2024 (UTC)

==Larger champions==
What are the known two-symbol champions beyond BB(16)? Vielhaber, Chacón, and Ceballos's paper "[https://arxiv.org/abs/2303.02855v1 Friedman's 'Long Finite Sequences': The End of the Busy Beaver Contest]" gives a 2450-state two-symbol busy beaver halting after at least n(4) steps, where n is Friedman's [https://googology.miraheze.org/wiki/Block_subsequence_theorem block subsequence function], but this is a very large jump up in state count from 14 states for fω+1(65536). (This paper has some mistakes with their (symbol,state count) notation for TMs, for example referring to Aaronson's and Yedidia's machine as a (7910,2) machine rather than a (2,7910) machine, so maybe the machine whose state count I wrote here is the wrong one.) [[User:C7X|C7X]] ([[User talk:C7X|talk]]) 22:00, 17 August 2024 (UTC)

:Today i found some bounds on BB(20) and BB(21), though i'm not sure if they're new. <math>\Sigma(20) > f_{\omega+2}^2(21)</math> due to {{TM|1LR0LR_0RJ1RG_0RD1LC_1RQ1RE_1LO0RQ_1LH1LF_0LC1LH_0LI0LF_1RD0LF_---0RK_0LM1LL_0LL1LM_1LE1LN_0LF0LM_0RP1LO_0LF0RQ_1RB1RQ_0RS1LA_1LT1RS_0LP0RR|halt}} and <math>\Sigma(21) > f_{\omega^2}^2(4 \uparrow\uparrow 341)</math> due to {{TM|0LI0LF_0RJ1RG_0RD1LC_1RH1RE_1LO0RH_1LA1LF_0LC1LA_1RB1RH_1RD0LF_1LP0RK_0LM1LL_0LL1LM_1LE1LN_0RQ0LM_0RP1LO_1LR0RH_1LF1RQ_---0LS_1LH0LT_1LH1LU_0LE1LR|halt}}.
:The old googology wiki claims [https://googology.fandom.com/wiki/Busy_beaver_function#Larger_values some other bounds], two of which are already implied by the bounds mentioned above, but <math>\Sigma(85)>f_{\varepsilon_0}(1907)</math> and the bounds for more than 2 symbols seem to still be the best known.
:[[User:Racheline|Racheline]] ([[User talk:Racheline|talk]]) 23:08, 17 August 2024 (UTC)
::Racheline, congratulations on discovering a TM that crushes Graham's number. I was very impressed. but I think that in reality BB(8,2) will beat Graham's number. But it is unrealistic for a human to build such a machine. Only to search in the wild. Unfortunately. Nevertheless, congratulations again and further success!!! --[[User:Konkhra|Konkhra]] ([[User talk:Konkhra|talk]]) 03:29, 18 August 2024 (UTC)
:::And how about an article about BB(14)?--[[User:Konkhra|Konkhra]] ([[User talk:Konkhra|talk]]) 03:30, 18 August 2024 (UTC)

IMHO, beyond Graham's number I think we should only list highlights (if anything). Like first TM bigger than blah for various notable blah. Otherwise the churn on this page will be high and the quality low. But I'm open to other points of view. If we do extend this much further, I think maybe we should have a more rigorous process for getting new results demonstrated before they are added. --[[User:Sligocki|sligocki]] ([[User talk:Sligocki|talk]]) 02:57, 18 August 2024 (UTC)

Can you design very large champions as beat the <math>f_{\psi(\varepsilon_{\Omega+1})}(1000)</math>, and beat the <math>f_{\psi(\Omega_\omega)}(1000)</math>, limit for [https://googology.fandom.com/wiki/Bashicu_matrix_system BMS] or beat [https://googology.fandom.com/wiki/Loader%27s_number Loader's number]? --[[User:Jacobzheng|Jacobzheng]] ([[User talk:Jacobzheng|talk]]) 00:45, 17 September 2024 (UTC)

: Later today I can try writing one (or at least starting to write one today), but my machine would likely have thousands of states. [[User:C7X|C7X]] ([[User talk:C7X|talk]]) 15:50, 16 September 2024 (UTC)

:: I now have two-symbol machines with the following running times. In order to squeeze the best possible results out of Bashicu matrix system, some machines have a different function applied to <math>n</math> at each step (this function is what Bashicu calls the "activation function"), although at this scale it doesn't make too much of a difference.

:: {| class="wikitable"
|+ Busy Beaver lower bounds using BM4
|-
! State count !! Running time !! Activation function
|-
| 5889 || <math> >f_{\psi(\varepsilon_{\Omega+1})}(1000)</math> (using BMS to define FSes) || <math>n\mapsto n+1</math>
|-
| 5894 || <math> >f_{\psi_0(\Omega_\omega)}(1000)</math> (using BMS to define FSes) || <math>n\mapsto n+1</math>
|-
| 5908 || <math> >(0,0,0,0,0)(1,1,1,1,1)[2]</math> || <math>n\mapsto n+2</math>
|-
| 5923 || <math> >(0,0,0,0,0)(1,1,1,1,1)[5]</math> || <math>n\mapsto n+1</math>
|-
| 5941 || <math> >(0,0,0,0,0,0,0,0,0,0)(1,1,1,1,1,1,1,1,1,1)[10]</math> || <math>n\mapsto n+1</math>
|-
| 5978 || <math> >(\underbrace{0,0,\ldots,0,0}_{889})(\underbrace{1,1,\ldots,1,1}_{889})[894]</math> || <math>n\mapsto n+6</math>
|-
| 6020 || <math> >(\underbrace{0,0,\ldots,0,0}_{N})(\underbrace{1,1,\ldots,1,1}_{N})[N]</math> where <math>N</math> is <math>2^{2^{2^{2059}}}</math> || <math>n\mapsto n+5</math>
|}

:: '''Edit:''' It turns out CatIsFluffy [https://github.com/CatsAreFluffy/metamath-turing-machines beat me to it]! I don't know how many states the BMS machine has, but [https://cosearch.bbchallenge.org/contribution/m5k4ulm8 BB(1094) > Loader's number], now down to [https://github.com/CatsAreFluffy/metamath-turing-machines/commit/85948b04fc4aeb983ca6d63d6aee5ad6ef308bfe BB(1015)]. [[User:C7X|C7X]] ([[User talk:C7X|talk]]) 11:37, 4 October 2024 (UTC)

Who can design a [https://googology.fandom.com/wiki/Laver_table Laver table] q function level machine. --[[User:Jacobzheng|Jacobzheng]] ([[User talk:Jacobzheng|talk]]) 06:57, 13 February 2025 (UTC)

: Me, probably. This 67-state TM should leave over q81(q(5)-2) 1s on the tape (maybe i have an off-by-one or off-by-two error in the exponent of q but it's still iterated quite a few times):
<pre>
M = (
((1, 1, 1), (0, -1, 3)),
((0, -1, 2), (0, 1, 1)),
((1, 1, 0), (1, -1, 2)),
((0, -1, 4), (1, -1, 0)),
((0, -1, 2), (1, -1, 5)),
((0, 1, 26), (0, 1, 5)),
((1, -1, 57), (0, 1, 26)),
((0, 1, 38), (1, 1, 8)),
((0, 1, 9), (1, 1, 8)),
((0, 1, 62), (0, 1, 10)),
((0, -1, 16), (0, -1, 11)),
((1, -1, 12), (1, -1, 11)),
((0, 1, 15), (0, 1, 13)),
((1, 1, 14), (1, 1, 13)),
((0, -1, 16), (0, -1, 11)),
((0, 1, 10), (1, 1, 15)),
((1, -1, 33), (0, -1, 17)),
((1, -1, 18), (1, -1, 17)),
((0, -1, 19), (1, -1, 18)),
((0, -1, 20), (1, -1, 19)),
((0, 1, 22), (1, -1, 21)),
((1, 1, 21), (0, 1, 22)),
((0, 1, 23), (1, 1, 22)),
((1, -1, 24), (1, 1, 23)),
((1, -1, 30), (0, 1, 25)),
((1, -1, 26), (1, 1, 25)),
((0, 1, 6), (0, -1, 27)),
((0, -1, 28), (1, -1, 27)),
((0, -1, 29), (1, -1, 28)),
((1, -1, 20), (1, -1, 29)),
((1, 1, 32), (0, -1, 31)),
((1, -1, 32), (1, -1, 31)),
((0, 1, 7), (0, -1, 30)),
((0, -1, 34), (0, -1, 33)),
((0, -1, 34), (0, -1, 35)),
((0, 1, 37), (1, 1, 36)),
((0, 1, 36), (1, -1, 16)),
((0, 1, 37), (0, 1, 7)),
((0, 1, 39), (0, 1, 7)),
((0, -1, 44), (0, -1, 40)),
((0, -1, 41), (1, -1, 40)),
((1, 1, 42), (1, -1, 41)),
((0, 1, 43), (1, 1, 42)),
((1, 1, 39), (1, 1, 43)),
((0, -1, 45), (1, -1, 44)),
((0, -1, 47), (0, -1, 46)),
((1, -1, 45), (1, -1, 46)),
((1, -1, 47), (1, 1, 48)),
((0, -1, 49), (1, 1, 48)),
((0, 1, 56), (0, -1, 50)),
((0, 1, 49), (0, 1, 51)),
((1, 1, 52), (1, 1, 51)),
((0, -1, 55), (0, -1, 53)),
((1, -1, 54), (1, -1, 53)),
((0, 1, 51), (0, 1, 51)),
((0, -1, 50), (1, -1, 55)),
((1, -1, 57), (1, 1, 56)),
((1, -1, 61), (0, -1, 58)),
((1, 1, 59), (1, -1, 58)),
((0, -1, 60), (0, 1, 56)),
((1, 1, 61), (1, -1, 60)),
((1, -1, 66), (0, 1, 7)),
((0, 1, 63), (0, 1, 62)),
((0, 1, 63), (0, 1, 64)),
((0, -1, 65), (1, 1, -1)),
((0, -1, 65), (1, -1, 66)),
((0, -1, 40), (1, -1, 66))
)

(start from state 0)
</pre>
: It could probably be optimized a bit more, because there are two parts that do basically the same thing and could probably be joined together, but it would cost a few extra states to then differentiate between which of them it was supposed to be, and i don't have time to do that right now.--[[User:Racheline|Racheline]] ([[User talk:Racheline|talk]]) 18:56, 13 February 2025 (UTC)

== BB(51) epsilon_0 champion ==
Can you show the transitions of BB(51) on [[Large champions transitions]] page? --[[User:Jacobzheng|Jacobzheng]] ([[User talk:Jacobzheng|talk]]) 03:24, 3 September 2024 (UTC)

: Here are the transitions and description from Racheline:
<pre>
Σ(51) > (f_ε0)^8(f_ω^ω^3(a lot)) > f_ε0+1(8)
M = (
0: ((1, -1, 0), (0, -1, 1)),
1: ((1, -1, 0), (1, 1, 2)),
2: ((1, -1, 2), (0, -1, 4)),
3: ((0, -1, 10), (1, -1, 4)),
4: ((0, -1, 3), (0, -1, 5)),
5: ((1, -1, 4), (1, 1, 6)),
6: ((1, -1, 7), (0, -1, 15)),
7: ((0, -1, 8), (1, -1, 7)),
8: ((0, -1, 9), (1, -1, 7)),
9: ((1, 1, 11), (1, -1, 9)),
10: ((0, -1, 20), (0, -1, 17)),
11: ((0, 1, 12), (1, 1, 11)),
12: ((0, 1, 13), (1, 1, 13)),
13: ((1, -1, 14), (1, 1, 12)),
14: ((0, -1, 6), (1, -1, 10)),
15: ((0, -1, 16), (1, -1, 16)),
16: ((1, -1, 20), (1, -1, 15)),
17: ((0, -1, 18), (1, -1, 18)),
18: ((1, 1, 19), (1, -1, 17)),
19: ((1, -1, 19), (1, -1, 20)),
20: ((0, -1, 50), (0, -1, 21)),
21: ((0, 1, 43), (0, -1, 9)),
22: ((0, 1, 22), (1, 1, 23)),
23: ((1, 1, 26), (0, -1, 24)),
24: ((1, -1, 25), (0, -1, 24)),
25: ((1, 1, 25), (1, 1, 22)),
26: ((0, 1, 50), (0, 1, 27)),
27: ((1, 1, 26), (1, -1, 35)),
28: ((0, 1, 29), (0, 1, 30)),
29: ((0, -1, 4), (1, 1, 28)),
30: ((1, -1, 31), (1, -1, 0)),
31: ((0, -1, 32), (1, -1, 33)),
32: ((0, -1, 33), (1, -1, 31)),
33: ((0, -1, 34), (0, -1, 35)),
34: ((0, -1, 37), (1, -1, 33)),
35: ((1, 1, 36), (1, 1, 38)),
36: ((0, 1, 37), (1, 1, 28)),
37: ((0, -1, 29), (1, 1, 36)),
38: ((1, 1, 38), (1, 1, 39)),
39: ((0, 1, 38), (1, 1, 40)),
40: ((0, 1, 41), (1, -1, 42)),
41: ((1, -1, 49), (1, 1, 40)),
42: ((1, 1, 36), (0, -1, 42)),
43: ((0, 1, 44), (1, 1, 44)),
44: ((1, -1, 45), (1, 1, 43)),
45: ((0, -1, 46), (1, -1, 46)),
46: ((0, 1, 22), (1, -1, 45)),
47: ((1, -1, 41), (1, -1, 47)),
48: ((0, -1, 47), (0, -1, 49)),
49: ((1, -1, 22), (1, -1, 48)),
50: ((0, -1, 48), (1, 1, halt))
)

(start from state 30)
</pre>

: I haven't investigated it yet. [[User:Sligocki|Sligocki]] ([[User talk:Sligocki|talk]]) 14:27, 3 September 2024 (UTC)

:: It directly simulates Address Notation, which is a different way to write Primitive Sequence System (PrSS for short, it's 1-row Bashicu Matrix System). Here are the expansion rules of Address Notation:
::: Given a sequence <math>S</math> of natural numbers, to compute its expansion, start by letting <math>c</math> be the last element of <math>S</math>. If <math>c=0</math>, then <math>S</math> is a successor and its predecessor is <math>S</math> without the last element. Otherwise, find the last element <math>r</math> of <math>S</math> which is less than <math>c</math>. Decrease <math>c</math> by <math>1</math>, and let <math>B</math> be everything in this new sequence after <math>r</math>. Append infinitely many copies of <math>B</math>.
:: Since the sequences are ordered lexicographically and each element decreases by <math>1</math> until it is <math>0</math>, for any fundamental sequence system where each <math>S[n]</math> is formed by taking an initial subsequence of the expansion of <math>S</math> and changing the last element of that subsequence to a smaller or equal natural number, the ordinal notation given by the fundamental sequence system is the same. If i remember correctly, the TM simulates a variant <math>h</math> of the Hardy Hierarchy with a fundamental sequence system where the FS of each standard <math>S</math> contains all sequences longer than <math>S</math> formed this way from its expansion (except for the first one or two).
:: Specifically,
::: <math>h_0(n)=n+c_0</math>
::: <math>h_{\alpha+1}(n)=h_\alpha(n+c_1)</math>
::: <math>h_\alpha(n)=h_{\alpha[n]}(c_2)</math> for limit <math>\alpha</math>
::: <math>h_{\varepsilon_0}(n) = h_{(0,\lfloor\frac{n+c_3}{2}\rfloor)}(c_4) = h_{\omega\uparrow\uparrow\lfloor\frac{n+c_3}{2}\rfloor}(c_4)</math>
:: for some constants <math>c_0,c_1,c_2,c_3,c_4</math> for which the hierarchy is not degenerate (the constants can be deduced easily from the TM's space-time diagram). In particular, the non-degeneracy means that for most FGHs <math>f</math> with "natural" FS systems, we will have <math>f_{\alpha+1}(n)<h_{\omega^{\alpha+1}}(n+k)</math> for some small constant <math>k</math> (depending on <math>f</math>), and as long as the FGH's FS system has <math>\varepsilon_0[n]\le\omega\uparrow\uparrow(n+c)</math> for some constant <math>c</math>, we have <math>f_{\varepsilon_0}(n)<h_{\varepsilon_0}(2(n+c)+k)</math> for some small constant <math>k</math> (also depending on <math>f</math>. For example, the Wainer Hierarchy is one of these "natural" FGHs (and one of the most well-known ones at this level), and if we extend it to include <math>f_{\varepsilon_0}</math> and <math>f_{\varepsilon_0+1}</math> with the FS <math>\varepsilon_0[n]=\omega\uparrow\uparrow n</math>, it does indeed satisfy <math>f_{\varepsilon_0}(n)<h_{\varepsilon_0}(2n+k)</math> for small <math>k</math>, which means that since the TM computes <math>h_{\varepsilon_0}^8(n)</math> for a large <math>n</math>, its output is larger than <math>f_{\varepsilon_0+1}(8)</math>. [[User:Racheline|Racheline]] ([[User talk:Racheline|talk]]) 19:06, 3 September 2024 (UTC)

I think the bbchallenge can search BB(7) and BB(4,3) in the wild. --[[User:Jacobzheng|Jacobzheng]] ([[User talk:Jacobzheng|talk]]) 14:56, 30 October 2024 (UTC)

: I have thought about writing a program that searches for Ackermann's worm-like behavior of TMs (or at least a program for exponential behavior), but I wouldn't be sure how to do it. [[User:C7X|C7X]] ([[User talk:C7X|talk]]) 22:07, 30 October 2024 (UTC)

== Cloud search for busy beavers ==
We still lack a website for cloud search busy beaver functions. --[[User:Jacobzheng|Jacobzheng]] ([[User talk:Jacobzheng|talk]]) 07:07, 15 December 2024 (UTC)

: In the case of distributed computing projects like Catalogue and Great Internet Mersenne Prime Search, it seems like those are distributed to divvy up a large finite amount of computation. I don't know much about searching for Busy Beavers (e.g. if there is such a thing as an automated process for finding accelerated simulators) but would distributed finite computation be able to help reduce holdout lists? [[User:C7X|C7X]] ([[User talk:C7X|talk]]) 09:05, 15 December 2024 (UTC)

It may be able to search the busy beaver domain BB(7) or even larger more quickly. [[User:Jacobzheng|Jacobzheng]] ([[User talk:Jacobzheng|talk]]) 13:38, 15 December 2024 (UTC)

: Certainly it could do something like direct simulation quickly, but is there a known way to automate more advanced techniques to look for long-running machines? [[User:C7X|C7X]] ([[User talk:C7X|talk]]) 22:17, 15 December 2024 (UTC)
::questions like these should be asked on discord. Few people look at this page.--[[User:Konkhra|Konkhra]] ([[User talk:Konkhra|talk]]) 06:10, 16 December 2024 (UTC)

0RB1RZ0RB 1RC1LB2LB 1LB2RD1LC 1RA2RC0LD

2025-02-08T14:36:36Z

Racheline:

{{machine|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD}}

{{TM|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}} is a halting [[BB(4,3)]] machine that appears to run for around

<math display="block">2 \uparrow\uparrow\uparrow (2^{2^{32}+1}-1)</math>

steps. The TM was discovered by Pavel Kropitz in May 2024 as a group of 6 long-running halting BB(4,3) TMs.<ref>https://discord.com/channels/960643023006490684/1026577255754903572/1243253180297646120</ref> Racheline analyzed the machine by hand in Feb 2025, validating the result and provided the step estimate listed above.<ref>https://discord.com/channels/960643023006490684/1331570843829932063/1337228898068463718</ref>

Pavel listed the halting tape as:

<pre>
1 2^((80*2^((<(8*2^((8*2^(29) - 2)) - 5); (<(80*2^((b - 10)/5) - 17)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> + 4); (<(80*2^((<(80*2^((8*2^((8*2^(29) - 2)) - 3)) - 13)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> - 6)/5) - 17)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> + 4)> - 10)/5) - 3)) 1 0 1 2 1^2 Z> 1 2^2 1
</pre>

== Analysis by racheline ==
https://discord.com/channels/960643023006490684/1331570843829932063/1337228898068463718

<pre>
f(n) = 2^2^(n+1)
g(n) = (5*2^(2^(f^n(0)+1)+2)-8)/9
n0 = (5*2^(2^(2^32+1)+1)-4)/9
n1 = 2^(2^32+1)-4
0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD halts with 5*2^(2^(f^g^n1(n0)(0)+1)+2)+7 nonzero symbols on the tape, after roughly (that)^2 steps
that's around 2^^^(2^(2^32+1)-1)
the rules necessary for verification:
0^inf 1 <D 0^(5n) 2^4 ->
0^inf 1 <D 0^(5*2^n+2)

0^inf 1 <D 0^(5n+2) 2^5 ->
0^inf 1 <D 0^(5*2^(n+1))

0^inf 1 <D 0^(5n) 221122 ->
0^inf 1 <D 0^(5*2^n+4)

0^inf 1 <D 0^(5n+4) 1 0^5 ->
0^inf 1 <D 0^2 2^23 1 0^(5*2^(n+2)-22) 1011221

0^inf 1 <D 0^(5n) 1 0^10 ->
0^inf 1 <D 0^2 2^(5*2^(n+1)) 11221

0^inf 1 <D 0^(5n+2) 2222112 ->
0^inf 1 <D 0^(5*2^(n+1)+2)

0^inf 1 <D 0^(5n+2) 21 0^10 ->
0^inf 1 <D 0^2 2^(5*2^(n+2)-4) 11221

0^inf 1 <D 0^(5n+2) 2^9 ->
0^inf 1 <D 0^(5*2^(n+1)) 2^4 ->
0^inf 1 <D 0^(5*2^2^(n+1)+2) =
0^inf 1 <D 0^(5f(n)+2)

0^inf 1 <D 0^2 2^(9n) ->
0^inf 1 <D 0^(5f^n(0)+2)

0^inf 1 <D 0^2 2^(9n+4) 11221 0^10 ->
0^inf 1 <D 0^(5f^n(0)+2) 222211221 0^10 ->
0^inf 1 <D 0^(5*2^(f^n(0)+1)+2) 21 ->
0^inf 1 <D 0^2 2^(5*2^(2^(f^n(0)+1)+2)-4) 11221 =
0^inf 1 <D 0^2 2^(9g(n)+4) 11221

0^inf 1 <D 0^2 2^(9n+4) 11221 0^(10m) ->
0^inf 1 <D 0^2 2^(9g^m(n)+4) 11221

0^inf 1 <D 0^2 2^16 11221 0^inf
0^inf 1 <D 0^10 2^11 11221 0^inf
0^inf 1 <D 0^22 2^7 11221 0^inf
0^inf 1 <D 0^160 2211221 0^inf
0^inf 1 <D 0^(5*2^32+4) 1 0^inf
0^inf 1 <D 0^2 2^23 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^10 2^18 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^22 2^14 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^160 2^9 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^(5*2^32+2) 2^5 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^(5*2^(2^32+1)) 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^2 2^(5*2^(2^(2^32+1)+1)) 11221 0^(5*2^(2^32+2)-32) 1011221 0^inf =
0^inf 1 <D 0^2 2^(9n0+4) 11221 0^(10n1+8) 1011221 0^inf
0^inf 1 <D 0^2 2^(9g^n1(n0)+4) 11221 0^8 1011221 0^inf
0^inf 1 <D 0^(5*2^(f^g^n1(n0)(0)+1)+2) 21 0^8 1011221 0^inf
this continues the same way as if the 0^8 was a 0^10 until the last few steps, so the tape differs from 0^inf 1 <D 0^2 2^(5*2^(2^(f^g^n1(n0)(0)+1)+2)-4) 11221 in a small amount of symbols on the left end and the right end, which you can easily count by running a smaller example
</pre>

== Equivalent TMs ==

The TMs {{TM|0RB1RZ1RC_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}}, {{TM|1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ0RA|halt}}, {{TM|1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ1RB|halt}} [https://discord.com/channels/960643023006490684/1331570843829932063/1337236324846927932 are equivalent] to {{TM|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}}, with the exact same halting configuration <code>0^inf 1 2^(σ-10) 101211 Z> 1221 0^inf</code>, where <code>σ = 5*2^(2^(f^g^n1(n0)(0)+1)+2)+7</code> is the total number of nonzero symbols.

To see that {{TM|0RB1RZ1RC_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}} is equivalent, simply notice that the situation <code>A> 20</code> never occurs in any of the rules in the above analysis, or inside the low-level bell cycles, and that <code>A> 21</code> and <code>A> 22</code> behave the same in both TMs, except that they take two more steps in {{TM|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}}. Since the A2 transition is the only difference between the two, this means the TMs only differ in the number of steps it takes to halt (and even that difference is insignificant, on the order of σ = <code>5*2^(2^(f^g^n1(n0)(0)+1)+2)+7</code> while the total number of steps is around σ2). {{TM|1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ0RA|halt}} and {{TM|1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ1RB|halt}} are just {{TM|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}} and {{TM|0RB1RZ1RC_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}} respectively, but started one step later, so that their halting time is 1 step smaller.

== References ==
<references />

1RB1LA2LA 1LA2RC1LB 1RD2RB0LC 0RA1RZ1RB

2025-02-08T14:32:37Z

Racheline: Redirected page to 0RB1RZ0RB 1RC1LB2LB 1LB2RD1LC 1RA2RC0LD

#REDIRECT [[0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD]]

1RB1LA2LA 1LA2RC1LB 1RD2RB0LC 0RA1RZ0RA

2025-02-08T14:31:32Z

Racheline: Redirected page to 0RB1RZ0RB 1RC1LB2LB 1LB2RD1LC 1RA2RC0LD

#REDIRECT [[0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD]]

0RB1RZ1RC 1RC1LB2LB 1LB2RD1LC 1RA2RC0LD

2025-02-08T14:30:12Z

Racheline: Redirected page to 0RB1RZ0RB 1RC1LB2LB 1LB2RD1LC 1RA2RC0LD

#REDIRECT [[0RB1RZ0RB 1RC1LB2LB 1LB2RD1LC 1RA2RC0LD]]

0RB1RZ0RB 1RC1LB2LB 1LB2RD1LC 1RA2RC0LD

2025-02-08T14:26:57Z

Racheline:

{{machine|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD}}

{{TM|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}} is a halting [[BB(4,3)]] machine that appears to run for around

<math display="block">2 \uparrow\uparrow\uparrow (2^{2^{32}+1}-1)</math>

steps. The TM was discovered by Pavel Kropitz in May 2024 as a group of 6 long-running halting BB(4,3) TMs.<ref>https://discord.com/channels/960643023006490684/1026577255754903572/1243253180297646120</ref> Racheline analyzed the machine by hand in Feb 2025, validating the result and provided the step estimate listed above.<ref>https://discord.com/channels/960643023006490684/1331570843829932063/1337228898068463718</ref>

Pavel listed the halting tape as:

<pre>
1 2^((80*2^((<(8*2^((8*2^(29) - 2)) - 5); (<(80*2^((b - 10)/5) - 17)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> + 4); (<(80*2^((<(80*2^((8*2^((8*2^(29) - 2)) - 3)) - 13)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> - 6)/5) - 17)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> + 4)> - 10)/5) - 3)) 1 0 1 2 1^2 Z> 1 2^2 1
</pre>

== Analysis by racheline ==
https://discord.com/channels/960643023006490684/1331570843829932063/1337228898068463718

<pre>
f(n) = 2^2^(n+1)
g(n) = (5*2^(2^(f^n(0)+1)+2)-8)/9
n0 = (5*2^(2^(2^32+1)+1)-4)/9
n1 = 2^(2^32+1)-4
0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD halts with 5*2^(2^(f^g^n1(n0)(0)+1)+2)+7 nonzero symbols on the tape, after roughly (that)^2 steps
that's around 2^^^(2^(2^32+1)-1)
the rules necessary for verification:
0^inf 1 <D 0^(5n) 2^4 ->
0^inf 1 <D 0^(5*2^n+2)

0^inf 1 <D 0^(5n+2) 2^5 ->
0^inf 1 <D 0^(5*2^(n+1))

0^inf 1 <D 0^(5n) 221122 ->
0^inf 1 <D 0^(5*2^n+4)

0^inf 1 <D 0^(5n+4) 1 0^5 ->
0^inf 1 <D 0^2 2^23 1 0^(5*2^(n+2)-22) 1011221

0^inf 1 <D 0^(5n) 1 0^10 ->
0^inf 1 <D 0^2 2^(5*2^(n+1)) 11221

0^inf 1 <D 0^(5n+2) 2222112 ->
0^inf 1 <D 0^(5*2^(n+1)+2)

0^inf 1 <D 0^(5n+2) 21 0^10 ->
0^inf 1 <D 0^2 2^(5*2^(n+2)-4) 11221

0^inf 1 <D 0^(5n+2) 2^9 ->
0^inf 1 <D 0^(5*2^(n+1)) 2^4 ->
0^inf 1 <D 0^(5*2^2^(n+1)+2) =
0^inf 1 <D 0^(5f(n)+2)

0^inf 1 <D 0^2 2^(9n) ->
0^inf 1 <D 0^(5f^n(0)+2)

0^inf 1 <D 0^2 2^(9n+4) 11221 0^10 ->
0^inf 1 <D 0^(5f^n(0)+2) 222211221 0^10 ->
0^inf 1 <D 0^(5*2^(f^n(0)+1)+2) 21 ->
0^inf 1 <D 0^2 2^(5*2^(2^(f^n(0)+1)+2)-4) 11221 =
0^inf 1 <D 0^2 2^(9g(n)+4) 11221

0^inf 1 <D 0^2 2^(9n+4) 11221 0^(10m) ->
0^inf 1 <D 0^2 2^(9g^m(n)+4) 11221

0^inf 1 <D 0^2 2^16 11221 0^inf
0^inf 1 <D 0^10 2^11 11221 0^inf
0^inf 1 <D 0^22 2^7 11221 0^inf
0^inf 1 <D 0^160 2211221 0^inf
0^inf 1 <D 0^(5*2^32+4) 1 0^inf
0^inf 1 <D 0^2 2^23 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^10 2^18 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^22 2^14 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^160 2^9 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^(5*2^32+2) 2^5 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^(5*2^(2^32+1)) 1 0^(5*2^(2^32+2)-22) 1011221 0^inf
0^inf 1 <D 0^2 2^(5*2^(2^(2^32+1)+1)) 11221 0^(5*2^(2^32+2)-32) 1011221 0^inf =
0^inf 1 <D 0^2 2^(9n0+4) 11221 0^(10n1+8) 1011221 0^inf
0^inf 1 <D 0^2 2^(9g^n1(n0)+4) 11221 0^8 1011221 0^inf
0^inf 1 <D 0^(5*2^(f^g^n1(n0)(0)+1)+2) 21 0^8 1011221 0^inf
this continues the same way as if the 0^8 was a 0^10 until the last few steps, so the tape differs from 0^inf 1 <D 0^2 2^(5*2^(2^(f^g^n1(n0)(0)+1)+2)-4) 11221 in a small amount of symbols on the left end and the right end, which you can easily count by running a smaller example
</pre>

== Equivalent TMs ==

The TMs {{TM|0RB1RZ1RC_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}}, {{TM|1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ0RA|halt}}, {{TM|1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ1RB|halt}} are equivalent to {{TM|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}}, with the exact same halting configuration <code>0^inf 1 2^(σ-10) 101211 Z> 1221 0^inf</code>, where <code>σ = 5*2^(2^(f^g^n1(n0)(0)+1)+2)+7</code> is the total number of nonzero symbols.

To see that {{TM|0RB1RZ1RC_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}} is equivalent, simply notice that the situation <code>A> 20</code> never occurs in any of the rules in the above analysis, or inside the low-level bell cycles, and that <code>A> 21</code> and <code>A> 22</code> behave the same in both TMs, except that they take two more steps in {{TM|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}}. Since the A2 transition is the only difference between the two, this means the TMs only differ in the number of steps it takes to halt (and even that difference is insignificant, on the order of σ = <code>5*2^(2^(f^g^n1(n0)(0)+1)+2)+7</code> while the total number of steps is around σ2. {{TM|1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ0RA|halt}} and {{TM|1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ1RB|halt}} are just {{TM|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}} and {{TM|0RB1RZ1RC_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}} respectively, but started one step later, so that their halting time is 1 step smaller.

== References ==
<references />

Bonus Cryptid

2025-02-06T23:09:04Z

Racheline:

{{TM|1RB3RB---3LA1RA_2LA3RA4LB0LB1LB|undecided}} sometimes called "Bonus Cryptid" is a [[BB(2,5)]] found by Daniel Yuan in May 2024. It appeared to be a [[Cryptid]], but in Aug 2024, Andrew Ducharme showed that it reached an unknown rule, so more investigation was necessary.

In Feb 2025, Racheline [https://discord.com/channels/960643023006490684/1259770421046411285/1337181169233559633 simulated] it past the unknown rule. According to her simulation, the machine reaches <code>A(1287547464911049659,10)</code> after <code>1894603970741566467769886232237213051</code> steps, and from there, the TM seems to be a cryptid.

See https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html#a-bonus-cryptid

== Behavior ==
<pre>
1RB3RB---3LA1RA_2LA3RA4LB0LB1LB

Define
A(a, b) = 0^inf Halt
A(3n, b+1) -> A(4n+3, b)
A(3n+1, b) -> A(4n+3, b+3)
A(3n+2, 0) -> ?
A(3n+2, b+1) -> A(4n+5, b)

Starts: A(3, 1)
</pre>

== Analysis by Andrew Ducharme ==
https://discord.com/channels/960643023006490684/1259770421046411285/1336973758182981634<nowiki>I found in August that it hits A(3n+2,0) after 113 A rule steps, but never seriously looked into what happened from there. The tape of the actual TM at that point is ginormous, so I looked at cases A(3n+2,0) -> 0<A 2 0^(3n+2) 2 0. From observations of the cases n=[0,1,2,...,10], the tape </nowiki><code>A(3n+2, 0)</code> goes to <code>(16/3 n + 7 , 1) if n = 0 (mod 3), (16/3n + 25/3, 2) if n = 2 (mod 3).</code> God knows what happens if n is congruent to 1. Using these rules, I was able to go from 113 rule steps to........118 before the congruent 1 case was triggered.

In the first two cases, the lone 2 on the right hand side of the tape becomes a lone 4, and then is subsumed into the normal A(a,b) framework. In the last case, the lone 2 becomes a lone 4, then becomes a lone 1, but from there, I don't see a pattern. Sometimes it fixes itself, like when n = 1, but sometimes we enter a whole new phase like with n = 4.{{Machine|1RB3RB---3LA1RA_2LA3RA4LB0LB1LB}}
[[Category:Cryptids]]
[[Category:Stub]]

1RB3LA4RB0RB2LA 1LB2LA3LA1RA1RZ

2025-01-16T21:12:28Z

Racheline:

{{machine|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ}}
{{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ}}

This is the current [[BB(2,5)]] champion. It halts with sigma score (and runtime) over <math>10^{10^{10^{3\,314\,360}}}</math>. It was discovered by Daniel Yuan and shared [https://discord.com/channels/960643023006490684/1084047886494470185/1254826217375273112 on Discord] on 24 Jun 2024 and shared on the busy-beaver-discuss email list [https://groups.google.com/g/busy-beaver-discuss/c/PGOBAz46K6I/m/af5sjd6MBAAJ the next day].

== Analyses ==

=== dyuan01 ===
dyuan01 [https://discord.com/channels/960643023006490684/1084047886494470185/1254826217375273112 24 Jun 2024 11:51am EDT]:<pre>
the TM appears to halt at

[11] [01]^(a+b+c+31) [11]^(d+1) 4 dyuan01 [https://discord.com/channels/960643023006490684/1084047886494470185/1254842225980997793 24 Jun 2024 12:55pm EDT]:<pre>
Alright, so first things first, I should establish some rules, (all variables are natural numbers unless otherwise specified)

Basic rules (all can be simulated in a fixed number of steps):
1) [01] <A -> [11] A>
2) [11] <A -> <A [33]
3) A> [33] -> [01] A>
4) [01] <A3 -> [11] 0B>
5) [11] <A3 -> <A3 [33]
6) 0B> [33] -> [01] 0B>
7) A> [21] -> <A [22]
8) A> [22] -> <A [23]
9) A> [23] -> [41] A>
10) A> 0^inf -> <A [21] 0^inf
11) 0B> [21] -> <A3 [33]
12) 0B> [22] 0^inf -> Halt at [11] 4 [23] -> [11] 0B>
14) [41] <A -> <A [23]
15) 0^inf [11] <A -> 0^inf [11] 0B>

Counter rule helper:
A) [01] [11]^x <A -> [11] [01]^x A> (Basic rules 2*, 1, 3*)

Counter rules:
1) [01] [11]^x <A [23]^y 0^inf -> [11] [01]^x <A [23]^y [21] 0^inf (Counter rule A, Basic rules 9*, 10, 14*)
2) [01] [11]^x <A [23]^y [21] -> [11] [01]^x <A [23]^y [22] (Counter rule A, Basic rules 9*, 7, 14*)
3) [01] [11]^x <A [23]^y [22] -> [11] [01]^x <A [23]^(y+1) (Counter rule A, Basic rules 9*, 8, 14*)
4) 0^inf [11]^(x+1) <A -> 0^inf [11] [01]^x 0B> (Basic rules 2*, 15, 6*)
5) [01] [11]^x <A3 -> [11] [01]^x 0B> (Split <A3 into <A 3, then use Counter rule A, then simulate a step and merge 0 B> into 0B>)

Advanced rules:
1) [01]^3 0B> 0^inf -> [11] [01]^3 <A [21] 0^inf (simulatable in finite steps)
2) [01] [11]^(x+2) 0B> 0^inf -> [11] [01]^x [11]^2 [01] <A [21] 0^inf (Uses Basic rules 2* and 3*, but otherwise can be simulated in finite and bounded steps)

Now, I will simulate some tapes when they are overflowing from certain starting positions (assume 0^inf on both ends and x,y>=2):

(Overflow rule 1)
[11]^x <A [23]^y [21]
[11] [01]^(x-1) 0B> [23]^y [21] (Counter rule 4)
[11] [01]^(x-1) [11]^y 0B> [21] (Basic rule 13*)
[11] [01]^(x-1) [11]^y <A3 [33] (Basic rule 11)
[11] [01]^(x-2) [11] [01]^y 0B> [33] (Counter rule 5)
[11] [01]^(x-2) [11] [01]^(y+1) 0B> (Basic rule 6)
[11] [01]^(x-2) [11] [01]^(y-2) [11] [01]^3 <A [21] (Advanced rule 1)

(Overflow rule 2)
[11]^x <A [23]^y
[11] [01]^(x-1) 0B> [23]^y (Counter rule 4)
[11] [01]^(x-1) [11]^y 0B> (Basic rule 13*)
[11] [01]^(x-2) [11] [01]^(y-2) [11]^2 [01] <A [21] (Advanced rule 2)

(Overflow rule 3)
[11]^x <A [23]^y [22]
[11] [01]^(x-1) 0B> [23]^y [22] (Counter rule 4)
[11] [01]^(x-1) [11]^y 0B> [22] (Basic rule 13*)
Halt at [11] [01]^(x-1) [11]^(y+1) 4 <B 1 (Basic rule 12)

The only steps missing now are the steps to get from (11|01)* <A (21) to (11)* <A (23)* (|21|22), which takes advantage of binary representations and division mod 3.
Now we start to simulate the tape

At some point, the tape reaches [11]^7 <A [23]^17 [21]. By overflow rule 1, we reach
[11] [01]^5 [11] [01]^15 [11] [01]^3 <A [21]

If we treat [11] as 0 and [01] as 1 in binary, then [11] [01]^5 [11] [01]^15 [11] [01]^3 has a binary representation of (2^25-2^19-9). This is divisible by 3, so let a = (2^25-2^19-9)/3 = 11010045 (an odd number). Then we get
[11] [01]^5 [11] [01]^15 [11] [01]^3 <A [21]
[11] [11]^5 [11] [11]^15 [11] [11]^3 <A [23]^a [21]
[11]^26 <A [23]^a [21]

We apply overflow rule 1 again to get
[11] [01]^24 [11] [01]^(a-2) [11] [01]^3 <A [21]

This has a binary representation of 2^(a+27)-2^(a+2)-9, which is 2 mod 3. Let b = (2^(a+27)-2^(a+2)-11)/3, which is an odd number, then we get
[11] [01]^24 [11] [01]^(a-2) [11] [01]^3 <A [21]
[11]^(a+28) <A [23]^(b+1)

Apply overflow rule 2 to get
[11] [01]^(a+26) [11] [01]^(b-1) [11]^2 [01] <A [21]

This has a binary representation of 2^(a+b+29)-2^(b+2)-7, which is also 2 mod 3. Let c = (2^(a+b+29)-2^(b+2)-9)/3, another odd number, then we get
[11]^(a+b+30) <A [23]^(c+1)

We apply overflow rule 2 again to get
[11] [01]^(a+b+28) [11] [01]^(c-1) [11]^2 [01] <A [21]

This has a binary representation of 2^(a+b+c+31)-2^(c+2)-7, which is 1 mod 3. Let d = (2^(a+b+c+31)-2^(c+2)-8)/3. We get
[11]^(a+b+c+32) <A [23]^d [22]

After applying overflow rule 3 we get that this halts at
[11] [01]^(a+b+c+31) [11]^(d+1) 4 Btw, d > 2^c > 2^2^b > 2^2^2^a > 2^2^2^2^23 > 2^2^2^2^2^4 = 2^2^2^2^2^2^2 = 2^^7, so that's probably the lower bound that should be used in steps and sigma for this TM.

LegionMammal978 [https://discord.com/channels/960643023006490684/1084047886494470185/1254967208291991582 24 Jun 2024 9:11pm EDT]:

Assuming your values are correct, HyperCalc and my own manual calculations agree that σ ≈ 2^2^(2.8138364628466968⋅10^3314361) ≈ 10^10^(8.470491782098934⋅10^3314360). Equivalently, this is (2 ↑)⁷ 1.127778888301767 or (10 ↑)⁴ 6.5203998005419574.

=== Shawn Ligocki ===
Shawn Ligocki [https://groups.google.com/g/busy-beaver-discuss/c/PGOBAz46K6I/m/L8hh3KqOBAAJ 25 Jun 2024 1:35am EDT]:

At a high level, this TM satisfies the following rules:

Counter Rules:

* 01 11^x <A 23^y 00 -> 11 01^x <A 23^y 21
* 01 11^x <A 23^y 21 -> 11 01^x <A 23^y 22
* 01 11^x <A 23^y 22 -> 11 01^x <A 23^y 23

In other words, each iteration, the left counts up 1 in a binary counter (using "01" for 0 and "11" for 1) while the right keeps track of the number of iterations modulo 3 (using the final value of "21", "22" or "23") and grows every 3 iterations.

This continues until the counter "overflows" and depending upon the mod on the right side it has one of 3 possible behaviors.

Overflow Rules:

* 0^inf 11^x+2 <A 23^y+2 0^inf -> 0^inf 11 01^x 11 01^y 11^2 01 <A 21 0^inf
* 0^inf 11^x+2 <A 23^y+2 21 0^inf -> 0^inf 11 01^x 11 01^y 11 01^3 <A 21 0^inf
* 0^inf 11^x+1 <A 23^y+1 22 0^inf -> 0^inf 11 01^x 11^y+2 1 Z> 1 0^inf

I have [https://github.com/sligocki/busy-beaver/commit/3189833014f1b2442d4ffe91c6e1d7fdb574675a confirmed] all of the above rules in my inductive validator.

At step 2430 it is in config "0^inf 11^7 <A 23^17 21 0^inf" and Daniel reports that it proceeds to overflow 5 times with the last one hitting the halt rule (I have not confirmed this behavior yet myself). The penultimate config reported by Daniel is:<pre>
0^inf [11] [01]^(a+b+c+31) [11]^(d+1) 4 Where<pre>
a = (2^25-2^19-9)/3 = 11010045
b = [2^(a+27)-2^(a+2)-11]/3
c = [2^(a+b+29)-2^(b+2)-9]/3
d = [2^(a+b+c+31)-2^(c+2)-8]/3
</pre>and Mathew House on Discord reported that this makes the sigma value for this TM > (10 ↑)^4 6.5

=== Pascal Michel ===
Pascal Michel [https://groups.google.com/g/busy-beaver-discuss/c/PGOBAz46K6I/m/ptLo9T7NCQAJ 15 Jan 2025 2:58am EST]:

Let M be the 2x5 TM found by Daniel Yuan in June 2024, with s(M) > 10^(10^(10^3314360)).

Here, I give a proof that s(M) is approximately 3/2 (sigma(M)^2).

(1) Time for

- Counter rules:

01 (11)^x <A (23)^y 00 --( 4(x + y) + 6 )--> 11 (01)^x <A (23)^y 21

01 (11)çx <A (23)^y 21 --( 4(x + y) + 6 )--> 11 (01)^x <A (23)^y 22

01 (11)^x <A (23)^y 22 --( 4(x + y) = 6 )--> 11 (01)^x <A (23)^y 23

so we have

. . . <A (23)^y 00 --( . . . + 12y + . . . )--> . . . <A (23)^(y + 1)

- Overflow rules:

0 (11)^(x + 2) <A (23)^(y + 2) 0^3 --( 4x + 8y + 53 )--> 11 (01)^x 11 (01)^y 01 <A 21

0 (11)^(x + 2) <A (23)^(y + 2) 21 0^3 --( 4x + 8y + 73 )--> 11 (01)^x 11 (01)^y 11 (01)^3 <A 21

0 (11)^(x + 1) <A (23)^(y + 1) 22 0 --( 4(x + y) + 15 )--> 11 (01)^x (11)^(y + 2) 1 Z>1

(2) The time taken on the binary counter is linear in the number of binary steps, so it is dominated by the time taken on the 23s, which is quadratic.

(3) The total time is dominated by the time taken from the 4th overflow to the last overflow.

Just before the last overflow, the configuration is

. . . <A (23)^d 22 0^inf

So the total time is

T ~= (12x1) + (12x2) + . . . +(12x(d - 1)) = 12(d - 1)d/2 ~= 6 d^2

We have sigma(M) ~= 2d, so s(M) ~= 3/2 (sigma(M)^2).

=== racheline ===
racheline [https://discord.com/channels/960643023006490684/1084047886494470185/1329499932847243424 16 Jan 2025 12:18 PM EST]:<pre>
for i in {1,2,3}, (3(a+2)+i,b) is <A 3^(2b+2) (23)^a 2 i
(3k+1,n) -> ((2^n-1)*2^k-2,n+k)
(3k+2,n) -> halt
(3k+3,n) -> ((2^n-1)*2^k,n+k)
start from (58,6)

(58,6) -> (3a+1,25) -> (3b+3,a+25) -> (3c+3,a+b+25) -> (3d+2,a+b+c+25) -> halt
where
a = 11010047
b = ((2^25-1)*2^a-5)/3
c = ((2^(a+25)-1)*2^b-3)/3
d = ((2^(a+b+25)-1)*2^c-2)/3
it halts with exactly a+b+c+25+2d+2 = a+b+c+2d+27 ones on the tape (and no other nonzero symbols)
</pre>

1RB3LA4RB0RB2LA 1LB2LA3LA1RA1RZ

2025-01-16T21:10:05Z

Racheline:

{{machine|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ}}
{{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ}}

This is the current [[BB(2,5)]] champion. It halts with sigma score (and runtime) over <math>10^{10^{10^{3\,314\,360}}}</math>. It was discovered by Daniel Yuan and shared [https://discord.com/channels/960643023006490684/1084047886494470185/1254826217375273112 on Discord] on 24 Jun 2024 and shared on the busy-beaver-discuss email list [https://groups.google.com/g/busy-beaver-discuss/c/PGOBAz46K6I/m/af5sjd6MBAAJ the next day].

== Analyses ==

=== dyuan01 ===
dyuan01 [https://discord.com/channels/960643023006490684/1084047886494470185/1254826217375273112 24 Jun 2024 11:51am EDT]:<pre>
the TM appears to halt at

[11] [01]^(a+b+c+31) [11]^(d+1) 4 dyuan01 [https://discord.com/channels/960643023006490684/1084047886494470185/1254842225980997793 24 Jun 2024 12:55pm EDT]:<pre>
Alright, so first things first, I should establish some rules, (all variables are natural numbers unless otherwise specified)

Basic rules (all can be simulated in a fixed number of steps):
1) [01] <A -> [11] A>
2) [11] <A -> <A [33]
3) A> [33] -> [01] A>
4) [01] <A3 -> [11] 0B>
5) [11] <A3 -> <A3 [33]
6) 0B> [33] -> [01] 0B>
7) A> [21] -> <A [22]
8) A> [22] -> <A [23]
9) A> [23] -> [41] A>
10) A> 0^inf -> <A [21] 0^inf
11) 0B> [21] -> <A3 [33]
12) 0B> [22] 0^inf -> Halt at [11] 4 [23] -> [11] 0B>
14) [41] <A -> <A [23]
15) 0^inf [11] <A -> 0^inf [11] 0B>

Counter rule helper:
A) [01] [11]^x <A -> [11] [01]^x A> (Basic rules 2*, 1, 3*)

Counter rules:
1) [01] [11]^x <A [23]^y 0^inf -> [11] [01]^x <A [23]^y [21] 0^inf (Counter rule A, Basic rules 9*, 10, 14*)
2) [01] [11]^x <A [23]^y [21] -> [11] [01]^x <A [23]^y [22] (Counter rule A, Basic rules 9*, 7, 14*)
3) [01] [11]^x <A [23]^y [22] -> [11] [01]^x <A [23]^(y+1) (Counter rule A, Basic rules 9*, 8, 14*)
4) 0^inf [11]^(x+1) <A -> 0^inf [11] [01]^x 0B> (Basic rules 2*, 15, 6*)
5) [01] [11]^x <A3 -> [11] [01]^x 0B> (Split <A3 into <A 3, then use Counter rule A, then simulate a step and merge 0 B> into 0B>)

Advanced rules:
1) [01]^3 0B> 0^inf -> [11] [01]^3 <A [21] 0^inf (simulatable in finite steps)
2) [01] [11]^(x+2) 0B> 0^inf -> [11] [01]^x [11]^2 [01] <A [21] 0^inf (Uses Basic rules 2* and 3*, but otherwise can be simulated in finite and bounded steps)

Now, I will simulate some tapes when they are overflowing from certain starting positions (assume 0^inf on both ends and x,y>=2):

(Overflow rule 1)
[11]^x <A [23]^y [21]
[11] [01]^(x-1) 0B> [23]^y [21] (Counter rule 4)
[11] [01]^(x-1) [11]^y 0B> [21] (Basic rule 13*)
[11] [01]^(x-1) [11]^y <A3 [33] (Basic rule 11)
[11] [01]^(x-2) [11] [01]^y 0B> [33] (Counter rule 5)
[11] [01]^(x-2) [11] [01]^(y+1) 0B> (Basic rule 6)
[11] [01]^(x-2) [11] [01]^(y-2) [11] [01]^3 <A [21] (Advanced rule 1)

(Overflow rule 2)
[11]^x <A [23]^y
[11] [01]^(x-1) 0B> [23]^y (Counter rule 4)
[11] [01]^(x-1) [11]^y 0B> (Basic rule 13*)
[11] [01]^(x-2) [11] [01]^(y-2) [11]^2 [01] <A [21] (Advanced rule 2)

(Overflow rule 3)
[11]^x <A [23]^y [22]
[11] [01]^(x-1) 0B> [23]^y [22] (Counter rule 4)
[11] [01]^(x-1) [11]^y 0B> [22] (Basic rule 13*)
Halt at [11] [01]^(x-1) [11]^(y+1) 4 <B 1 (Basic rule 12)

The only steps missing now are the steps to get from (11|01)* <A (21) to (11)* <A (23)* (|21|22), which takes advantage of binary representations and division mod 3.
Now we start to simulate the tape

At some point, the tape reaches [11]^7 <A [23]^17 [21]. By overflow rule 1, we reach
[11] [01]^5 [11] [01]^15 [11] [01]^3 <A [21]

If we treat [11] as 0 and [01] as 1 in binary, then [11] [01]^5 [11] [01]^15 [11] [01]^3 has a binary representation of (2^25-2^19-9). This is divisible by 3, so let a = (2^25-2^19-9)/3 = 11010045 (an odd number). Then we get
[11] [01]^5 [11] [01]^15 [11] [01]^3 <A [21]
[11] [11]^5 [11] [11]^15 [11] [11]^3 <A [23]^a [21]
[11]^26 <A [23]^a [21]

We apply overflow rule 1 again to get
[11] [01]^24 [11] [01]^(a-2) [11] [01]^3 <A [21]

This has a binary representation of 2^(a+27)-2^(a+2)-9, which is 2 mod 3. Let b = (2^(a+27)-2^(a+2)-11)/3, which is an odd number, then we get
[11] [01]^24 [11] [01]^(a-2) [11] [01]^3 <A [21]
[11]^(a+28) <A [23]^(b+1)

Apply overflow rule 2 to get
[11] [01]^(a+26) [11] [01]^(b-1) [11]^2 [01] <A [21]

This has a binary representation of 2^(a+b+29)-2^(b+2)-7, which is also 2 mod 3. Let c = (2^(a+b+29)-2^(b+2)-9)/3, another odd number, then we get
[11]^(a+b+30) <A [23]^(c+1)

We apply overflow rule 2 again to get
[11] [01]^(a+b+28) [11] [01]^(c-1) [11]^2 [01] <A [21]

This has a binary representation of 2^(a+b+c+31)-2^(c+2)-7, which is 1 mod 3. Let d = (2^(a+b+c+31)-2^(c+2)-8)/3. We get
[11]^(a+b+c+32) <A [23]^d [22]

After applying overflow rule 3 we get that this halts at
[11] [01]^(a+b+c+31) [11]^(d+1) 4 Btw, d > 2^c > 2^2^b > 2^2^2^a > 2^2^2^2^23 > 2^2^2^2^2^4 = 2^2^2^2^2^2^2 = 2^^7, so that's probably the lower bound that should be used in steps and sigma for this TM.

LegionMammal978 [https://discord.com/channels/960643023006490684/1084047886494470185/1254967208291991582 24 Jun 2024 9:11pm EDT]:

Assuming your values are correct, HyperCalc and my own manual calculations agree that σ ≈ 2^2^(2.8138364628466968⋅10^3314361) ≈ 10^10^(8.470491782098934⋅10^3314360). Equivalently, this is (2 ↑)⁷ 1.127778888301767 or (10 ↑)⁴ 6.5203998005419574.

=== Shawn Ligocki ===
Shawn Ligocki [https://groups.google.com/g/busy-beaver-discuss/c/PGOBAz46K6I/m/L8hh3KqOBAAJ 25 Jun 2024 1:35am EDT]:

At a high level, this TM satisfies the following rules:

Counter Rules:

* 01 11^x <A 23^y 00 -> 11 01^x <A 23^y 21
* 01 11^x <A 23^y 21 -> 11 01^x <A 23^y 22
* 01 11^x <A 23^y 22 -> 11 01^x <A 23^y 23

In other words, each iteration, the left counts up 1 in a binary counter (using "01" for 0 and "11" for 1) while the right keeps track of the number of iterations modulo 3 (using the final value of "21", "22" or "23") and grows every 3 iterations.

This continues until the counter "overflows" and depending upon the mod on the right side it has one of 3 possible behaviors.

Overflow Rules:

* 0^inf 11^x+2 <A 23^y+2 0^inf -> 0^inf 11 01^x 11 01^y 11^2 01 <A 21 0^inf
* 0^inf 11^x+2 <A 23^y+2 21 0^inf -> 0^inf 11 01^x 11 01^y 11 01^3 <A 21 0^inf
* 0^inf 11^x+1 <A 23^y+1 22 0^inf -> 0^inf 11 01^x 11^y+2 1 Z> 1 0^inf

I have [https://github.com/sligocki/busy-beaver/commit/3189833014f1b2442d4ffe91c6e1d7fdb574675a confirmed] all of the above rules in my inductive validator.

At step 2430 it is in config "0^inf 11^7 <A 23^17 21 0^inf" and Daniel reports that it proceeds to overflow 5 times with the last one hitting the halt rule (I have not confirmed this behavior yet myself). The penultimate config reported by Daniel is:<pre>
0^inf [11] [01]^(a+b+c+31) [11]^(d+1) 4 Where<pre>
a = (2^25-2^19-9)/3 = 11010045
b = [2^(a+27)-2^(a+2)-11]/3
c = [2^(a+b+29)-2^(b+2)-9]/3
d = [2^(a+b+c+31)-2^(c+2)-8]/3
</pre>and Mathew House on Discord reported that this makes the sigma value for this TM > (10 ↑)^4 6.5

=== Pascal Michel ===
Pascal Michel [https://groups.google.com/g/busy-beaver-discuss/c/PGOBAz46K6I/m/ptLo9T7NCQAJ 15 Jan 2025 2:58am EST]:

Let M be the 2x5 TM found by Daniel Yuan in June 2024, with s(M) > 10^(10^(10^3314360)).

Here, I give a proof that s(M) is approximately 3/2 (sigma(M)^2).

(1) Time for

- Counter rules:

01 (11)^x <A (23)^y 00 --( 4(x + y) + 6 )--> 11 (01)^x <A (23)^y 21

01 (11)çx <A (23)^y 21 --( 4(x + y) + 6 )--> 11 (01)^x <A (23)^y 22

01 (11)^x <A (23)^y 22 --( 4(x + y) = 6 )--> 11 (01)^x <A (23)^y 23

so we have

. . . <A (23)^y 00 --( . . . + 12y + . . . )--> . . . <A (23)^(y + 1)

- Overflow rules:

0 (11)^(x + 2) <A (23)^(y + 2) 0^3 --( 4x + 8y + 53 )--> 11 (01)^x 11 (01)^y 01 <A 21

0 (11)^(x + 2) <A (23)^(y + 2) 21 0^3 --( 4x + 8y + 73 )--> 11 (01)^x 11 (01)^y 11 (01)^3 <A 21

0 (11)^(x + 1) <A (23)^(y + 1) 22 0 --( 4(x + y) + 15 )--> 11 (01)^x (11)^(y + 2) 1 Z>1

(2) The time taken on the binary counter is linear in the number of binary steps, so it is dominated by the time taken on the 23s, which is quadratic.

(3) The total time is dominated by the time taken from the 4th overflow to the last overflow.

Just before the last overflow, the configuration is

. . . <A (23)^d 22 0^inf

So the total time is

T ~= (12x1) + (12x2) + . . . +(12x(d - 1)) = 12(d - 1)d/2 ~= 6 d^2

We have sigma(M) ~= 2d, so s(M) ~= 3/2 (sigma(M)^2).

=== racheline ===
racheline [https://discord.com/channels/960643023006490684/1084047886494470185/1329499932847243424 16 Jan 2025 12:18 PM EST]:<pre>
(3k+1,n) -> ((2^n-1)*2^k-2,n+k)
(3k+2,n) -> halt
(3k+3,n) -> ((2^n-1)*2^k,n+k)
start from (58,6)

(58,6) -> (3a+1,25) -> (3b+3,a+25) -> (3c+3,a+b+25) -> (3d+2,a+b+c+25) -> halt
where
a = 11010047
b = ((2^25-1)*2^a-5)/3
c = ((2^(a+25)-1)*2^b-3)/3
d = ((2^(a+b+25)-1)*2^c-2)/3
it halts with exactly a+b+c+25+2d+2 = a+b+c+2d+27 ones on the tape (and no other nonzero symbols)
</pre>

Talk:1RJ1RH 1RC1RB 1LI0RD 1RC1LE 0LE1LF 1LG1RH 1RB0LF 0RA1LE 1RF1LJ 0LK1RZ 1LL1LK 1LM1LM 0LI0LL

2024-12-07T11:27:56Z

Racheline: /* Search algorithm */

==Search algorithm==
Incredible result! Has Racheline made public what algorithm she used to find the Collatz-like component? [[User:C7X|C7X]] ([[User talk:C7X|talk]]) 02:40, 7 December 2024 (UTC)

:I manually looked through a space of potentially collatz-like components. In the bbchallenge discord server, i [https://discord.com/channels/960643023006490684/1026577255754903572/1272982108935159881 talked] about some of the ones i checked before this. If i remember correctly, that's also how i found the current BB(n) champions for n in {8,10,11,12,14,20,21}.--[[User:Racheline|Racheline]] ([[User talk:Racheline|talk]]) 11:27, 7 December 2024 (UTC)

1RJ1RH 1RC1RB 1LI0RD 1RC1LE 0LE1LF 1LG1RH 1RB0LF 0RA1LE 1RF1LJ 0LK1RZ 1LL1LK 1LM1LM 0LI0LL

2024-12-07T10:26:59Z

Racheline: not a champion anymore

{{TM|1RJ1RH_1RC1RB_1LI0RD_1RC1LE_0LE1LF_1LG1RH_1RB0LF_0RA1LE_1RF1LJ_0LK1RZ_1LL1LK_1LM1LM_0LI0LL|halt}}

Former BB(13) [[Champions|champion]]. This machine was found by Racheline using an 8-state <math>f_\omega</math>-level mechanism (in the [[Fast-Growing Hierarchy]]) shared by the previous [https://googology.fandom.com/wiki/User:Wythagoras/Rado%27s_sigma_function/BB(13) BB(13) champion] and [https://wiki.bbchallenge.org/wiki/User:Jacobzheng BB(14) champion]. Instead of using the 5 extra states to build a large input to which <math>f_\omega</math> would be applied once before halting, this machine applies <math>f_\omega</math> repeatedly with Collatz-like rules, which allows it to halt with over <math>f_\omega(f_\omega(f_\omega(f_\omega(70))))</math> ones on the tape.

== Analysis ==

The <math>f_\omega</math> mechanism operates on lists of numbers, and simulates the rule

<math display="block">B(a_0,0^k,a_1+1,a_2,a_3,\ldots,a_m) \to B(0^k,a_0+3,a_1,a_2,a_3,\ldots,a_m)</math>

where <math>0^k</math> denotes <math>k</math> consecutive zeroes in the list, using configurations of the form <math>B(a_0,a_1,a_2,\ldots,a_m) = 0^\infty \; 1 \; B> \; 1^{a_0} \; 10 \; 1^{a_1} \; 10 \; 1^{a_2} \; 10 \; \ldots \; 10 \; 1^{a_m} \; 10 \; 0^\infty</math>.
 
This computes a slightly modified Fast-Growing Hierarchy. In particular, letting

<math display="block">\begin{array}{l}
h_0(n)&=&n+3 \\
h_{k+1}(n)&=&h_k^n(1)
\end{array}</math>

one can prove by induction on <math>k</math> that

<math display="block">B(a_0-4,0^k,a_1+1,a_2,a_3,\ldots,a_m) \to B(h_k(a_0)-4,0^k,a_1,a_2,a_3,\ldots,a_m)</math>

for <math>a_0\ge4</math>. This motivates the use of <math>B'(a_0,a_1,\ldots,a_m) = A(a_0-4,a_1,\ldots,a_m)</math> instead, so that

<math display="block">B'(a_0,0^k,a_1+1,a_2,a_3,\ldots,a_m) \to B'(h_k(a_0),0^k,a_1,a_2,a_3,\ldots,a_m)</math>

and by applying this repeatedly,

<math display="block">B'(a_0,a_1,a_2,\ldots,a_k) \to B'(h_{k-1}^{a_k}(\cdots(h_2^{a_2}(h_1^{a_1}(a_0)))\cdots),0^k)</math>
 
This leaves only the case <math>B'(n,0^k)</math>, which we write as <math>D(n,k)</math>. The machine then simulates the Collatz-like rules

<math display="block">\begin{array}{l}
D(n,3k) & \to & Halt(n+4k) \\
D(n,3k+1) & \to & B'(4,n+1,(0,2)^k,1) & \to & D(h_{2k+1}(h_{2k}^2(h_{2k-2}^2(\cdots(h_2^2(h_0^{n+1}(4)))\cdots))),2k+2) \\
D(n,3k+2) & \to & B'(7,0^{g(n)-1},(2,0)^k,2,1) & \to & D(h_{g(n)+2k}(h_{g(n)+2k-1}^2(h_{g(n)+2k-3}^2(\cdots(h_{g(n)+1}^2(h_{g(n)-1}^2(7)))\cdots))),g(n)+2k+1)
\end{array}</math>

where <math>(x,y)^k</math> denotes <math>k</math> consecutive copies of <math>x,y</math> (<math>2k</math> total entries), <math>g(n)=\lfloor\frac{n+1}{2}\rfloor</math>, and <math>Halt(x)</math> means that the machine halts with <math>x</math> ones on the tape.

== Trajectory ==

This machine reaches the configuration <math>D(13,1)</math> after 89 steps, and then follows this trajectory:

<math display="block">\begin{array}{l}
D(13,1) & \to & D(139,2) & \to & D(n_0,71) & \to & D(n_1,\frac{n_0}{2}+47) & \to & D(n_2,\frac{n_0+98}{3}) & \to \\
D(n_3,\frac{2n_0+208}{9}) & \to & D(n_4,\frac{n_3}{2}+\frac{4n_0+407}{27}) & \to & D(n_5,\frac{n_4}{2}+\frac{27n_3+8n_0+787}{81}) & \to & D(n_6,\frac{81n_4+54n_3+16n_0+1898}{243}) & \to & Halt(n_6+\frac{324n_4+216n_3+64n_0+7592}{243})
\end{array}</math>

where <math>n_6\approx n_5\approx f_\omega(n_4)\approx f_\omega^2(n_3)\approx f_\omega^2(n_2)\approx f_\omega^2(n_1)\approx f_\omega^3(n_0)\approx f_\omega^3(h_{70}(h_{69}(h_{69}(7)))) > f_\omega^4(70)</math>.

The trajectory can be computed in the following way.
 
First, note that <math>h_k(n)\equiv n+1\ (mod\ 2)</math> can be proven by induction on <math>k</math>. Next, note that <math>D(n,3k+2)\to D(n',k')</math> where <math>n'</math> is obtained by applying <math>2k+1</math> functions of the form <math>h_m</math> to the input 7, so <math>n'\equiv 7+2k+1\equiv 0\ (mod\ 2)</math>, and <math>D(2n,3k+1)\to D(n',k')</math> where <math>n'</math> is obtained by applying <math>2k+1+n+1</math> functions of the form <math>h_m</math> to the input 4, so <math>n'\equiv 4+2k+1+n+1\equiv 0\ (mod\ 2)</math>. This means that after the first application of the <math>D(n,3k+2)</math> rule, <math>n</math> will always be even, and thus for <math>n</math> appearing after this point, we have <math>g(n)=\lfloor\frac{n+1}{2}\rfloor=\frac{n}{2}</math>.
 
Now the only modular arithmetic left is finding the values of the first arguments of <math>D</math> modulo large powers of 3, so that we know the values of the second arguments of <math>D</math> modulo 3, and thus know which rules to apply. We have <math>h_1(n)=h_0^n(1)=1+\underbrace{3+3+\ldots+3+3}_{n}=1+3n</math> and <math>h_2(n)=h_1^n(1)=1+3(1+3(\cdots(1+3(1\underbrace{))\cdots))}_{n}=1+3+3^2+\ldots+3^{n-1}+3^n=\frac{3^{n+1}-1}{2}</math>. Since the computation of <math>h_k(n)</math> for any <math>k>2</math> ends with something of the form <math>h_2(m)</math>, all first arguments of <math>D</math> starting from <math>n_0=h_{70}(h_{69}(h_{69}(7)))</math> are of the form <math>\frac{3^m-1}{2}</math> for large <math>m</math>, and thus are <math>\frac{3^i-1}{2}\ (mod\ 3^i)</math> for <math>i<h_{69}(7)</math> (note: This upper bound is much larger than what we need and significantly smaller than the exact maximum of <math>i</math> for which this statement holds).
 
With this, we can easily compute each second argument of <math>D</math> modulo 3 just from its expression as a linear combination (with relatively simple coefficients) of the previous first arguments of <math>D</math>, and thus we can compute the linear combination of first arguments that is equal to the second argument in the next step. Repeating this allows us to compute the whole trajectory.

== Related machines ==

The analysis section applies to all machines obtained from this machine by varying the <math>A0</math> transition and the starting state. If the search didn't miss any of these machines, this machine takes the longest to halt out of all machines in this family. This family is part of a larger family of machines obtained by additionally varying the <math>C0</math> transition, but the Collatz-like rules depend on the <math>C0</math> transition. Furthermore, we can change the order of the last 5 states to get {{TM|1RJ1RH_1RC1RB_1LI0RD_1RC1LE_0LE1LF_1LG1RH_1RB0LF_0RA1LE_1LJ1LJ_0LK0LI_1LL1LK_1RF1LM_0LI1RZ|halt}}, which also forms a family of similar size by varying the transitions <math>A0,C0</math> and the starting state. Perhaps even more families can be obtained by changing the <math>G0</math> transition from 1RB to 0RB, but these also differ in the <math>f_\omega</math> part of their behavior, so they compute a different variant of the Fast-Growing Hierarchy (in particular, they simulate <math>B(a_0,0^k,a_1+1,a_2,a_3,\ldots,a_m) \to B(0^k,a_0+2,a_1,a_2,a_3,\ldots,a_m)</math>).

The second place so far (not counting machines that also reach <math>D(13,1)</math>) is taken by {{TM|1RL1RH_1RC1RB_1LI0RD_1RC1LE_0LE1LF_1LG1RH_1RB0LF_0RA1LE_1RF1LJ_0LK1RZ_1LL1LK_1LM1LM_0LI0LL|halt}}, which reaches <math>D(7,2)</math> and halts with more than <math>f_\omega^4(4)</math> ones on the tape, so it's a close competition. The search of these families for higher scores is ongoing.

1RB1RC 1LC1RE 1LD0LB 1RE1LC 1LE0RF 1RZ1RA

2024-11-26T10:46:29Z

Racheline: explained TM behavior

{{machine|1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA}}

{{TM|1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA}} is a long running Halting [[BB(6)]] TM analyzed by Racheline on 25 Nov 2024 ([https://discord.com/channels/960643023006490684/1239205785913790465/1310651468881334394 Discord Link]):

Analysis by Racheline:
<pre>
a_1 = (2^179+1)/3+179
a_2 = (2^a_1+1)/3+a_1
a_3 = (2^a_2+1)/3+a_2
a_4 = (2^a_3+1)/3+a_3-1
a_5 = (2^a_4+1)/3+a_4

the tapes after overflow:
0^∞ <B 0 (10)^17 11 (10)^5 11 (10)^3 11 (10)^2 1111 0^∞
0^∞ <B 0 (10)^513 11 (10)^17 11 (10)^5 11 (10)^3 11 10 1111 0^∞
0^∞ <B 0 (10)^(2^179+1) 11 (10)^513 11 (10)^17 11 (10)^5 11 (10)^4 1111 0^∞
0^∞ <B 0 (10)^(2^a_1+1) 11 (10)^(2^179+1) 11 (10)^513 11 (10)^17 11 (10)^5 11 (10)^3 1111 0^∞
0^∞ <B 0 (10)^(2^a_2+1) 11 (10)^(2^a_1+1) 11 (10)^(2^179+1) 11 (10)^513 11 (10)^17 11 (10)^5 11 (10)^3 11 0^∞
0^∞ <B 0 (10)^(2^a_3+1) 11 (10)^(2^a_2+1) 11 (10)^(2^a_1+1) 11 (10)^(2^179+1) 11 (10)^513 11 (10)^17 11 (10)^5 11 (10)^2 11 0^∞
0^∞ <B 0 (10)^(2^a_4+1) 11 (10)^(2^a_3+1) 11 (10)^(2^a_2+1) 11 (10)^(2^a_1+1) 11 (10)^(2^179+1) 11 (10)^513 11 (10)^17 11 (10)^4 111111 10 11 0^∞

halt at roughly 2^a_5 ≈ 2^2^2^2^2^(2^179/3) ≈ 10^10^10^10^10^10^52.8
</pre>
Between overflows, the right side of the TM is a binary counter, whose bits are either <math>(101010\ |\ 111111)</math>, <math>(10101110\ |\ 11111011)</math>, <math>(1011101010\ |\ 1110111111)</math> or <math>(11101010\ |\ 10111111)</math>, except for the least significant bit which is <math>(1010\ |\ 1111)</math>, where <math>(x\ |\ y)</math> means the bit looks like <math>x</math> when it represents a 0 on the counter, and it looks like <math>y</math> when it represents a 1. The counter is split into bits in a greedy way from left to right. For example, when the tape is <math>0^\infty\! <\!\!B\ 0\ (10)^{17}\ 11\ (10)^5\ 11\ (10)^3\ 11\ (10)^2\ 1111\ 0^\infty</math>, the counter is split into bits as <math>(1010)\ (101010)^5\ (11101010)\ (10101110)^2</math>, and we have <math>101111\ 0^\infty</math> left over at the right end.

The left side is simply a bouncer, which expands leftwards by 2 cells each time the counter increases by 1. To accelerate the TM, we can skip from one overflow to the next by splitting the counter into bits, setting all the bits to represent 1 instead of 0, running the TM (and accelerating its passes through the bits) until it reaches the left end again (which it will do in state B), and then changing the <math>0^\infty\! <\!\!B\ 0\ (10)^2\ 11</math> on the left end into <math>0^\infty\! <\!\!B\ 0\ (10)^{2^n+1}\ 11</math> where <math>n</math> is the number of bits, because the bouncer's size would have increased by <math>2\cdot(2^n-1)</math> cells during the counting we skipped.

Splitting the counter into bits is simple even for very large tapes like <math>0^\infty\! <\!\!B\ 0\ (10)^{2^{a_3}+1}\ 11\ (10)^{2^{a_2}+1}\ 11\ (10)^{2^{a_1}+1}\ 11\ (10)^{2^{179}+1}\ 11\ (10)^{513}\ 11\ (10)^{17}\ 11\ (10)^5\ 11\ (10)^2\ 11\ 0^\infty</math>, because almost all bits are <math>(101010\ |\ 111111)</math>, so we only need to compute the remainders modulo 3 of the amounts of <math>10</math>s between each pair of consecutive <math>11</math>s, and <math>2^n\ (\text{mod}\ 3)</math> only depends on the parity of <math>n</math>.

1RB1LD 1RC1RB 1LC1LA 0RC0RD

2024-09-04T18:28:56Z

Racheline: made a new section for my previous edit because i didn't notice the name of the section i originally put it in

{{machine|1RB1LD_1RC1RB_1LC1LA_0RC0RD}}
{{TM|1RB1LD_1RC1RB_1LC1LA_0RC0RD}}

[[Blanking Beaver]] BLB(4,2) champion which creates a blank tape after 32,779,477 steps. It was discovered and reported by Nick Drozd in 2021.<ref>Nick Drozd. [https://nickdrozd.github.io/2021/07/11/self-cleaning-turing-machine.html A New Record in Self-Cleaning Turing Machines]. 2021.</ref>

== Analysis by [[User:sligocki|Shawn Ligocki]] ==
Let <math display="block">D(a, b) = 0^\infty \; 1^a \; 0^b \; \textrm{D>} \; 0^\infty</math>then:<math display="block">\begin{array}{lc}
D(a+3, & b) & \to & D(a, b+5) \\
D(0, & b) & = & \textrm{Blank} \\
D(1, & b) & \to & D(b+2, 4) \\
D(2, & b) & \to & D(b+3, 4) \\
\end{array}</math>let <math>D(a) = D(a, 4)</math>, then we can simplify to:

<math display="block">\begin{array}{lc}
D(3k ) & \to & \textrm{Blank} \\
D(3k+1) & \to & D(5k+6) \\
D(3k+2) & \to & D(5k+7) \\
\end{array}</math>Starting from <math>D(2)</math> (at step 19) we get the trajectory:

<math display="block">\begin{array}{l}
D(2)
& \to & D(7) & \to & D(16) & \to & D(31) & \to & D(56) & \to & D(97) \\
& \to & D(166) & \to & D(281) & \to & D(472) & \to & D(791) & \to & D(1322) \\
& \to & D(2207) & \to & D(3682) & \to & D(6141) & \to & \textrm{Blank} \\
\end{array} </math>which has the remarkable luck of applying this [[Collatz-like]] map 14 times before reaching the blanking config (expected # of applications before halting is 3).

== Relation to other machines ==

The map and trajectory are equivalent to that of the [[BB(5) champion]]. For all <math>k</math>, let <math>f(k)</math> be the number such that <math>D(k)\to D(f(k))</math>, or <math>\text{HALT}</math> if <math>D(k)\to\textrm{Blank}</math>, and let <math>g</math> be the map simulated by the BB(5) champion. Then:

<math display="block">\begin{array}{lc}
g(2(3k)+2) & = & g(6k+2) & = & \text{HALT} & = & f(3k) \\
g(2(3k+1)+2) & = & g(6k+4) & = & 10k+14 & = & 2f(3k+1)+2 \\
g(2(3k+2)+2) & = & g(6k+6) & = & 10k+16 & = & 2f(3k+2)+2 \\
\end{array}</math>

So the size of this machine's BLB output is tied to the size of the BB(5) champion's output.

== References ==

1RB1LD 1RC1RB 1LC1LA 0RC0RD

2024-09-04T18:25:10Z

Racheline: mentioned equivalence to BB(5) champion

{{machine|1RB1LD_1RC1RB_1LC1LA_0RC0RD}}
{{TM|1RB1LD_1RC1RB_1LC1LA_0RC0RD}}

[[Blanking Beaver]] BLB(4,2) champion which creates a blank tape after 32,779,477 steps. It was discovered and reported by Nick Drozd in 2021.<ref>Nick Drozd. [https://nickdrozd.github.io/2021/07/11/self-cleaning-turing-machine.html A New Record in Self-Cleaning Turing Machines]. 2021.</ref>

== Analysis by [[User:sligocki|Shawn Ligocki]] ==
Let <math display="block">D(a, b) = 0^\infty \; 1^a \; 0^b \; \textrm{D>} \; 0^\infty</math>then:<math display="block">\begin{array}{lc}
D(a+3, & b) & \to & D(a, b+5) \\
D(0, & b) & = & \textrm{Blank} \\
D(1, & b) & \to & D(b+2, 4) \\
D(2, & b) & \to & D(b+3, 4) \\
\end{array}</math>let <math>D(a) = D(a, 4)</math>, then we can simplify to:

<math display="block">\begin{array}{lc}
D(3k ) & \to & \textrm{Blank} \\
D(3k+1) & \to & D(5k+6) \\
D(3k+2) & \to & D(5k+7) \\
\end{array}</math>Starting from <math>D(2)</math> (at step 19) we get the trajectory:

<math display="block">\begin{array}{l}
D(2)
& \to & D(7) & \to & D(16) & \to & D(31) & \to & D(56) & \to & D(97) \\
& \to & D(166) & \to & D(281) & \to & D(472) & \to & D(791) & \to & D(1322) \\
& \to & D(2207) & \to & D(3682) & \to & D(6141) & \to & \textrm{Blank} \\
\end{array} </math>which has the remarkable luck of applying this [[Collatz-like]] map 14 times before reaching the blanking config (expected # of applications before halting is 3).

The map and trajectory are equivalent to that of the [[BB(5) champion]]. For all <math>k</math>, let <math>f(k)</math> be the number such that <math>D(k)\to D(f(k))</math>, or <math>\text{HALT}</math> if <math>D(k)\to\textrm{Blank}</math>, and let <math>g</math> be the map simulated by the BB(5) champion. Then:

<math display="block">\begin{array}{lc}
g(2(3k)+2) & = & g(6k+2) & = & \text{HALT} & = & f(3k) \\
g(2(3k+1)+2) & = & g(6k+4) & = & 10k+14 & = & 2f(3k+1)+2 \\
g(2(3k+2)+2) & = & g(6k+6) & = & 10k+16 & = & 2f(3k+2)+2 \\
\end{array}</math>

So the size of this machine's BLB output is tied to the size of the BB(5) champion's output.

== References ==

BB(5) champion

2024-09-04T18:23:11Z

Racheline: Redirected page to 5-state busy beaver winner

#REDIRECT [[5-state busy beaver winner]]

Talk:Champions

2024-09-03T19:06:37Z

Racheline:

==Larger champions==
What are the known two-symbol champions beyond BB(16)? Vielhaber, Chacón, and Ceballos's paper "[https://arxiv.org/abs/2303.02855v1 Friedman's 'Long Finite Sequences': The End of the Busy Beaver Contest]" gives a 2450-state two-symbol busy beaver halting after at least n(4) steps, where n is Friedman's [https://googology.miraheze.org/wiki/Block_subsequence_theorem block subsequence function], but this is a very large jump up in state count from 14 states for fω+1(65536). (This paper has some mistakes with their (symbol,state count) notation for TMs, for example referring to Aaronson's and Yedidia's machine as a (7910,2) machine rather than a (2,7910) machine, so maybe the machine whose state count I wrote here is the wrong one.) [[User:C7X|C7X]] ([[User talk:C7X|talk]]) 22:00, 17 August 2024 (UTC)

:Today i found some bounds on BB(20) and BB(21), though i'm not sure if they're new. <math>\Sigma(20) > f_{\omega+2}^2(21)</math> due to {{TM|1LR0LR_0RJ1RG_0RD1LC_1RQ1RE_1LO0RQ_1LH1LF_0LC1LH_0LI0LF_1RD0LF_---0RK_0LM1LL_0LL1LM_1LE1LN_0LF0LM_0RP1LO_0LF0RQ_1RB1RQ_0RS1LA_1LT1RS_0LP0RR|halt}} and <math>\Sigma(21) > f_{\omega^2}^2(4 \uparrow\uparrow 341)</math> due to {{TM|0LI0LF_0RJ1RG_0RD1LC_1RH1RE_1LO0RH_1LA1LF_0LC1LA_1RB1RH_1RD0LF_1LP0RK_0LM1LL_0LL1LM_1LE1LN_0RQ0LM_0RP1LO_1LR0RH_1LF1RQ_---0LS_1LH0LT_1LH1LU_0LE1LR|halt}}.
:The old googology wiki claims [https://googology.fandom.com/wiki/Busy_beaver_function#Larger_values some other bounds], two of which are already implied by the bounds mentioned above, but <math>\Sigma(85)>f_{\varepsilon_0}(1907)</math> and the bounds for more than 2 symbols seem to still be the best known.
:[[User:Racheline|Racheline]] ([[User talk:Racheline|talk]]) 23:08, 17 August 2024 (UTC)
::Racheline, congratulations on discovering a TM that crushes Graham's number. I was very impressed. but I think that in reality BB(8,2) will beat Graham's number. But it is unrealistic for a human to build such a machine. Only to search in the wild. Unfortunately. Nevertheless, congratulations again and further success!!! --[[User:Konkhra|Konkhra]] ([[User talk:Konkhra|talk]]) 03:29, 18 August 2024 (UTC)
:::And how about an article about BB(14)?--[[User:Konkhra|Konkhra]] ([[User talk:Konkhra|talk]]) 03:30, 18 August 2024 (UTC)

IMHO, beyond Graham's number I think we should only list highlights (if anything). Like first TM bigger than blah for various notable blah. Otherwise the churn on this page will be high and the quality low. But I'm open to other points of view. If we do extend this much further, I think maybe we should have a more rigorous process for getting new results demonstrated before they are added. --[[User:Sligocki|sligocki]] ([[User talk:Sligocki|talk]]) 02:57, 18 August 2024 (UTC)

== BB(51) epsilon_0 champion ==
Can you show the transitions of BB(51) on [[Large champions transitions]] page? --[[User:Jacobzheng|Jacobzheng]] ([[User talk:Jacobzheng|talk]]) 03:24, 3 September 2024 (UTC)

: Here are the transitions and description from Racheline:
<pre>
Σ(51) > (f_ε0)^8(f_ω^ω^3(a lot)) > f_ε0+1(8)
n0 = 21
n1 = 42
n2 = 46
M = (
((1, -1, 0), (0, -1, 1)),
((1, -1, 0), (1, 1, 2)),
((1, -1, 2), (0, -1, 4)),
((0, -1, 10), (1, -1, 4)),
((0, -1, 3), (0, -1, 5)),
((1, -1, 4), (1, 1, 6)),
((1, -1, 7), (0, -1, 15)),
((0, -1, 8), (1, -1, 7)),
((0, -1, 9), (1, -1, 7)),
((1, 1, 11), (1, -1, 9)),
((0, -1, 20), (0, -1, 17)),
((0, 1, 12), (1, 1, 11)),
((0, 1, 13), (1, 1, 13)),
((1, -1, 14), (1, 1, 12)),
((0, -1, 6), (1, -1, 10)),
((0, -1, 16), (1, -1, 16)),
((1, -1, 20), (1, -1, 15)),
((0, -1, 18), (1, -1, 18)),
((1, 1, 19), (1, -1, 17)),
((1, -1, 19), (1, -1, 20)),
((0, -1, n2 + 4), (0, -1, 21)),
((0, 1, n1 + 1), (0, -1, 9)),

((0, 1, n0 + 1), (1, 1, n0 + 2)),
((1, 1, n0 + 5), (0, -1, n0 + 3)),
((1, -1, n0 + 4), (0, -1, n0 + 3)),
((1, 1, n0 + 4), (1, 1, n0 + 1)),
((0, 1, n2 + 4), (0, 1, n0 + 6)),
((1, 1, n0 + 5), (1, -1, n0 + 14)),
((0, 1, n0 + 8), (0, 1, n0 + 9)),
((0, -1, 4), (1, 1, n0 + 7)),
((1, -1, n0 + 10), (1, -1, 0)),
((0, -1, n0 + 11), (1, -1, n0 + 12)),
((0, -1, n0 + 12), (1, -1, n0 + 10)),
((0, -1, n0 + 13), (0, -1, n0 + 14)),
((0, -1, n0 + 16), (1, -1, n0 + 12)),
((1, 1, n0 + 15), (1, 1, n0 + 17)),
((0, 1, n0 + 16), (1, 1, n0 + 7)),
((0, -1, n0 + 8), (1, 1, n0 + 15)),
((1, 1, n0 + 17), (1, 1, n0 + 18)),
((0, 1, n0 + 17), (1, 1, n0 + 19)),
((0, 1, n0 + 20), (1, -1, n0 + 21)),
((1, -1, n2 + 3), (1, 1, n0 + 19)),
((1, 1, n0 + 15), (0, -1, n0 + 21)),

((0, 1, n1 + 2), (1, 1, n1 + 2)),
((1, -1, n1 + 3), (1, 1, n1 + 1)),
((0, -1, n1 + 4), (1, -1, n1 + 4)),
((0, 1, n0 + 1), (1, -1, n1 + 3)),

((1, -1, n0 + 20), (1, -1, n2 + 1)),
((0, -1, n2 + 1), (0, -1, n2 + 3)),
((1, -1, n0 + 1), (1, -1, n2 + 2)),
((0, -1, n2 + 2), (1, 1, -1))
)

(start from state 30)
</pre>

: I haven't investigated it yet. [[User:Sligocki|Sligocki]] ([[User talk:Sligocki|talk]]) 14:27, 3 September 2024 (UTC)

:: It directly simulates Address Notation, which is a different way to write Primitive Sequence System (PrSS for short, it's 1-row Bashicu Matrix System). Here are the expansion rules of Address Notation:
::: Given a sequence <math>S</math> of natural numbers, to compute its expansion, start by letting <math>c</math> be the last element of <math>S</math>. If <math>c=0</math>, then <math>S</math> is a successor and its predecessor is <math>S</math> without the last element. Otherwise, find the last element <math>r</math> of <math>S</math> which is less than <math>c</math>. Decrease <math>c</math> by <math>1</math>, and let <math>B</math> be everything in this new sequence after <math>r</math>. Append infinitely many copies of <math>B</math>.
:: Since the sequences are ordered lexicographically and each element decreases by <math>1</math> until it is <math>0</math>, for any fundamental sequence system where each <math>S[n]</math> is formed by taking an initial subsequence of the expansion of <math>S</math> and changing the last element of that subsequence to a smaller or equal natural number, the ordinal notation given by the fundamental sequence system is the same. If i remember correctly, the TM simulates a variant <math>h</math> of the Hardy Hierarchy with a fundamental sequence system where the FS of each standard <math>S</math> contains all sequences longer than <math>S</math> formed this way from its expansion (except for the first one or two).
:: Specifically,
::: <math>h_0(n)=n+c_0</math>
::: <math>h_{\alpha+1}(n)=h_\alpha(n+c_1)</math>
::: <math>h_\alpha(n)=h_{\alpha[n]}(c_2)</math> for limit <math>\alpha</math>
::: <math>h_{\varepsilon_0}(n) = h_{(0,\lfloor\frac{n+c_3}{2}\rfloor)}(c_4) = h_{\omega\uparrow\uparrow\lfloor\frac{n+c_3}{2}\rfloor}(c_4)</math>
:: for some constants <math>c_0,c_1,c_2,c_3,c_4</math> for which the hierarchy is not degenerate (the constants can be deduced easily from the TM's space-time diagram). In particular, the non-degeneracy means that for most FGHs <math>f</math> with "natural" FS systems, we will have <math>f_{\alpha+1}(n)<h_{\omega^{\alpha+1}}(n+k)</math> for some small constant <math>k</math> (depending on <math>f</math>), and as long as the FGH's FS system has <math>\varepsilon_0[n]\le\omega\uparrow\uparrow(n+c)</math> for some constant <math>c</math>, we have <math>f_{\varepsilon_0}(n)<h_{\varepsilon_0}(2(n+c)+k)</math> for some small constant <math>k</math> (also depending on <math>f</math>. For example, the Wainer Hierarchy is one of these "natural" FGHs (and one of the most well-known ones at this level), and if we extend it to include <math>f_{\varepsilon_0}</math> and <math>f_{\varepsilon_0+1}</math> with the FS <math>\varepsilon_0[n]=\omega\uparrow\uparrow n</math>, it does indeed satisfy <math>f_{\varepsilon_0}(n)<h_{\varepsilon_0}(2n+k)</math> for small <math>k</math>, which means that since the TM computes <math>h_{\varepsilon_0}^8(n)</math> for a large <math>n</math>, its output is larger than <math>f_{\varepsilon_0+1}(8)</math>. [[User:Racheline|Racheline]] ([[User talk:Racheline|talk]]) 19:06, 3 September 2024 (UTC)

Champions

2024-09-02T14:04:32Z

Racheline: links to discoveries for large champions

Busy Beaver '''Champions''' are the current record holding [[Turing machine|Turing machines]] who maximize a [[Busy Beaver function]]. In this article we focus specifically on the longest running TMs. Some have been proven to be the longest running of all (and so are the ultimate champion) while others are only current champions and may be usurped in the future. For smaller domains, Pascal Michel's website is the canonical source for [https://bbchallenge.org/~pascal.michel/bbc Busy Beaver champions] and the [https://bbchallenge.org/~pascal.michel/ha History of Previous Champions].

== 2-Symbol TMs ==
Rows are blank if no champion has been found which surpasses a smaller size problem. Take also note that the <math> f_{x}(n) </math> used in the lowerbounds represent the [https://googology.fandom.com/wiki/Fast-growing_hierarchy Fast Growing Hierarchy].
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2)]]
|<math> 6 </math>
|{{TM|1RB1LB_1LA1RZ|halt}} {{TM|1RB0LB_1LA1RZ|halt}} {{TM|1RB1RZ_1LB1LA|halt}} {{TM|1RB1RZ_0LB1LA|halt}} {{TM|0RB1RZ_1LA1RB|halt}}
|Discovered and proven by hand by Tibor Radó
|-
|[[BB(3)]]
|<math> 21 </math>
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|Proven by Shen Lin
|-
|[[BB(4)]]
|<math> 107 </math>
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|Discovered and proven by Allen Brady
|-
|[[BB(5)]]
|<math> 47,176,870 </math>
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|Discovered by Heiner Marxen & Jürgen Buntrock in 1989
Proven by [[bbchallenge.org]] in 2024
|-
|[[BB(6)]]
|<math> > 10 \uparrow\uparrow 15 </math>
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}
|Discovered by Pavel Kropitz in 2022
|-
|[[BB(7)]]
|
|
|
|-
|BB(8)
|<math> > 2 \uparrow^5 4 > f_6(2) </math>
|{{TM|1RH1RF_0LC0LH_0RD1LC_0RE1RA_1RB1RE_1RZ1RG_1RF0RE_1LB1LH|halt}}
|Discovered by Racheline in 2024
|-
|BB(9)
|
|
|
|-
|BB(10)
|<math> > f_\omega^2(25) </math>
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ|halt}}
|Discovered by Racheline in 2024
|-
|BB(11)
|<math> > f_\omega^2(2 \uparrow\uparrow 12) > f_\omega^2(f_3(9)) </math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RZ0LI_0LD1LE|halt}}
|Discovered by Racheline in 2024
|-
|BB(12)
|<math> > f_\omega^4(2 \uparrow\uparrow\uparrow 4-3) > f_\omega^4(f_4(2)) </math>
|{{TM|0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_1RZ1LA_1RF1LL|halt}}
|Discovered by Racheline in 2024
|-
|BB(13)
|
|
|
|-
|BB(14)
|<math> > f_{\omega + 1}(65536) > g_{64} </math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM1RZ_0LN1LF_0LJ---|halt}}
|Discovered by Racheline in 2024
|-
|BB(15)
|
|
|
|-
|BB(16)
|<math> > f_{\omega + 1}(2 \uparrow\uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow\uparrow 9) </math>
|
|Designed by Daniel Nagaj in 2021<ref>Shawn Ligocki. 2022. "BB(16) > Graham's Number". https://www.sligocki.com/2022/07/11/bb-16-graham.html</ref>
|-
|BB(20)
|<math> > f_{\omega + 2}^2(21) </math>
|
|[https://discord.com/channels/960643023006490684/1026577255754903572/1274414683331366924 Discovered] by Racheline in 2024
|-
|BB(21)
|<math> > f_{\omega^2}^2(4 \uparrow\uparrow 341) </math>
|
|[https://discord.com/channels/960643023006490684/1026577255754903572/1274471360206344213 Discovered] by Racheline in 2024
|-
|BB(51)
|<math> > f_{\epsilon_0 + 1}(8) </math>
|
|[https://discord.com/channels/960643023006490684/1026577255754903572/1276881449685094495 Designed] by Racheline in 2024
|}

== 3-Symbol TMs ==

{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2,3)]]
|<math> 38 </math>
|{{TM|1RB2LB1RZ_2LA2RB1LB|halt}}
|
|-
|[[BB(3,3)]]
|<math> > 10^{17} </math>
|{{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}}
|-
|[[BB(4,3)]]
|<math> > 10^{14072} </math>
|{{TM|1RB1RZ2RC_2LC2RD0LC_1RA2RB0LB_1LB0LD2RC|halt}}
|
|}

== 4-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,4)
|<math> 3,932,964 </math>
|{{TM|1RB2LA1RA1RA_1LB1LA3RB1RZ|halt}}
|
|-
|BB(3,4)
|<math> > 2 \uparrow^{15} 5 </math>
|{{TM|1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC|halt}}
|
|}

== 5-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,5)
|<math> > 10^{10^{10^{3314360}}} </math>
|{{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ|halt}}
|
|-
|BB(3,5)
|<math> > f_\omega(2 \uparrow^{15} 5) > f_\omega^2(15) </math>
|{{TM|1RB3LB4LC2RA4LB_2LC3RB1LC2RA1RZ_3RB1LB3LC2RC4LC|halt}}
|
|}

== References ==
<references />

Champions

2024-09-02T13:58:28Z

Racheline: added BB(20), BB(21) and BB(3,5) bounds, champions for >3 symbols and made minor formatting changes for consistency

Busy Beaver '''Champions''' are the current record holding [[Turing machine|Turing machines]] who maximize a [[Busy Beaver function]]. In this article we focus specifically on the longest running TMs. Some have been proven to be the longest running of all (and so are the ultimate champion) while others are only current champions and may be usurped in the future. For smaller domains, Pascal Michel's website is the canonical source for [https://bbchallenge.org/~pascal.michel/bbc Busy Beaver champions] and the [https://bbchallenge.org/~pascal.michel/ha History of Previous Champions].

== 2-Symbol TMs ==
Rows are blank if no champion has been found which surpasses a smaller size problem. Take also note that the <math> f_{x}(n) </math> used in the lowerbounds represent the [https://googology.fandom.com/wiki/Fast-growing_hierarchy Fast Growing Hierarchy].
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2)]]
|<math> 6 </math>
|{{TM|1RB1LB_1LA1RZ|halt}} {{TM|1RB0LB_1LA1RZ|halt}} {{TM|1RB1RZ_1LB1LA|halt}} {{TM|1RB1RZ_0LB1LA|halt}} {{TM|0RB1RZ_1LA1RB|halt}}
|Discovered and proven by hand by Tibor Radó
|-
|[[BB(3)]]
|<math> 21 </math>
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|Proven by Shen Lin
|-
|[[BB(4)]]
|<math> 107 </math>
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|Discovered and proven by Allen Brady
|-
|[[BB(5)]]
|<math> 47,176,870 </math>
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|Discovered by Heiner Marxen & Jürgen Buntrock in 1989
Proven by [[bbchallenge.org]] in 2024
|-
|[[BB(6)]]
|<math> > 10 \uparrow\uparrow 15 </math>
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}
|Discovered by Pavel Kropitz in 2022
|-
|[[BB(7)]]
|
|
|
|-
|BB(8)
|<math> > 2 \uparrow^5 4 > f_6(2) </math>
|{{TM|1RH1RF_0LC0LH_0RD1LC_0RE1RA_1RB1RE_1RZ1RG_1RF0RE_1LB1LH|halt}}
|Discovered by Racheline in 2024
|-
|BB(9)
|
|
|
|-
|BB(10)
|<math> > f_\omega^2(25) </math>
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ|halt}}
|Discovered by Racheline in 2024
|-
|BB(11)
|<math> > f_\omega^2(2 \uparrow\uparrow 12) > f_\omega^2(f_3(9)) </math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RZ0LI_0LD1LE|halt}}
|Discovered by Racheline in 2024
|-
|BB(12)
|<math> > f_\omega^4(2 \uparrow\uparrow\uparrow 4-3) > f_\omega^4(f_4(2)) </math>
|{{TM|0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_1RZ1LA_1RF1LL|halt}}
|Discovered by Racheline in 2024
|-
|BB(13)
|
|
|
|-
|BB(14)
|<math> > f_{\omega + 1}(65536) > g_{64} </math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM1RZ_0LN1LF_0LJ---|halt}}
|Discovered by Racheline in 2024
|-
|BB(15)
|
|
|
|-
|BB(16)
|<math> > f_{\omega + 1}(2 \uparrow\uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow\uparrow 9) </math>
|
|Designed by Daniel Nagaj in 2021<ref>Shawn Ligocki. 2022. "BB(16) > Graham's Number". https://www.sligocki.com/2022/07/11/bb-16-graham.html</ref>
|-
|BB(20)
|<math> > f_{\omega + 2}^2(21) </math>
|
|Discovered by Racheline in 2024
|-
|BB(21)
|<math> > f_{\omega^2}^2(4 \uparrow\uparrow 341) </math>
|
|Discovered by Racheline in 2024
|-
|BB(51)
|<math> > f_{\epsilon_0 + 1}(8) </math>
|
|Designed by Racheline in 2024
|}

== 3-Symbol TMs ==

{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2,3)]]
|<math> 38 </math>
|{{TM|1RB2LB1RZ_2LA2RB1LB|halt}}
|
|-
|[[BB(3,3)]]
|<math> > 10^{17} </math>
|{{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}}
|-
|[[BB(4,3)]]
|<math> > 10^{14072} </math>
|{{TM|1RB1RZ2RC_2LC2RD0LC_1RA2RB0LB_1LB0LD2RC|halt}}
|
|}

== 4-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,4)
|<math> 3,932,964 </math>
|{{TM|1RB2LA1RA1RA_1LB1LA3RB1RZ|halt}}
|
|-
|BB(3,4)
|<math> > 2 \uparrow^{15} 5 </math>
|{{TM|1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC|halt}}
|
|}

== 5-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,5)
|<math> > 10^{10^{10^{3314360}}} </math>
|{{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ|halt}}
|
|-
|BB(3,5)
|<math> > f_\omega(2 \uparrow^{15} 5) > f_\omega^2(15) </math>
|{{TM|1RB3LB4LC2RA4LB_2LC3RB1LC2RA1RZ_3RB1LB3LC2RC4LC|halt}}
|
|}

== References ==
<references />

Talk:Champions

2024-08-17T23:08:29Z

Racheline:

Champions

2024-08-17T19:17:31Z

Racheline:

Busy Beaver '''Champions''' are the current record holding [[Turing machine|Turing machines]] who maximize a [[Busy Beaver function]]. In this article we focus specifically on the longest running TMs. Some have been proven to be the longest running of all (and so are the ultimate champion) while others are only current champions and may be usurped in the future. For smaller domains, Pascal Michel's website is the canonical source for [https://bbchallenge.org/~pascal.michel/bbc Busy Beaver champions] and the [https://bbchallenge.org/~pascal.michel/ha History of Previous Champions].

== 2-Symbol TMs ==
Rows are blank if no champion has been found which surpasses a smaller size problem. Take also note that the <math> f_{x}(n) </math> used in the lowerbounds represent the [https://googology.fandom.com/wiki/Fast-growing_hierarchy Fast Growing Hierarchy].
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2)]]
|6
|{{TM|1RB1LB_1LA1RZ|halt}} {{TM|1RB0LB_1LA1RZ|halt}} {{TM|1RB1RZ_1LB1LA|halt}} {{TM|1RB1RZ_0LB1LA|halt}} {{TM|0RB1RZ_1LA1RB|halt}}
|Discovered and proven by hand by Tibor Radó
|-
|[[BB(3)]]
|21
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|Proven by Shen Lin
|-
|[[BB(4)]]
|107
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|Discovered and proven by Allen Brady
|-
|[[BB(5)]]
|47,176,870
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|Discovered by Heiner Marxen & Jürgen Buntrock in 1989
Proven by [[bbchallenge.org]] in 2024
|-
|[[BB(6)]]
|<math>> 10 \uparrow\uparrow 15</math>
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}
|Discovered by Pavel Kropitz in 2022
|-
|[[BB(7)]]
|
|
|
|-
|BB(8)
|<math> > 2 \uparrow^5 4 > f_6(2) </math>
|{{TM|1RH1RF_0LC0LH_0RD1LC_0RE1RA_1RB1RE_1RZ1RG_1RF0RE_1LB1LH|halt}}
|Discovered by Racheline in 2024
|-
|BB(9)
|
|
|
|-
|BB(10)
|<math> > f_\omega^2(25) </math>
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ|halt}}
|Discovered by Racheline in 2024
|-
|BB(11)
|<math> > f_\omega^2(2 \uparrow\uparrow 12) > f_\omega^2(f_3(9)) </math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RZ0LI_0LD1LE|halt}}
|Discovered by Racheline in 2024
|-
|BB(12)
|<math> > f_\omega^4(2 \uparrow\uparrow\uparrow 4-3) > f_\omega^4(f_4(2)) </math>
|{{TM|0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_1RZ1LA_1RF1LL|halt}}
|Discovered by Racheline in 2024
|-
|BB(13)
|
|
|
|-
|BB(14)
|<math> > f_{\omega + 1}(65536) > g_{64} </math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM1RZ_0LN1LF_0LJ---|halt}}
|Discovered by Racheline in 2024
|-
|BB(15)
|
|
|
|-
|BB(16)
|<math> > f_{\omega + 1}(2 \uparrow\uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow\uparrow 9) </math>
|
|Designed by Daniel Nagaj in 2021<ref>Shawn Ligocki. 2022. "BB(16) > Graham's Number". https://www.sligocki.com/2022/07/11/bb-16-graham.html</ref>
|}

== 3-Symbol TMs ==

{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2,3)]]
|38
|{{TM|1RB2LB1RZ_2LA2RB1LB|halt}}
|
|-
|[[BB(3,3)]]
|<math> > 10^{17}</math>
|{{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}}
|-
|[[BB(4,3)]]
|<math> > 10^{14072} </math>
|{{TM|1RB1RZ2RC_2LC2RD0LC_1RA2RB0LB_1LB0LD2RC|halt}}
|
|}

== 4-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,4)
|<math>\geq3,932,964</math>
|
|
|-
|BB(3,4)
|<math>>2\uparrow^{15}5</math>
|
|
|}

== 5-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,5)
|<math>>10^{10^{10^{3314360}}}</math>
|
|
|}

== References ==
<references />

Champions

2024-08-17T14:22:24Z

Racheline: fixed starting state

Busy Beaver '''Champions''' are the current record holding [[Turing machine|Turing machines]] who maximize a [[Busy Beaver function]]. In this article we focus specifically on the longest running TMs. Some have been proven to be the longest running of all (and so are the ultimate champion) while others are only current champions and may be usurped in the future. For smaller domains, Pascal Michel's website is the canonical source for [https://bbchallenge.org/~pascal.michel/bbc Busy Beaver champions] and the [https://bbchallenge.org/~pascal.michel/ha History of Previous Champions].

== 2-Symbol TMs ==
Rows are blank if no champion has been found which surpasses a smaller size problem. Take also note that the <math> f_{x}(n) </math> used in the lowerbounds represent the [https://googology.fandom.com/wiki/Fast-growing_hierarchy Fast Growing Hierarchy].
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2)]]
|6
|{{TM|1RB1LB_1LA1RZ|halt}} {{TM|1RB0LB_1LA1RZ|halt}} {{TM|1RB1RZ_1LB1LA|halt}} {{TM|1RB1RZ_0LB1LA|halt}} {{TM|0RB1RZ_1LA1RB|halt}}
|Discovered and proven by hand by Tibor Radó
|-
|[[BB(3)]]
|21
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|Proven by Shen Lin
|-
|[[BB(4)]]
|107
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|Discovered and proven by Allen Brady
|-
|[[BB(5)]]
|47,176,870
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|Discovered by Heiner Marxen & Jürgen Buntrock in 1989
Proven by [[bbchallenge.org]] in 2024
|-
|[[BB(6)]]
|<math>> 10 \uparrow\uparrow 15</math>
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}
|Discovered by Pavel Kropitz in 2022
|-
|[[BB(7)]]
|
|
|
|-
|BB(8)
|<math> > 2 \uparrow^5 4 > f_6(2) </math>
|{{TM|1RH1RF_0LC0LH_0RD1LC_0RE1RA_1RB1RE_1RZ1RG_1RF0RE_1LB1LH|halt}}
|Discovered by Racheline in 2024
|-
|BB(9)
|
|
|
|-
|BB(10)
|<math> > f_\omega^2(25) </math>
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ|halt}}
|Discovered by Racheline in 2024
|-
|BB(11)
|<math> > f_\omega^2(2 \uparrow\uparrow 12) > f_\omega^2(f_3(9)) </math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_---0LI_0LD1LE|halt}}
|Discovered by Racheline in 2024
|-
|BB(12)
|<math> > f_\omega^4(2 \uparrow\uparrow\uparrow 4-3) > f_\omega^4(f_4(2)) </math>
|{{TM|0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_1RZ1LA_1RF1LL|halt}}
|Discovered by Racheline in 2024
|-
|BB(13)
|
|
|
|-
|BB(14)
|<math> > f_{\omega + 1}(65536) > g_{64} </math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM1RZ_0LN1LF_0LJ---|halt}}
|Discovered by Racheline in 2024
|-
|BB(15)
|
|
|
|-
|BB(16)
|<math> > f_{\omega + 1}(2 \uparrow\uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow\uparrow 9) </math>
|
|Designed by Daniel Nagaj in 2021<ref>Shawn Ligocki. 2022. "B(16) > Graham's Number". https://www.sligocki.com/2022/07/11/bb-16-graham.html</ref>
|}

== 3-Symbol TMs ==

{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2,3)]]
|38
|{{TM|1RB2LB1RZ_2LA2RB1LB|halt}}
|
|-
|[[BB(3,3)]]
|<math> > 10^{17}</math>
|{{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}}
|-
|[[BB(4,3)]]
|<math> > 10^{14072} </math>
|{{TM|1RB1RZ2RC_2LC2RD0LC_1RA2RB0LB_1LB0LD2RC|halt}}
|
|}

== 4-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,4)
|<math>\geq3,932,964</math>
|
|
|-
|BB(3,4)
|<math>>2\uparrow^{15}5</math>
|
|
|}

== 5-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,5)
|<math>>10^{10^{10^{3314360}}}</math>
|
|
|}

== References ==
<references />

Champions

2024-08-17T14:12:40Z

Racheline:

Busy Beaver '''Champions''' are the current record holding [[Turing machine|Turing machines]] who maximize a [[Busy Beaver function]]. In this article we focus specifically on the longest running TMs. Some have been proven to be the longest running of all (and so are the ultimate champion) while others are only current champions and may be usurped in the future. For smaller domains, Pascal Michel's website is the canonical source for [https://bbchallenge.org/~pascal.michel/bbc Busy Beaver champions] and the [https://bbchallenge.org/~pascal.michel/ha History of Previous Champions].

== 2-Symbol TMs ==
Rows are blank if no champion has been found which surpasses a smaller size problem. Take also note that the <math> f_{x}(n) </math> used in the lowerbounds represent the [https://googology.fandom.com/wiki/Fast-growing_hierarchy Fast Growing Hierarchy].
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2)]]
|6
|{{TM|1RB1LB_1LA1RZ|halt}} {{TM|1RB0LB_1LA1RZ|halt}} {{TM|1RB1RZ_1LB1LA|halt}} {{TM|1RB1RZ_0LB1LA|halt}} {{TM|0RB1RZ_1LA1RB|halt}}
|Discovered and proven by hand by Tibor Radó
|-
|[[BB(3)]]
|21
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|Proven by Shen Lin
|-
|[[BB(4)]]
|107
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|Discovered and proven by Allen Brady
|-
|[[BB(5)]]
|47,176,870
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|Discovered by Heiner Marxen & Jürgen Buntrock in 1989
Proven by [[bbchallenge.org]] in 2024
|-
|[[BB(6)]]
|<math>> 10 \uparrow\uparrow 15</math>
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}
|Discovered by Pavel Kropitz in 2022
|-
|[[BB(7)]]
|
|
|
|-
|BB(8)
|<math> > 2 \uparrow^5 4 > f_6(2) </math>
|{{TM|1RH1RF_0LC0LH_0RD1LC_0RE1RA_1RB1RE_1RZ1RG_1RF0RE_1LB1LH|halt}}
|Discovered by Racheline in 2024
|-
|BB(9)
|
|
|
|-
|BB(10)
|<math> > f_\omega^2(25) </math>
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ|halt}}
|Discovered by Racheline in 2024
|-
|BB(11)
|<math> > f_\omega^2(2 \uparrow\uparrow 12) > f_\omega^2(f_3(9)) </math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_---0LI_0LD1LE|halt}}
|Discovered by Racheline in 2024
|-
|BB(12)
|<math> > f_\omega^4(2 \uparrow\uparrow\uparrow 4-3) > f_\omega^4(f_4(2)) </math>
|{{TM|0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_1RZ1LA_1RF1LL|halt}}
|Discovered by Racheline in 2024
|-
|BB(13)
|
|
|
|-
|BB(14)
|<math> > f_{\omega + 1}(65536) > g_{64} </math>
|{{TM|1RB1RA_1LI1RG_0RD1LC_0RA1RE_1LJ0RA_1LH1LF_0LC1LH_0LC0LF_1LK1LJ_1RL0LI_0LL1LE_1LM1RZ_0LN1LA_0LJ---|halt}}
|Discovered by Racheline in 2024
|-
|BB(15)
|
|
|
|-
|BB(16)
|<math> > f_{\omega + 1}(2 \uparrow\uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow\uparrow 9) </math>
|
|Designed by Daniel Nagaj in 2021<ref>Shawn Ligocki. 2022. "B(16) > Graham's Number". https://www.sligocki.com/2022/07/11/bb-16-graham.html</ref>
|}

== 3-Symbol TMs ==

{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2,3)]]
|38
|{{TM|1RB2LB1RZ_2LA2RB1LB|halt}}
|
|-
|[[BB(3,3)]]
|<math> > 10^{17}</math>
|{{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}}
|-
|[[BB(4,3)]]
|<math> > 10^{14072} </math>
|{{TM|1RB1RZ2RC_2LC2RD0LC_1RA2RB0LB_1LB0LD2RC|halt}}
|
|}

== 4-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,4)
|<math>\geq3,932,964</math>
|
|
|-
|BB(3,4)
|<math>>2\uparrow^{15}5</math>
|
|
|}

== 5-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,5)
|<math>>10^{10^{10^{3314360}}}</math>
|
|
|}

== References ==
<references />

Champions

2024-08-17T14:12:03Z

Racheline: BB(14) > Graham's number

Busy Beaver '''Champions''' are the current record holding [[Turing machine|Turing machines]] who maximize a [[Busy Beaver function]]. In this article we focus specifically on the longest running TMs. Some have been proven to be the longest running of all (and so are the ultimate champion) while others are only current champions and may be usurped in the future. For smaller domains, Pascal Michel's website is the canonical source for [https://bbchallenge.org/~pascal.michel/bbc Busy Beaver champions] and the [https://bbchallenge.org/~pascal.michel/ha History of Previous Champions].

== 2-Symbol TMs ==
Rows are blank if no champion has been found which surpasses a smaller size problem. Take also note that the <math> f_{x}(n) </math> used in the lowerbounds represent the [https://googology.fandom.com/wiki/Fast-growing_hierarchy Fast Growing Hierarchy].
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2)]]
|6
|{{TM|1RB1LB_1LA1RZ|halt}} {{TM|1RB0LB_1LA1RZ|halt}} {{TM|1RB1RZ_1LB1LA|halt}} {{TM|1RB1RZ_0LB1LA|halt}} {{TM|0RB1RZ_1LA1RB|halt}}
|Discovered and proven by hand by Tibor Radó
|-
|[[BB(3)]]
|21
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|Proven by Shen Lin
|-
|[[BB(4)]]
|107
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|Discovered and proven by Allen Brady
|-
|[[BB(5)]]
|47,176,870
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|Discovered by Heiner Marxen & Jürgen Buntrock in 1989
Proven by [[bbchallenge.org]] in 2024
|-
|[[BB(6)]]
|<math>> 10 \uparrow\uparrow 15</math>
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}
|Discovered by Pavel Kropitz in 2022
|-
|[[BB(7)]]
|
|
|
|-
|BB(8)
|<math> > 2 \uparrow^5 4 > f_6(2) </math>
|{{TM|1RH1RF_0LC0LH_0RD1LC_0RE1RA_1RB1RE_1RZ1RG_1RF0RE_1LB1LH|halt}}
|Discovered by Racheline in 2024
|-
|BB(9)
|
|
|
|-
|BB(10)
|<math> > f_\omega^2(25) </math>
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ|halt}}
|Discovered by Racheline in 2024
|-
|BB(11)
|<math> > f_\omega^2(2 \uparrow\uparrow 12) > f_\omega^2(f_3(9)) </math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_---0LI_0LD1LE|halt}}
|Discovered by Racheline in 2024
|-
|BB(12)
|<math> > f_\omega^4(2 \uparrow\uparrow\uparrow 4-3) > f_\omega^4(f_4(2)) </math>
|{{TM|0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_1RZ1LA_1RF1LL|halt}}
|Discovered by Racheline in 2024
|-
|BB(13)
|
|
|
|-
|BB(14)
|<math> > f_{\omega + 1}(65536) > g_{64}
|{{TM|1RB1RA_1LI1RG_0RD1LC_0RA1RE_1LJ0RA_1LH1LF_0LC1LH_0LC0LF_1LK1LJ_1RL0LI_0LL1LE_1LM1RZ_0LN1LA_0LJ---|halt}}
|
|-
|BB(15)
|
|
|
|-
|BB(16)
|<math> > f_{\omega + 1}(2 \uparrow\uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow\uparrow 9) </math>
|
|Designed by Daniel Nagaj in 2021<ref>Shawn Ligocki. 2022. "B(16) > Graham's Number". https://www.sligocki.com/2022/07/11/bb-16-graham.html</ref>
|}

== 3-Symbol TMs ==

{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2,3)]]
|38
|{{TM|1RB2LB1RZ_2LA2RB1LB|halt}}
|
|-
|[[BB(3,3)]]
|<math> > 10^{17}</math>
|{{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}}
|-
|[[BB(4,3)]]
|<math> > 10^{14072} </math>
|{{TM|1RB1RZ2RC_2LC2RD0LC_1RA2RB0LB_1LB0LD2RC|halt}}
|
|}

== 4-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,4)
|<math>\geq3,932,964</math>
|
|
|-
|BB(3,4)
|<math>>2\uparrow^{15}5</math>
|
|
|}

== 5-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,5)
|<math>>10^{10^{10^{3314360}}}</math>
|
|
|}

== References ==
<references />

Champions

2024-08-17T13:01:40Z

Racheline: updated BB(11) and BB(12)

Busy Beaver '''Champions''' are the current record holding [[Turing machine|Turing machines]] who maximize a [[Busy Beaver function]]. In this article we focus specifically on the longest running TMs. Some have been proven to be the longest running of all (and so are the ultimate champion) while others are only current champions and may be usurped in the future. For smaller domains, Pascal Michel's website is the canonical source for [https://bbchallenge.org/~pascal.michel/bbc Busy Beaver champions] and the [https://bbchallenge.org/~pascal.michel/ha History of Previous Champions].

== 2-Symbol TMs ==
Rows are blank if no champion has been found which surpasses a smaller size problem. Take also note that the <math> f_{x}(n) </math> used in the lowerbounds represent the [https://googology.fandom.com/wiki/Fast-growing_hierarchy Fast Growing Hierarchy].
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2)]]
|6
|{{TM|1RB1LB_1LA1RZ|halt}} {{TM|1RB0LB_1LA1RZ|halt}} {{TM|1RB1RZ_1LB1LA|halt}} {{TM|1RB1RZ_0LB1LA|halt}} {{TM|0RB1RZ_1LA1RB|halt}}
|Discovered and proven by hand by Tibor Radó
|-
|[[BB(3)]]
|21
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|Proven by Shen Lin
|-
|[[BB(4)]]
|107
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|Discovered and proven by Allen Brady
|-
|[[BB(5)]]
|47,176,870
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|Discovered by Heiner Marxen & Jürgen Buntrock in 1989
Proven by [[bbchallenge.org]] in 2024
|-
|[[BB(6)]]
|<math>> 10 \uparrow\uparrow 15</math>
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}
|Discovered by Pavel Kropitz in 2022
|-
|[[BB(7)]]
|
|
|
|-
|BB(8)
|<math> > 2 \uparrow^5 4 > f_6(2) </math>
|{{TM|1RH1RF_0LC0LH_0RD1LC_0RE1RA_1RB1RE_1RZ1RG_1RF0RE_1LB1LH|halt}}
|Discovered by Racheline in 2024
|-
|BB(9)
|
|
|
|-
|BB(10)
|<math> > f_\omega^2(25) </math>
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ|halt}}
|Discovered by Racheline in 2024
|-
|BB(11)
|<math> > f_\omega^2(2 \uparrow\uparrow 12) > f_\omega^2(f_3(9)) </math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_---0LI_0LD1LE|halt}}
|Discovered by Racheline in 2024
|-
|BB(12)
|<math> > f_\omega^4(2 \uparrow\uparrow\uparrow 4-3) > f_\omega^4(f_4(2)) </math>
|{{TM|0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_1RZ1LA_1RF1LL|halt}}
|Discovered by Racheline in 2024
|-
|BB(13)
|
|
|
|-
|BB(14)
|
|
|
|-
|BB(15)
|
|
|
|-
|BB(16)
|<math> > f_{\omega + 1}(2 \uparrow\uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow\uparrow 9) > g_{64} </math>
|
|Designed by Daniel Nagaj in 2021<ref>Shawn Ligocki. 2022. "B(16) > Graham's Number". https://www.sligocki.com/2022/07/11/bb-16-graham.html</ref>
|}

== 3-Symbol TMs ==

{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2,3)]]
|38
|{{TM|1RB2LB1RZ_2LA2RB1LB|halt}}
|
|-
|[[BB(3,3)]]
|<math> > 10^{17}</math>
|{{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}}
|-
|[[BB(4,3)]]
|<math> > 10^{14072} </math>
|{{TM|1RB1RZ2RC_2LC2RD0LC_1RA2RB0LB_1LB0LD2RC|halt}}
|
|}

== 4-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,4)
|<math>\geq3,932,964</math>
|
|
|-
|BB(3,4)
|<math>>2\uparrow^{15}5</math>
|
|
|}

== 5-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,5)
|<math>>10^{10^{10^{3314360}}}</math>
|
|
|}

== References ==
<references />

Fast-Growing Hierarchy

2024-08-15T16:36:06Z

Racheline: explained FS systems

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 machines.

== Definition ==

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.

Given a system of fundamental sequences for limit ordinals below <math>\lambda</math>, its corresponding FGH is defined by

<math display="block">\begin{array}{l}
f_0(n) & = & n+1 \\
f_{\alpha+1}(n) & = & f_\alpha^n(n) & \text{for }\alpha<\lambda \\
f_\alpha(n) & = & f_{\alpha[n]}(n) & \text{for limit ordinals }\alpha<\lambda
\end{array}</math>

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

<math display="block">\begin{array}{l}
(\alpha+\omega^{\beta+1})[n] & = & \alpha+\omega^\beta n & \text{if }\alpha\text{ is a multiple of }\omega^{\beta+1} \\
(\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}
\end{array}</math>

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].

Champions

2024-08-15T14:33:06Z

Racheline: updated BB(8) and BB(9)

Champions

2024-08-15T13:00:06Z

Racheline: updated BB(10)

Champions

2024-08-15T10:49:41Z

Racheline: updated BB(9)

Champions

2024-08-15T02:51:12Z

Racheline:

Champions

2024-08-15T02:18:10Z

Racheline: much shorter and surprisingly close lower bound