Holdouts lists: Difference between revisions
Jump to navigation
Jump to search
Updated number of BB(7) holdouts and removed BB(4,3) holdout number which was affected by bugs |
Qwertyasdf (talk | contribs) Editing prose for clarity; hope I explained TNF correctly |
||
| (34 intermediate revisions by 5 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 yet 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. Contributors have shared lists of holdouts. Some lists exclude known equivalent machines, i.e., machines whose halting status is implied by the halting status of another machine. If a holdout machine with more than one undefined transitions is found to reach a undefined transition, the number of holdouts may increase as a consequence of [[Tree Normal Form|TNF enumeration]]. | ||
{| class="wikitable" | {| class="wikitable" | ||
| Line 20: | Line 16: | ||
|0 | |0 | ||
|0 | |0 | ||
| | |1326 | ||
| | |20,197,978 | ||
|- | |- | ||
!3-symbol | !3-symbol | ||
|0 | |0 | ||
| | |4 | ||
| | |9,401,447 | ||
| | | | ||
| | | | ||
| Line 33: | Line 29: | ||
!4-symbol | !4-symbol | ||
|0 | |0 | ||
| | |12,435,284 | ||
| | | | ||
| | | | ||
| Line 48: | Line 44: | ||
|- | |- | ||
!6-symbol | !6-symbol | ||
| | |870,085 | ||
| | | | ||
| | | | ||
| Line 57: | Line 53: | ||
== Downloadable Holdout Lists == | == Downloadable Holdout Lists == | ||
This is a 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. | |||
{| class="wikitable sortable" | {| class="wikitable sortable" | ||
|+ | |+ | ||
| Line 65: | Line 62: | ||
!File | !File | ||
!Notes | !Notes | ||
|- | |||
|[[BB(6)]] | |||
|December 30th, 2025 | |||
|@mxdys | |||
|1326 | |||
|[https://wiki.bbchallenge.org/w/images/f/f0/BB6_holdouts_1326.txt BB6_holdouts_1326.txt] | |||
| | |||
|- | |||
|[[BB(6)]] | |||
|November 22nd, 2025 | |||
|Robin Rovenszky | |||
|Variable (1325) | |||
|[https://docs.google.com/spreadsheets/d/1mMp8bAcTFT91j7azn72liX8NSTwc2E_ozKnOGTfRCfw/edit?gid=1330361301#gid=1330361301 Google Sheets] | |||
|Annotated list, including links to Discord discussions, always up-to-date. | |||
|- | |||
|[[BB(6)]] | |||
|December 16th, 2025 | |||
|@mxdys | |||
|1343 | |||
|[https://wiki.bbchallenge.org/w/images/9/9a/BB6_holdouts_classified_1343.txt BB6_holdouts_1343.txt] | |||
| | |||
|- | |||
|[[BB(6)]] | |||
|November 28th, 2025 | |||
|@mxdys | |||
|1416 | |||
|[https://wiki.bbchallenge.org/w/images/9/98/BB6_holdouts_1416.txt BB6_holdouts_1416.txt] | |||
| | |||
|- | |||
|[[BB(6)]] | |||
|November 14th, 2025 | |||
|@mxdys | |||
|1534 | |||
|[https://wiki.bbchallenge.org/w/images/0/02/BB6_holdouts_1534.txt BB6_holdouts_1534.txt] | |||
| | |||
|- | |||
|[[BB(6)]] | |||
|October 20th, 2025 | |||
|@mxdys | |||
|1618 | |||
|[https://wiki.bbchallenge.org/w/images/e/e3/BB6_holdouts_1618.txt BB6 holdouts 1618.txt] | |||
| | |||
|- | |||
|[[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(7)]] | |||
|[https://discord.com/channels/960643023006490684/1369339127652159509/1423806362072256676 October 4th, 2025] | |||
|Andrew Ducharme | |||
|22,721,168 | |||
|[https://drive.google.com/file/d/1xAFSPh6qAR8VxsF4QVipmdc0UpdPC1hn/view bb7_holdouts_22721168.txt.zip] | |||
| | |||
|- | |||
|[[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)]] | |[[BB(6)]] | ||
| Line 84: | Line 144: | ||
|83 | |83 | ||
|[[:File:BB2x5 Coq holdouts 83.txt]] | |[[:File:BB2x5 Coq holdouts 83.txt]] | ||
| | |||
|- | |- | ||
|[[BB(4,3)]] | |[[BB(4,3)]] | ||
Latest revision as of 08:14, 14 January 2026
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. Contributors have shared lists of holdouts. Some lists exclude known equivalent machines, i.e., machines whose halting status is implied by the halting status of another machine. If a holdout machine with more than one undefined transitions is found to reach a undefined transition, the number of holdouts may increase as a consequence of TNF enumeration.
| 2-state | 3-state | 4-state | 5-state | 6-state | 7-state | |
|---|---|---|---|---|---|---|
| 2-symbol | 0 | 0 | 0 | 0 | 1326 | 20,197,978 |
| 3-symbol | 0 | 4 | 9,401,447 | |||
| 4-symbol | 0 | 12,435,284 | ||||
| 5-symbol | 75 | |||||
| 6-symbol | 870,085 |
Downloadable Holdout Lists
This is a 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.