8
$\begingroup$

I understand from the Wikipedia page on the Busy Beaver problem that the Busy Beaver values for 5-state 2-symbol (quintuple) Turing-machines have not been determined, because there are 'holdout' machines whose halting behavior is as of yet unknown.

Can someone provide me with a concrete example of such a 5-state 2-symbol current (or as close to 'current' as possible) 'holdout'? When looking around on the net, I am finding lots of 'champions', but never any 'holdouts'. Does someone have one or more examples, please?

Thanks!

EDIT

THe linked question asked about 'short programs', but this question is specific to Turing-machines and the Busy Beaver problem. And yes, while that question solicited a response with two Busy Beaver Holdouts of the right kind (Thanks Ricki!), the source provided is 27 years old ... I would like to be able to point to any of these machines and say that these are 'current' holdouts, so if anyone can tell me whether these are still holdouts, or knows of any other, more current, holdouts, I would appreciate it. So, I am holding out for someone who maybe has some more current knowledge regarding the status of these busy beaver holdouts. Thanks!

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ cs.stackexchange.com/a/59345/12859 ​ ​ $\endgroup$
    – user12859
    Commented Jul 18, 2017 at 20:14
  • $\begingroup$ @RickyDemer Cool! 27 years old, so not exactly 'current', but it's the first I've seen, thanks!! $\endgroup$
    – Bram28
    Commented Jul 18, 2017 at 20:25
  • 3
    $\begingroup$ Possible duplicate of What are very short programs with unknown halting status? $\endgroup$
    – David Richerby
    Commented Jul 18, 2017 at 23:07
  • 1
    $\begingroup$ @DavidRicherby Yes, I looked at that one, but I really want it to be for Turing-machines. Then again, the answer provided there by Ricki was what I was looking for ... though a bit dated ... Thanks!! $\endgroup$
    – Bram28
    Commented Jul 18, 2017 at 23:12
  • $\begingroup$ The bibliography of the following paper lists a number of websites devoted to the study of BBs. I too have been frustrated with the absence of a list of holdouts. They can be enumerated so concisely, there must be another reason than "too verbose" for why they aren't shared: arxiv.org/pdf/0906.3749.pdf. At least that paper is from 2017. Page 8 of that paper also discusses where the results of various TMs have been stored and the challenges researchers have faced. $\endgroup$
    – ballenf
    Commented Nov 9, 2017 at 18:38

1 Answer 1

Reset to default
3
$\begingroup$

Skelet has 43 holdouts (those with type = ----). At least No. 827123 (the very first in the lists) is still open, afaik. My "feeling" is that all but 6 (no idea, which!) have been shown to be infinite. Good luck!

http://skelet.ludost.net/bb/nreg.html

No info on actual holdouts, but state-of-the-art in several aspects: https://www.scottaaronson.com/papers/bb.pdf

These are the 43 holdouts according to Skelet:

Nonregular machines:

    A0  A1   B0  B1   C0  C1   D0  D1   E0  E1   |    id    |
    
    C1L E1L  H1L D1L  D1R D0L  A1L E1R  B0L C0R  |   827123 |
    C1L E0R  H1L C0R  D1R A0L  A1R D1R  A1L B0R  |  1668912 |
    C1L A0R  H1L E1L  D1R B0L  A1R C1R  C0L D1L  |  2523420 |
    C1L D0R  H1L E0L  D1R C1L  E1L A1R  B1L D0L  |  3911891 |
    C1L A1L  H1L D0L  D1R E0L  A1L C0R  C1R B0L  |  6311798 |
    C1L B0R  H1L D0R  D1L A0R  E1R C0L  C1R E1R  |  7224038 |
    C1L B0R  H1L E1R  D1L A1L  A1R D0L  A0R C1R  | 11799516 |
    C1L B0R  H1L C0R  D1L C0L  E0R C1L  A0R E1R  | 11997798 |
    C1L D1R  H1L C0L  A1R C1L  E1R A0R  B1L E0L  | 18119527 |
    C1L A0L  H1L C0L  D0R A1L  B1L E1R  D1R E0R  | 21181509 |
    C1L A0L  H1L A0R  D0R A1L  E0R D1R  A1L B0R  | 22109761 |
    C1L E0L  H1L E1L  D0R A1L  A0L C1R  C1R B0L  | 22600133 |
    C1L B0R  H1L A1R  D0L E1R  E0R C1L  C1R A0R  | 25621006 |
    B1L H1L  C1R E0R  D1L B0R  D0L A1L  C0R A0L  |  5359517 |
    B1L H1L  C1L B1R  D1R E1L  B1R D0R  A1L C0L  |  6594274 |
    B1L H1L  C0R D1L  D1R C1R  E1L E0L  A0L B0R  | 11530505 |
    B1L H1L  C0R E1L  D0R C1R  A1L B1R  B0L A0L  | 11679832 |
    B1L H1L  C0L D0R  D1L E0R  E1L A0L  C1R D0R  | 14576100 |
    B1L H1L  C0L B0L  C1R D0R  A1L E0R  A0R E0R  | 15076017 |
    B1L H1L  C0L D1L  D0R C1L  E1R A0L  A1L E0R  | 15764213 |
    
    A0  A1   B0  B1   C0  C1   D0  D1   E0  E1   |    id    |
    
    C1L E1L  A1L H1L  D1R E0R  B1R E1R  C1R A0L  |   123831 |
    C1L E0L  A1R H1L  D1R A0L  D0R B1R  C0L B0R  |  3198755 |
    C1L C0R  D0L H1L  D1R E0L  C1L E0R  A1R B1L  |  5585454 |
    C1L A1L  E1R H1L  D1R D0R  B0R E0L  A0L C1R  |  6314131 |
    C1L A0R  A1L H1L  D1R E1L  A1R D0R  E0L B0R  |  6929003 |
    C1L E1R  D1R H1L  D1L C0L  A1R D1L  B1R A0R  | 12568936 |
    C1L E0L  D1R H1L  B1L E1L  A1R E1R  A1L D0R  | 17982461 |
    C1L D0R  A0L H1L  A1R D0L  E1R B1L  C1L C0R  | 23741566 |
    C1L E0L  C1R H1L  D0R A1L  A1R E0R  B1R E0L  | 30515821 |
    C1L B0R  E0R H1L  D0L C1L  E1L C0L  A1R C0R  | 33424333 |
    C1L E0R  C0L H1L  D0L B0L  D1R A0R  A1R D1L  | 33938206 |
    C1L D1R  E1R H1L  D0L C0L  B1R A0R  A1R E1L  | 34364505 |
    C1L D1R  E1R H1L  D0L C0L  B1R A0R  A1R A1L  | 34429669 |
    C1L D1R  E1R H1L  D0L C0L  B1R A0R  A1R A0R  | 34508331 |
    C1L E1R  D1R H1L  D0L C0L  B1R A1L  D1L A0R  | 34605254 |
    C1L B0R  C1R H1L  D0L D0R  A1R E0L  D1L E1L  | 36278670 |
    C1L C0L  D1L H1L  B0L D0R  E0R A1L  A1R E1R  | 40470734 |
    B1L D1L  C1R H1L  E1R D1R  E1L C0R  A1L D0L  | 43710027 |
    B1L A0L  C1R H1L  C0R D0R  E1L B0L  E0L A1L  | 45963385 |
    B1L A0R  C1L H1L  D0L E1R  E1L A0L  C1R A0R  | 50233205 |
    B1L E0R  C1L H1L  D0L C0L  D1R A0R  B0R E0R  | 50317033 |
    B1L A0R  C0L H1L  C1R D1L  E1L A1R  B0L D0R  | 54769539 |

This page was last modified at 16 May 2003.

(c) Skelet, May 2003 in terms of GNU GPL

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Stackexchange likes answers to be self-contained (to prevent problems like link rot). Could you copy-paste at least one specific machine here? $\endgroup$
    – Zachary Vance
    Commented Oct 17, 2020 at 1:31
  • $\begingroup$ Some of Skelet's holdouts have been since solved btw: cs.stackexchange.com/a/162108/10517 $\endgroup$
    – Ciro Santilli OurBigBook.com
    Commented Sep 18, 2023 at 7:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.