Holdouts lists: Difference between revisions
mNo edit summary |
(Started to add tables with verifiable holdout lists. These changes work out the structure. More content to follow.) |
||
| 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. Here is a table that summarises the number of holdout per busy beaver domain: | 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. | ||
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 47: | Line 49: | ||
|} | |} | ||
== Downloadable | == Downloadable Holdout Lists == | ||
{| class="wikitable sortable" | {| class="wikitable sortable" | ||
|+ | |+ | ||
| Line 205: | Line 207: | ||
|} | |} | ||
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" | |||
|+ | |||
!BB space | |||
!Date | |||
!Shared by | |||
!Number of holdouts | |||
!File | |||
!Notes | |||
|- | |||
|BB space | |||
|Date | |||
|Shared by | |||
|Number of holdouts | |||
|File | |||
|Notes | |||
|- | |||
|} | |||
Revision as of 05:51, 23 January 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. After that table are several tables, Verifiable Holdout Lists, that attempt to document a reproducible path from the initial enumeration of TMs of a given size tracking the holdout lists.
Here is a table that summarises the number of holdout per busy beaver domain based on the Downloadable Holdout Lists:
| 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.
Verifiable Holdout Lists
BB(3,3)
| BB space | Date | Shared by | Number of holdouts | File | Notes |
|---|---|---|---|---|---|
| BB space | Date | Shared by | Number of holdouts | File | Notes |