Holdouts lists: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older editNewer edit →
VisualWikitext
ADucharme (talk | contribs)
284 edits
→Downloadable Holdout Lists: trying to add txt file of 217 holdout list
Tjligocki (talk | contribs)
264 edits
Removed the section (and tables) that were attempting to document how someone could attain some of the holdout lists. This is being moved to the wiki page for the specific BB domain.
Line 1: Line 1:
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.
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. After that table are several tables, [[#Verifiable Holdout Lists|Verifiable Holdout Lists]], that attempt to document a reproducible path from the initial enumeration of TMs of a given size tracking the holdout lists.
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.


Here is a table that summarises the number of holdout per busy beaver domain based on the Downloadable Holdout Lists:
{| class="wikitable"
{| class="wikitable"
|+Number of holdouts
|+Number of holdouts
Line 214: Line 213:
|}
|}
Georgi Georgiev (Skelet) posted [https://skelet.ludost.net/bb/nreg.html a list of 43 holdouts] for BB(5) in 2003. bbchallenge.org successfully reduced the number of holdouts for BB(5) to zero in June 2024.
Georgi Georgiev (Skelet) posted [https://skelet.ludost.net/bb/nreg.html a list of 43 holdouts] for BB(5) in 2003. bbchallenge.org successfully reduced the number of holdouts for BB(5) to zero in June 2024.
== Verifiable Holdout Lists ==
=== BB(3,3) ===
{| class="wikitable sortable"
|+
!Date
!Shared by
!Number of holdouts
!Holdout TMs
!Decided TMs
!Notes
|-
|[https://discord.com/channels/960643023006490684/1259770474897080380/1333364755011731456 January 27, 2025]
|@tjligocki
|367
|[[:File:3x3.unk.sort.txt|3x3.unk.sort.txt]]
|For halting and infinte TMs see [https://drive.google.com/drive/folders/101U9htddFdE889agAZnU58VLgQJlfn0v?usp=drive_link Google Drive directory for 3x3 TMs]
|Initial pass at generating a verified holdout list using software from [https://github.com/sligocki/busy-beaver Shawn's BB Github]. See [https://docs.google.com/spreadsheets/d/1PU386wH1wcOpSAhU5BjJqkub7YJv5cRQ/edit?usp=drive_link&ouid=101141952239004788549&rtpof=true&sd=true spreadsheet]. This a subset of the holdouts generated by @sligocki below.
|-
|[https://discord.com/channels/960643023006490684/1084047886494470185/1116351783040716830 June 8, 2023]
|@Iijil
|925
|[[:File:2023 06 08.3x3.holdouts intersect sligocki iijil 925.txt]]
|Derived from TMs in the holdouts generated by @sligocki and @Iijil, see below.
|Intersection of @sligocki and @Iijil from below.
|-
|[https://discord.com/channels/960643023006490684/1084047886494470185/1116351783040716830 June 8, 2023]
|@Iijil
|2,480
|[[:File:2023 06 08.3x3.holdouts iijil 2380.txt]]
|Unknown
|Still gathering information on how this was generated.
|-
|[https://discord.com/channels/960643023006490684/1084047886494470185/1116178334620070000 June 7, 2023]
|@sligocki
|2,417
|[[:File:2023 06 07.3x3.holdouts 2417.txt]]
|Unknown
|Initial pass at generating a verified holdout using software from [https://github.com/sligocki/busy-beaver Shawn's BB Github].
|-
|}

Revision as of 06:53, 28 February 2025

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 deciders are unable to decide.

Holdout lists are often shared by contributors. There is a 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.

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 273
6-symbol 22,302,296

Downloadable Holdout Lists

BB space Date Shared by Number of holdouts File Notes
BB(4,3) December 21, 2024 @tjligocki 460,916,384 4x3_holdouts_460916384.txt.gz Google Drive directory for 4x3 TMs
BB(6) November 25, 2024 (@icy) @tjligocki 4,319 Spreadsheet of holdouts Keeping track of BB(6) progress - informal.
BB(3,3) November 10, 2024 6 3x3 holdout 6.txt
BB(6) November 8, 2024 @mxdys 4,408 BB6_holdouts_4408.txt
BB(2,6) November 4, 2024 @tjligocki 22,302,296 2x6_holdouts_22302296.txt.gz Google Drive directory for 2x6 TMs
BB(3,4) November 3, 2024 @tjligocki 434,787,751 3x4_holdouts_434787751.txt.gz Google Drive directory for 3x4 TMs
BB(6) September 2, 2024 @mxdys 5394 File:BB6 holdouts 5394.txt
BB(6) August 4, 2024 @mxdys 5877 File:BB6 holdouts 5877.txt
BB(6) July 6, 2024 @mxdys 7296 File:BB6 holdouts 7296.txt
BB(2,5) 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) June 13, 2024 @tjligocki 12,091 File:BB6 holdouts 12091.txt Work done with @Shawn Ligocki
BB(3,3) June 9, 2024 @Justin Blanchard 22 File:3x3.todo.txt, File:Mugshots small.pdf
BB(6) 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) May 22, 2024 @Justin Blanchard 499 File:2x5.todo.txt
BB(3,3) 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) June 8, 2023 @Iijil 2,480 File:2023 06 08.3x3.holdouts iijil 2380.txt
BB(3,3) June 7, 2023 @sligocki 2,417 File:2023 06 07.3x3.holdouts 2417.txt
BB(5) circa May 13th, 2003 Georgi Georgiev (Skelet) 43 List of 43 holdouts
BB(6) May 27, 2023 @sligocki 181,851 6x2.holdouts_181851.txt.gz This was posted to the BBChallenge Forum (before Discord)
BB(6) May 10, 2023 @sligocki 1,458,704 6x2.holdouts_1458704.txt.gz This was posted to the BBChallenge Forum (before Discord)

Georgi Georgiev (Skelet) posted a list of 43 holdouts for BB(5) in 2003. bbchallenge.org successfully reduced the number of holdouts for BB(5) to zero in June 2024.

Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=Holdouts_lists&oldid=1602"