BusyBeaverWiki - User contributions [en]

1RB0LE 1LC1RA ---1LD 0RB1LF 1RD1LA 0LA0RD

2025-07-16T11:40:26Z

A6P457: Added non-halting

{{machine|1RB0LE_1LC1RA_---1LD_0RB1LF_1RD1LA_0LA0RD}}
{{TM|1RB0LE_1LC1RA_---1LD_0RB1LF_1RD1LA_0LA0RD|non}} is a non-halting [[BB(6)]] Turing machine.

Analysis by @racheline on 29 July 2024 ([https://discord.com/channels/960643023006490684/1239205785913790465/1267551868997992652 Discord link]):

<pre>
1RB0LE_1LC1RA_---1LD_0RB1LF_1RD1LA_0LA0RD
A(n) = 0^inf <A 0 1^n

rules:
A(6n) -> A(12n+3)
A(6n+1) -> A(12n+6)
A(6n+2) -> halt
A(6n+3) -> A(9n+9)
A(6n+4) -> halt
A(6n+5) -> A(9n+12)
start from A(3)

as we can see, everything that doesn't halt goes to A(6m) or A(6m+3) for some m, so halting is unreachable

the next two (1RB0LE_1LC1RA_---1LD_0RB1LF_1RD1LA_1RD0LA and 1RB0LE_1LC1RA_---1LD_0RB1LF_1RD1LA_0LA0LA) are clearly equivalent to it, so also non-halting
</pre>

Champions

2025-07-15T13:40:58Z

A6P457: added links

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 [[Fast-Growing Hierarchy]]. Note that most champions above 6 states are self-reported and have not been independently verified.

{| class="wikitable"
|+
!
!Runtime
!Champions
!Discovered By
!Verification
|-
|[[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}}
|Tibor Radó
|Direct Simulation
|-
|[[BB(3)]]
|<math> 21 </math>
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|Proven by Shen Lin
|Direct Simulation
|-
|[[BB(4)]]
|<math> 107 </math>
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|Allen Brady
|Direct Simulation
|-
|[[BB(5)]]
|<math> 47\,176\,870 </math>
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|Heiner Marxen & Jürgen Buntrock in 1989
|Direct Simulation
|-
|[[BB(6)]]
|<math> > 2\uparrow\uparrow\uparrow 5 </math>
|{{TM|1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE|halt}}
|mxdys in 2025
|See mxdys's analysis on the TM page
|-
|[[BB(7)]]
|<math>> 2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF|halt}}
|[https://discord.com/channels/960643023006490684/1369339127652159509/1370678203395604562 Pavel Kropitz in 2025]
|Analyzed by Shawn Ligocki (see TM page)
|-
|[[BB(8)]]
|
|
|
|
|-
|BB(9)
|<math> > f_\omega(f_9(2)) </math>
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_1LB0LH|halt}}
|Jacobzheng in 2024
|
|-
|BB(10)
|<math> > f_\omega^2(25) </math>
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ|halt}}
|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}}
|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}}
|Racheline in 2024
|
|-
|BB(13)
|
|
|
|
|-
|BB(14)
|<math> > f_{\omega + 1}(65\,536) > g_{64} </math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM1RZ_0LN1LF_0LJ---|halt}}
|[https://discord.com/channels/960643023006490684/960643023530762341/1274366178529120287 Racheline in 2024]
|
|-
|BB(15)
|<math> > f_{\omega + 1}(f_\omega(10^{57})) </math>
|{{TM|0RH1LD_1RI0RC_1RB1LD_0LD1LE_1LF1RA_1RG0LE_1RB1RG_1RD1RA_0LN0RJ_1RZ0LK_0LK1LL_1RG1LM_0LL0LL_1LO1LN_0LG1LN|halt}}
|Jacobzheng in 2025
|
|-
|BB(16)
|<math> > f_{\omega + 1}^2(10^{10^{57}}) </math>
|[[User:Jacobzheng/BB(16)]]
|Jacobzheng in 2025
|
|-
|BB(17)
|
|
|
|
|-
|BB(18)
|
|
|
|
|-
|BB(19)
|<math> > f_{\omega + 1}^3(f_\omega(60)) </math>
|[[User:Jacobzheng/BB(19)]]
|Jacobzheng in 2024
|
|-
|BB(20)
|<math> > f_{\omega + 2}^2(21) </math>
|
|[https://discord.com/channels/960643023006490684/1026577255754903572/1274414683331366924 Racheline in 2024]
|
|-
|BB(21)
|<math> > f_{\omega^2}^2(4 \uparrow\uparrow 341) </math>
|
|[https://discord.com/channels/960643023006490684/1026577255754903572/1274471360206344213 Racheline in 2024]
|
|-
|BB(40)
|<math> > f_{\omega^\omega}(75\,500) </math>
|[[User:Jacobzheng/BB(40)]]
|Jacobzheng in 2024
|
|-
|BB(41)
|<math> > f_{\omega^\omega}^4(32) </math>
|[[User:Jacobzheng/BB(41)]]
|Jacobzheng in 2024
|
|-
|BB(51)
|<math> > f_{\varepsilon_0 + 1}(8) </math>
|
|[https://discord.com/channels/960643023006490684/1026577255754903572/1276881449685094495 Racheline in 2024]
|
|}

== 3-Symbol TMs ==

{| class="wikitable"
|+
!
!Runtime
!Champions
!Discovered By
!Verification
|-
|[[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> > 2 \uparrow\uparrow\uparrow 2^{2^{32}}</math>
|{{TM|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}}
|
|
|}

== 4-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Discovered By
!Verification
|-
|[[BB(2,4)]]
|<math> 3\,932\,964 </math>
|{{TM|1RB2LA1RA1RA_1LB1LA3RB1RZ|halt}}
|Shawn & Terry Ligocki in 2005
|Pascal Michel, Heiner Marxen, Allen Brady
|-
|BB(3,4)
|<math> > 2 \uparrow^{15} 5 </math>
|{{TM|1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC|halt}}
|
|
|}

== 5-Symbol TMs ==
{| class="wikitable"
!
!Runtime
!Champions
!Discovered By
!Verification
|-
|[[BB(2,5)]]
|<math> > 10^{10^{10^{3\,314\,360}}} </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}}
|
|
|}

== 6-Symbol TMs ==
{| class="wikitable"
!
!Runtime
!Champions
!Discovered By
!Verification
|-
|BB(2,6)
|<math> > 10 \uparrow\uparrow 10 \uparrow\uparrow 10^{10^{115}} </math>
|{{TM|1RB3RB5RA1LB5LA2LB_2LA2RA4RB1RZ3LB2LA|halt}}
|
|
|}

Holdouts lists

2025-07-06T16:54:32Z

A6P457: BB(6)#Holdouts

A '''holdout''' (or undecided machine) is a [[Turing machine]] for which it is not known whether the machine halts or not from all-0 input tape. Holdouts are the machines which [[Decider|deciders]] are unable to decide.

Holdout lists are often shared by contributors. There is a [[#Downloadable Holdout Lists|Downloadable Holdout Lists]] table where people have added lists with no restriction or independent verification. For some of the entries there is a reference to a spreadsheet that documents what was run to achieve the result. For others, there is additional documentation on the specific BB pages.

The table with the "Number of holdouts" is based on the holdout lists listed in the table below it. Thus, some of these numbers have not been independently verified so they should be treated as such. All the zero entries, no holdouts, have been verified.

{| class="wikitable"
|+Number of holdouts
!
!2-state
!3-state
!4-state
!5-state
!6-state
|-
!2-symbol
|0
|0
|0
|0
|3335
|-
!3-symbol
|0
|6
|460,916,384
|
|
|-
!4-symbol
|0
|434,787,751
|
|
|
|-
!5-symbol
|83
|
|
|
|
|-
!6-symbol
|22,302,296
|
|
|
|
|}

== Downloadable Holdout Lists ==
{| class="wikitable sortable"
|+
!BB space
!Date
!Shared by
!Number of holdouts
!File
!Notes
|-
|[[BB(2,5)]]
|[https://discordapp.com/channels/960643023006490684/1259770421046411285/1355593937531961365, March 29 2025]
|@mxdys
|83
|
|-
|[[BB(4,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1320172124509311004 December 21, 2024]
|@tjligocki
|460,916,384
|[https://drive.google.com/file/d/1hKy0TuPuI62rN95j6ZLjXgE-Pue8tRsK/view?usp=drive_link 4x3_holdouts_460916384.txt.gz]
|[https://drive.google.com/drive/folders/1HBPZ17llVE_8wCy5FvRUFQ5MJsaYXAW-?usp=drive_link Google Drive directory for 4x3 TMs]
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1310648046576730124 November 25, 2024 (@icy)]
|@tjligocki
|4,319
|[https://docs.google.com/spreadsheets/d/1grhW_0neb2I8TfceN5-v70_3W42Z2U159r9L6FhPGf8/edit?usp=sharing Spreadsheet of holdouts]
|Keeping track of BB(6) progress - informal.
|-
|[[BB(3,3)]]
|November 10, 2024
|
|6
|[[:File:3x3 holdout 6.txt|3x3 holdout 6.txt]]
|
|-
|[[BB(6)]]
|[https://discordapp.com/channels/960643023006490684/1239205785913790465/1304303803213942846 November 8, 2024]
|@mxdys
|4,408
|[[:File:BB6 holdouts 4408.txt|BB6_holdouts_4408.txt]]
|
|-
|[[BB(2,6)]]
|[https://discord.com/channels/960643023006490684/960643023530762341/1303219184221683733 November 4, 2024]
|@tjligocki
|22,302,296
|[https://drive.google.com/file/d/1xRLIjdiqImFP2SL38gvhxVlAaX0L1cYO/view?usp=drive_link 2x6_holdouts_22302296.txt.gz]
|[https://drive.google.com/drive/folders/1p9b5g-Id3WEMUYIwEnaKWRBGIW66ADjM?usp=drive_link Google Drive directory for 2x6 TMs]
|-
|[[BB(3,4)]]
|[https://discord.com/channels/960643023006490684/960643023530762341/1302767449476694188 November 3, 2024]
|@tjligocki
|434,787,751
|[https://drive.google.com/file/d/1PLzN3wLw-MRgk1OFmYh4RTwNc30nflR7/view?usp=drive_link 3x4_holdouts_434787751.txt.gz]
|[https://drive.google.com/drive/folders/1bZxl7jg5q9IVvHQNZwItx1kPusAWznZk?usp=drive_link Google Drive directory for 3x4 TMs]
|-
|[[BB(6)]]
|[https://discordapp.com/channels/960643023006490684/1239205785913790465/1280185195877634098 September 2, 2024]
|@mxdys
|5394
|[[:File:BB6 holdouts 5394.txt]]
|
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1269612923127599164 August 4, 2024]
|@mxdys
|5877
|[[:File:BB6 holdouts 5877.txt]]
|
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1259131753176498216 July 6, 2024]
|@mxdys
|7296
|[[:File:BB6 holdouts 7296.txt]]
|
|-
|[[BB(2,5)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1252989316175499284 June 19, 2024]
|@mxdys
|217
|[[:File:2x5_holdouts_217.txt]]
|273 holdouts minus machines solved by CTL
|-
|[[BB(2,5)]]
|June 15th 2024
|@dyuan01
| 273
|[[:File:2x5_holdouts_273.txt]]
|@Justin Blanchard's 499 holdouts minus machines solved by @mxdys
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1250895665719148595 June 13, 2024]
|@tjligocki
| 12,091
|[[:File:BB6 holdouts 12091.txt]]
|Work done with @Shawn Ligocki
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1249142547217907772 June 9, 2024]
|@Justin Blanchard
|22
|[[:File:3x3.todo.txt]], [[:File:Mugshots small.pdf]]
|
|-
|BB(6)
|[https://discord.com/channels/960643023006490684/1239205785913790465/1248708916381220954 June 7, 2024]
|@mxdys
|12,325
|[[:File:BB6 holdouts 12325.txt]]
|Some equivalent machines are removed.
|-
|[[BB(5)]]
|June 2024
|BBChallenge
|0
|
|'''BB(5) is SOLVED!'''
|-
|[[BB(2,5)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1242679236142170203 May 22, 2024]
|@Justin Blanchard
|499
|[[:File:2x5.todo.txt]]
|
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1116351783040716830 June 8, 2023]
|@Iijil
|925
|[[:File:2023 06 08.3x3.holdouts intersect sligocki iijil 925.txt]]
|Intersection of @sligocki and @Iijil from below
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1116351783040716830 June 8, 2023]
|@Iijil
|2,480
|[[:File:2023 06 08.3x3.holdouts iijil 2380.txt]]
|
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1116178334620070000 June 7, 2023]
|@sligocki
|2,417
|[[:File:2023 06 07.3x3.holdouts 2417.txt]]
|
|-
|[[BB(6)]]
|May 27, 2023
|@sligocki
|181,851
|[https://drive.google.com/file/d/1YNwFCN6XJeDNKxxK5KbGHOAFOdIBvDb6/view?usp=drive_link 6x2.holdouts_181851.txt.gz]
|This was posted to the BBChallenge Forum (before Discord)
|-
|[[BB(6)]]
|May 10, 2023
|@sligocki
|1,458,704
|[https://drive.google.com/file/d/14bDnBt0OwuHATFBiubc_5jub0220EyXf/view?usp=drive_link 6x2.holdouts_1458704.txt.gz]
|This was posted to the BBChallenge Forum (before Discord)
|-
|[[BB(5)]]
|[https://skelet.ludost.net/bb/nreg.html circa May 13th, 2003]
|Georgi Georgiev (Skelet)
|43
|[https://bbchallenge.org/skelet List of 43 holdouts]
|
|}

Main Page

2025-07-06T16:25:07Z

A6P457: Champions

The [[Busy Beaver function]] BB (called ''S'' originally) was introduced by [https://en.wikipedia.org/wiki/Tibor_Rad%C3%B3 Tibor Radó] in 1962 for 2-symbol [[Turing machines]] and later generalised to ''m''-symbol Turing machines:<ref>Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. https://doi.org/10.1002/j.1538-7305.1962.tb00480.x</ref><ref>Brady, Allen H, and the Meaning of Life, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey (Oxford, 1990; online edn, Oxford Academic, 31 Oct. 2023), https://doi.org/10.1093/oso/9780198537748.003.0009, accessed 8 June 2024.</ref>

{| class="wikitable"
|-
| BB(''n'', ''m'') = Maximum number of steps taken by a halting ''n''-state, ''m''-symbol Turing machine starting from a blank (all 0) tape
|}

The 2-symbol case BB(''n'', 2) is abbreviated as BB(''n''). The busy beaver function is not computable, but a few of its values are known:

{| class="wikitable"
|+ Small busy beaver values<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref>
! !!2-state!!3-state !!4-state!!5-state!!6-state
!7-state
|-
! 2-symbol
| [[BB(2)]] = 6
| [[BB(3)]] = 21
| [[BB(4)]] = 107
| [[BB(5)]] = 47,176,870
| style="background: orange;" | [[BB(6)]] > <math>2 \uparrow \uparrow \uparrow 5</math>
| style="background: #ffe4b2;" | [[BB(7)]] > <math>2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|-
! 3-symbol
| [[BB(2,3)]] = 38
| style="background: orange;" | [[BB(3,3)]] > <math>10^{17}</math>
| style="background: #ffe4b2;" | [[BB(4,3)]] > <math>2 \uparrow\uparrow\uparrow 2^{2^{32}}</math>
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
|-
! 4-symbol
| [[BB(2,4)]] = 3,932,964
| style="background: #ffe4b2;" | [[BB(3,4)]] > <math>2 \uparrow^{15} 5</math>
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
|-
! 5-symbol
| style="background: orange;" | [[BB(2,5)]] > <math>10\uparrow\uparrow 4</math>
| style="background: #ffe4b2;" | [[BB(3,5)]] > <math> f_\omega(2 \uparrow^{15} 5)</math>
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
|-
! 6-symbol
| style="background: #ffe4b2;" | [[BB(2,6)]] > <math>10 \uparrow\uparrow\uparrow 3</math>
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
|}

In the above table, <span style="background: orange">cells are highlighted in orange</span> when there are known [[Cryptids]] (mathematically-hard machines) in that class, and <span style="background: #ffe4b2">cells are highlighted in light orange</span> when the existence of a Cryptid is given by using a known one with less states or symbols.

== About bbchallenge ==
[https://www.bbchallenge.org bbchallenge] is a massively collaborative research project whose general goal is to obtain more knowledge on the [[Busy Beaver function]]. In practice, it mainly consists in collaboratively building [[Deciders]], programs that automatically prove that some Turing machines do not halt. Other efforts also include:

* Formalising results using theorem provers (such as [https://en.wikipedia.org/wiki/Coq_(software) Coq])
* Maintaining [[Holdouts lists]] for small busy beaver values
* Proving the behavior of [[:Category:Individual Machines|Individual machines]]
* Finding [[Cryptids]] (mathematically-hard machines)
* Searching for new [[Champions]]
* Building [[Accelerated Simulator]]s to simulate halting machines faster
* Writing papers and giving talks about busy beaver, see [[Papers & Talks]]

In June 2024, bbchallenge achieved a significant milestone by proving in Coq / Rocq that the 5th busy beaver value, [[BB(5)]], is equal to the lower bound found in 1989: 47,176,870.<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5.
Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref>

== Contribute to this wiki ==
This wiki is collaborative, feel free to contribute by editing existing pages or creating new ones:

<inputbox>
type=create
width=100
break=no
buttonlabel=Create new article
default=(Article title)
</inputbox>

==Notes==
<references />