BusyBeaverWiki - User contributions [en]

Champions

2025-05-10T10:45:27Z

DF476: /* 2-Symbol TMs */

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]. 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> > 10 \uparrow\uparrow 15 </math>
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}
|Pavel Kropitz in 2022
|[https://www.sligocki.com/2022/06/21/bb-6-2-t15.html Analysis by Shawn Ligocki]
|-
|[[BB(7)]]
|<math> > 10 \uparrow\uparrow 286 </math>
|{{TM|1RB1RF_0RC1RG_1LD1LE_0LE1LD_0RF0LC_1RA0LC_0RF1RZ|halt}}
|[https://discord.com/channels/960643023006490684/1369339127652159509/1370683302176096347 Terry Ligocki in 2025]
|
|-
|BB(8)
|<math> > 2 \uparrow^5 4 > f_6(2) </math>
|{{TM|1RH1RF_0LC0LH_0RD1LC_0RE1RA_1RB1RE_1RZ1RG_1RF0RE_1LB1LH|halt}}
|Racheline in 2024
|
|-
|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)
|
|
|
|
|-
|BB(16)
|<math> > f_{\omega + 1}(2 \uparrow\uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow\uparrow 9) </math>
|
|Daniel Nagaj in 2021
|[https://www.sligocki.com/2022/07/11/bb-16-graham.html Analysis by Shawn Ligocki]
|-
|BB(17)
|<math> > f_{\omega + 1}(f_\omega(60)) </math>
|[[User:Jacobzheng/BB(17)]]
|Jacobzheng in 2024
|
|-
|BB(18)
|<math> > f_{\omega + 1}(f_\omega^2(60)) </math>
|[[User:Jacobzheng/BB(18)]]
|Jacobzheng in 2024
|
|-
|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, Hiener 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)
|
|
|
|
|}

== References ==
<references />

Holdouts lists

2025-03-29T17:53:03Z

DF476: /* Downloadable Holdout Lists */

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
|4408
|-
!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]
|
|}

Holdouts lists

2025-03-29T17:50:45Z

DF476:

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
|4408
|-
!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]
|
|}

File:BB2x5 Coq holdouts 83.txt

2025-03-29T17:48:15Z

DF476:

User:DF476/BB2Zoology

2025-02-02T07:57:38Z

DF476: Created page with "I'm working on creating this page for the wiki. This is a complete Zoology for all 2×2 TMs, considering halting and non-halting (including free-halting TMs, that is, machines that don't have any undefined or halting transition) machines. All TNF machines are included so that <code>0RA---_------</code> and <code>0RB---_1LA1LA</code> are both valid options that are actually considered in this zoology. == Non-halting machines == In general, there are 130 machines, 106..."

I'm working on creating this page for the wiki.

This is a complete Zoology for all 2×2 TMs, considering halting and non-halting (including free-halting TMs, that is, machines that don't have any undefined or halting transition) machines. All TNF machines are included so that <code>0RA---_------</code> and <code>0RB---_1LA1LA</code> are both valid options that are actually considered in this zoology.

== Non-halting machines ==
In general, there are 130 machines, 106 of which are in TNF-1RB, 22 in TNF-0RB, and we also have <code>0RA---_------</code> and <code>1RA---_------</code>

=== Cyclers ===
There are 17 [[Cyclers]] in the 2×2 domain.

==== Record cyclers ====

* {{TM|1RB0RB_0LA---}}, one of the 8 cyclers with a record period of 4.
* {{TM|1RB1LB_1LA1RA}}, the pre-period champion with a pre-period of 5.

BB(2)

2024-11-18T06:13:42Z

DF476: /* Translated Cyclers */ I ended up using the preperiod definition from the wiki (which should be more genuine from a deciders perspective)

The 2-state 2-symbol Busy Beaver problem '''BB(2)''' was solved by Tibor Radó using pencil and paper and announced in his seminal Busy Beaver paper, On Non-Computable Functions.<ref>Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. <nowiki>https://doi.org/10.1002/j.1538-7305.1962.tb00480.x</nowiki></ref>

== Deciders ==
The only deciders needed to prove BB(2) are [[cycler]] and [[translated cycler]] deciders. All 26 infinite TMs listed below are either Translated Cyclers or Cyclers.

== Champions ==
S(2) = 6 and there are 5 shift champions in [[TNF]]:

* {{TM|1RB1LB_1LA1RZ|halt}} leaves 4 ones (the ones champion)
* {{TM|1RB0LB_1LA1RZ|halt}} leaves 3 ones
* {{TM|1RB1RZ_1LB1LA|halt}} leaves 3 ones
* {{TM|1RB1RZ_0LB1LA|halt}} leaves 2 ones
* {{TM|0RB1RZ_1LA1RB|halt}} leaves 2 ones

Σ(2) = 4 and there is one unique ones champion in TNF:

* {{TM|1RB1LB_1LA1RZ|halt}} runs for 6 steps (a shift champion)

== Enumeration ==
In [[TNF-1RB]] there are exactly 41 2-state, 2-symbol [[TM]]s, of which 15 halt and 26 never halt. The last group can be divided to 3 [[cycler]]s and 23 [[translated cycler]]s.

=== Halting TMs ===
The following TMs are ordered by the number of steps before halting and by the number of ones left in the tape (represented by the left and right numbers, respectively):

<pre>
1RB1LB_1LA1RZ Halt 6 4
1RB1RZ_1LB1LA Halt 6 3
1RB0LB_1LA1RZ Halt 6 3
1RB1RZ_0LB1LA Halt 6 2
1RB1LA_1LA1RZ Halt 5 3
1RB1LA_0LA1RZ Halt 5 2
1RB1RZ_1LB1RA Halt 4 2
1RB1RB_1LA1RZ Halt 4 2
1RB1RZ_1LB0RA Halt 4 1
1RB0RB_1LA1RZ Halt 4 1
1RB1RZ_1LA--- Halt 3 2
1RB---_1LB1RZ Halt 3 2
1RB1RZ_0LA--- Halt 3 1
1RB---_0LB1RZ Halt 3 1
1RB---_1RZ--- Halt 2 2
</pre>

=== Cyclers ===
The following TMs are ordered by the period and preperiod (represented by the left and right numbers, respectively):

<pre>
1RB0RB_0LA--- Cycler 4 0
1RB1RB_0LA--- Cycler 2 1
1RB---_0LB1RB Cycler 2 1
</pre>

=== Translated Cyclers ===
The following TMs are classified (in order of appereance) by their period, the preperiod and by the offset (in absolute value):<pre>
1RB1RA_1LA--- Translated Cycler 4 4 2
1RB1LB_0LA--- Translated Cycler 4 3 2
1RB0RA_1LA--- Translated Cycler 4 0 2
1RB0LB_0LA--- Translated Cycler 4 0 2
1RB1RA_0LA--- Translated Cycler 3 1 1
1RB---_1LB1RB Translated Cycler 3 1 1
1RB---_0LB1RA Translated Cycler 3 1 1
1RB---_0LB0LA Translated Cycler 3 0 1
1RB0RA_0LA--- Translated Cycler 3 0 1
1RB0LA_1LA--- Translated Cycler 3 0 1
1RB0LA_0LA--- Translated Cycler 3 0 1
1RB---_1LB0LA Translated Cycler 3 0 1
1RB---_0LB0RA Translated Cycler 3 0 1
1RB---_1RA--- Translated Cycler 2 2 2
1RB---_0RA--- Translated Cycler 2 1 2
1RB---_1LB0RB Translated Cycler 1 5 1
1RB---_1LB0LB Translated Cycler 1 4 1
1RB---_0LB1LB Translated Cycler 1 4 1
1RB---_1LB1LB Translated Cycler 1 3 1
1RB---_0LB0RB Translated Cycler 1 3 1
1RB---_0LB0LB Translated Cycler 1 3 1
1RB---_0RB--- Translated Cycler 1 2 1
1RB---_1RB--- Translated Cycler 1 1 1

</pre>

== References ==
<references />

BB(2)

2024-11-15T15:03:19Z

DF476: /* Enumeration */

The 2-state 2-symbol Busy Beaver problem '''BB(2)''' was solved by Tibor Radó using pencil and paper and announced in his seminal Busy Beaver paper, On Non-Computable Functions.<ref>Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. <nowiki>https://doi.org/10.1002/j.1538-7305.1962.tb00480.x</nowiki></ref>

== Deciders ==
The only decider needed to prove BB(2) is [[Translated Cycler]]. All 26 infinite TMs listed below are either Translated Cyclers or Cyclers.

== Champions ==
S(2) = 6 and there are 5 shift champions in [[TNF]]:

* {{TM|1RB1LB_1LA1RZ|halt}} leaves 4 ones (the ones champion)
* {{TM|1RB0LB_1LA1RZ|halt}} leaves 3 ones
* {{TM|1RB1RZ_1LB1LA|halt}} leaves 3 ones
* {{TM|1RB1RZ_0LB1LA|halt}} leaves 2 ones
* {{TM|0RB1RZ_1LA1RB|halt}} leaves 2 ones

Σ(2) = 4 and there is one unique ones champion in TNF:

* {{TM|1RB1LB_1LA1RZ|halt}} runs for 6 steps (a shift champion)

== Enumeration ==
In [[TNF-1RB]] there are exactly 41 2-state, 2-symbol [[TM]]s, of which 15 halt and 26 never halt. The last group can be divided to 3 [[Cycler|cyclers]] and 23 [[Translated Cycler|translated cyclers]].

=== Halting TMs ===
The following TMs are ordered by the number of steps before halting and by the number of ones left in the tape (represented by the left and right numbers, respectively).

<pre>
1RB1LB_1LA1RZ Halt 6 4
1RB1RZ_1LB1LA Halt 6 3
1RB0LB_1LA1RZ Halt 6 3
1RB1RZ_0LB1LA Halt 6 2
1RB1LA_1LA1RZ Halt 5 3
1RB1LA_0LA1RZ Halt 5 2
1RB1RZ_1LB1RA Halt 4 2
1RB1RB_1LA1RZ Halt 4 2
1RB1RZ_1LB0RA Halt 4 1
1RB0RB_1LA1RZ Halt 4 1
1RB1RZ_1LA--- Halt 3 2
1RB---_1LB1RZ Halt 3 2
1RB1RZ_0LA--- Halt 3 1
1RB---_0LB1RZ Halt 3 1
1RB---_1RZ--- Halt 2 2
</pre>

=== Cyclers ===
The following TMs are ordered by the period and preperiod (represented by the left and right numbers, respectively).

<pre>
1RB0RB_0LA--- Cycler 4 1
1RB1RB_0LA--- Cycler 2 1
1RB---_0LB1RB Cycler 2 1
</pre>

=== Translated Cyclers ===
<pre>
1RB1RA_1LA--- Translated Cycler
1RB1RA_0LA--- Translated Cycler
1RB1LB_0LA--- Translated Cycler
1RB0RA_1LA--- Translated Cycler
1RB0RA_0LA--- Translated Cycler
1RB0LB_0LA--- Translated Cycler
1RB0LA_1LA--- Translated Cycler
1RB0LA_0LA--- Translated Cycler
1RB---_1RB--- Translated Cycler
1RB---_1RA--- Translated Cycler
1RB---_1LB1RB Translated Cycler
1RB---_1LB1LB Translated Cycler
1RB---_1LB0RB Translated Cycler
1RB---_1LB0LB Translated Cycler
1RB---_1LB0LA Translated Cycler
1RB---_0RB--- Translated Cycler
1RB---_0RA--- Translated Cycler
1RB---_0LB1RA Translated Cycler
1RB---_0LB1LB Translated Cycler
1RB---_0LB0RB Translated Cycler
1RB---_0LB0RA Translated Cycler
1RB---_0LB0LB Translated Cycler
1RB---_0LB0LA Translated Cycler
</pre>

== References ==
<references />

User:DF476

2024-11-15T14:45:08Z

DF476:

I'm working this section for the BB(2) page, once it's been completed I would update it.

Classification of 2-state 2-symbol non-halting machines:

=== Cyclers ===
3 of the 26 non-halting TMs are [[Cycler|cyclers]]. The following list orders them by the period (the left number) and the preperiod (the right one).<pre>
1RB0RB_0LA--- CYCLER 4 1
1RB1RB_0LA--- CYCLER 2 1
1RB---_0LB1RB CYCLER 2 1
</pre>

=== Translated Cyclers ===
<pre>
1RB1RA_1LA---
1RB1RA_0LA---
1RB1LB_0LA---
1RB0RA_1LA---
1RB0RA_0LA---
1RB0LB_0LA---
1RB0LA_1LA---
1RB0LA_0LA---
1RB---_1RB---
1RB---_1RA---
1RB---_1LB1RB
1RB---_1LB1LB
1RB---_1LB0RB
1RB---_1LB0LB
1RB---_1LB0LA
1RB---_0RB---
1RB---_0RA---
1RB---_0LB1RA
1RB---_0LB1LB
1RB---_0LB0RB
1RB---_0LB0RA
1RB---_0LB0LB
1RB---_0LB0LA
</pre>

User:DF476

2024-11-15T06:30:11Z

DF476: Created page with "I'm working this section for the BB(2) page, once it's been completed I would update it. Classification of 2-state 2-symbol non-halting machines: === Cyclers === <pre> 1RB1RB_0LA--- 1RB0RB_0LA--- 1RB---_0LB1RB </pre> === Translated Cyclers === <pre> 1RB1RA_1LA--- 1RB1RA_0LA--- 1RB1LB_0LA--- 1RB0RA_1LA--- 1RB0RA_0LA--- 1RB0LB_0LA--- 1RB0LA_1LA--- 1RB0LA_0LA--- 1RB---_1RB--- 1RB---_1RA--- 1RB---_1LB1RB 1RB---_1LB1LB 1RB---_1LB0RB 1RB---_1LB0LB 1RB---_1LB0LA 1RB---_0RB-..."

I'm working this section for the BB(2) page, once it's been completed I would update it.

Classification of 2-state 2-symbol non-halting machines:

=== Cyclers ===
<pre>
1RB1RB_0LA---
1RB0RB_0LA---
1RB---_0LB1RB

</pre>

=== Translated Cyclers ===
<pre>
1RB1RA_1LA---
1RB1RA_0LA---
1RB1LB_0LA---
1RB0RA_1LA---
1RB0RA_0LA---
1RB0LB_0LA---
1RB0LA_1LA---
1RB0LA_0LA---
1RB---_1RB---
1RB---_1RA---
1RB---_1LB1RB
1RB---_1LB1LB
1RB---_1LB0RB
1RB---_1LB0LB
1RB---_1LB0LA
1RB---_0RB---
1RB---_0RA---
1RB---_0LB1RA
1RB---_0LB1LB
1RB---_0LB0RB
1RB---_0LB0RA
1RB---_0LB0LB
1RB---_0LB0LA
</pre>

BB(2)

2024-11-14T19:10:42Z

DF476:

Holdouts lists

2024-11-10T15:54:26Z

DF476:

Holdouts lists

2024-11-10T15:47:01Z

DF476:

File:3x3 holdout 6.txt

2024-11-10T15:45:11Z

DF476:

Holdouts lists

2024-11-10T15:35:23Z

DF476:

File:BB6 holdouts 4408.txt

2024-11-10T15:33:36Z

DF476:

Holdouts lists

2024-11-10T15:33:03Z

DF476: Perhaps someone could update the BB(2,5) and BB(3,3) holdouts lists.

Main Page

2024-07-13T16:56:18Z

DF476: Since BB(5) has been proven, now BB(5,3) forms part of the new Busy Beaver frontier.

The [[Busy Beaver function]] BB (called S originally) was introduced by [https://en.wikipedia.org/wiki/Tibor_Rad%C3%B3 Tibor Radó] in 1962 <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> for 2-symbol [[Turing machines]] and later generalised<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> to m-symbol Turing machines:

{| 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, and few of its values are known:

{| class="wikitable"
|+ Small busy beaver values <ref>https://bbchallenge.org/~pascal.michel/ha.html</ref> <ref name=":0">https://bbchallenge.org/</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>10 \uparrow \uparrow 15</math>
| style="background: orange;" | [[BB(7)]]
|-
| 3-symbol || [[BB(2,3)]] = 38
| style="background: orange;" | [[BB(3,3)]] > <math>10^{17}</math>
| style="background: #ffe4b2;" | [[BB(4,3)]] > <math>10^{14072}</math>
| style="background: #ffe4b2;" |[[BB(5,3)]]
| 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 + 14</math>
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
|-
| 5-symbol
| style="background: orange;" | [[BB(2,5)]] > 6.5 × <math>10^{38033}</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.

== bbchallenge.org ==
[[bbchallenge.org]] <ref name=":0" /> 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

Notably, as part of bbchallenge.org, in June 2024 the 5th busy beaver value [[BB(5)]] was proven in Coq to be equal to the lower bound found in 1989<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>: 47,176,870.

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