Holdouts lists: Difference between revisions
Jump to navigation
Jump to search
(Adding more to the BB 3x3 holdout history.) |
(BB(4,3) table, will sort out list entry tomorrow) |
||
| (43 intermediate revisions by 11 users not shown) | |||
| 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 yet 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. | 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. All the zero entries (no remaining holdouts) have been verified. | |||
{| class="wikitable" | {| class="wikitable" | ||
|+Number of holdouts | |+Number of holdouts | ||
| Line 12: | Line 13: | ||
!5-state | !5-state | ||
!6-state | !6-state | ||
!7-state | |||
|- | |- | ||
!2-symbol | !2-symbol | ||
| Line 18: | Line 20: | ||
|0 | |0 | ||
|0 | |0 | ||
| | |1,691 | ||
|22,721,168 | |||
|- | |- | ||
!3-symbol | !3-symbol | ||
|0 | |0 | ||
|6 | |6 | ||
| | |40,836,159 | ||
| | |||
| | | | ||
| | | | ||
| Line 29: | Line 33: | ||
!4-symbol | !4-symbol | ||
|0 | |0 | ||
| | |64,777,377 | ||
| | |||
| | | | ||
| | | | ||
| Line 35: | Line 40: | ||
|- | |- | ||
!5-symbol | !5-symbol | ||
| | |75 | ||
| | |||
| | | | ||
| | | | ||
| Line 42: | Line 48: | ||
|- | |- | ||
!6-symbol | !6-symbol | ||
| | |873,469 | ||
| | |||
| | | | ||
| | | | ||
| Line 58: | Line 65: | ||
!File | !File | ||
!Notes | !Notes | ||
|- | |||
|[[BB(3,4)]] | |||
|[https://drive.google.com/drive/folders/1_5j19qrvo1q7jN_c0pYnjBOrIXAP6b7i October 4th, 2025] | |||
|@tjligocki | |||
|64,777,377 | |||
|[https://drive.google.com/file/d/1I3s3w-T4NPLn-eCdaZLPgC2Mya51pyvH/view?usp=drive_link 3x4_holdouts_64777377.txt.gz] | |||
|Work done by [[User:XnoobSpeakable|XnoobSpeakable]] and [[User:WarpedWartWars|Lúkos]]. | |||
|- | |||
|[[BB(2,6)]] | |||
|[https://drive.google.com/drive/folders/1TsSpW27x3LBlu5qmk-cjzCJzgo_3ehyT September 22nd, 2025] | |||
|@tjligocki | |||
|873,469 | |||
|[http://2x6_holdouts_873469.txt.zip 2x6_holdouts_873469.txt.zip] | |||
|Work done by Andrew Ducharme. | |||
|- | |||
|[[BB(6)]] | |||
|[https://discord.com/channels/960643023006490684/1239205785913790465/1411308408220549140 August 30 2025] | |||
|@mxdys | |||
|2,592 | |||
|[[:File:BB6 holdouts 2592.txt|BB6 holdouts 2592.txt]] | |||
|- | |||
|[[BB(6)]] | |||
|[https://discord.com/channels/960643023006490684/1239205785913790465/1399783936019664896 July 29 2025] | |||
|@mxdys | |||
|2,728 | |||
|[[:File:BB6 holdouts 2728.txt|BB6 holdouts 2728.txt]] | |||
| | |||
|- | |||
|[[BB(2,5)]] | |||
|[https://discord.com/channels/960643023006490684/1259770421046411285/1355593937531961365 March 29 2025] | |||
|@mxdys | |||
|83 | |||
|[[:File:BB2x5 Coq holdouts 83.txt]] | |||
| | |||
|- | |- | ||
|[[BB(4,3)]] | |[[BB(4,3)]] | ||
| Line 121: | Line 162: | ||
|[[:File:BB6 holdouts 7296.txt]] | |[[: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)]] | |[[BB(2,5)]] | ||
| Line 183: | Line 231: | ||
|2,417 | |2,417 | ||
|[[:File:2023 06 07.3x3.holdouts 2417.txt]] | |[[:File:2023 06 07.3x3.holdouts 2417.txt]] | ||
| | | | ||
|- | |- | ||
| Line 205: | Line 246: | ||
|[https://drive.google.com/file/d/14bDnBt0OwuHATFBiubc_5jub0220EyXf/view?usp=drive_link 6x2.holdouts_1458704.txt.gz] | |[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) | |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] | |||
| | |||
|} | |} | ||
Revision as of 18:59, 4 October 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 yet 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.
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. All the zero entries (no remaining holdouts) have been verified.
| 2-state | 3-state | 4-state | 5-state | 6-state | 7-state | |
|---|---|---|---|---|---|---|
| 2-symbol | 0 | 0 | 0 | 0 | 1,691 | 22,721,168 |
| 3-symbol | 0 | 6 | 40,836,159 | |||
| 4-symbol | 0 | 64,777,377 | ||||
| 5-symbol | 75 | |||||
| 6-symbol | 873,469 |