Holdouts lists: Difference between revisions
Updated BB(3,4) holdout count (the old value had a typo) |
RobinCodes (talk | contribs) Added BB6 progres |
||
| (11 intermediate revisions by 4 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. | ||
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. | 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. They may exclude known equivalent machines, whose halting status is implied by the halting status of another machine. | ||
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. | 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. | ||
| Line 20: | Line 20: | ||
|0 | |0 | ||
|0 | |0 | ||
|1, | |1,534 | ||
| | |20,405,295 | ||
|- | |- | ||
!3-symbol | !3-symbol | ||
|0 | |0 | ||
|6 | |6 | ||
| | |9,401,447 | ||
| | | | ||
| | | | ||
| Line 33: | Line 33: | ||
!4-symbol | !4-symbol | ||
|0 | |0 | ||
| | |15,136,283 | ||
| | | | ||
| | | | ||
| Line 48: | Line 48: | ||
|- | |- | ||
!6-symbol | !6-symbol | ||
| | |870,085 | ||
| | | | ||
| | | | ||
| Line 65: | Line 65: | ||
!File | !File | ||
!Notes | !Notes | ||
|- | |||
|[[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)]] | |[[BB(3,4)]] | ||
Latest revision as of 11:17, 15 November 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. They may exclude known equivalent machines, whose halting status is implied by the halting status of another machine.
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,534 | 20,405,295 |
| 3-symbol | 0 | 6 | 9,401,447 | |||
| 4-symbol | 0 | 15,136,283 | ||||
| 5-symbol | 75 | |||||
| 6-symbol | 870,085 |