Holdouts lists: Difference between revisions
Jump to navigation
Jump to search
(→Downloadable Holdout Lists: trying to add txt file of 217 holdout list) |
(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. | 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. | ||
{| 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. | ||
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.
| 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
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.