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?



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!

  • 1
    $\begingroup$ cs.stackexchange.com/a/59345/12859 ​ ​ $\endgroup$ – user12859 Jul 18 '17 at 20:14
  • $\begingroup$ @RickyDemer Cool! 27 years old, so not exactly 'current', but it's the first I've seen, thanks!! $\endgroup$ – Bram28 Jul 18 '17 at 20:25
  • 2
    $\begingroup$ Possible duplicate of What are very short programs with unknown halting status? $\endgroup$ – David Richerby Jul 18 '17 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 Jul 18 '17 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$ – Ben Fletcher Nov 9 '17 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.