BusyBeaverWiki - User contributions [en]

Busy beaver lack of hope recurrence

2025-12-14T07:08:24Z

Ighwhenever:

Reading through old Busy Beaver papers, there is a common recurring theme in which someone working on solving BB(n-1) believes BB(n) to be impossible. We document here the quotes demonstrating this phenomenon.

== BB(2) to BB(3) ==
'''1.5th-hand report:''' "Suppose that, just to gain experience, we simplify the situation by merely asking whether a given 3-card machine will ever stop if started (with its card 1) on an all-zero tape. This particular question has been studied extensively by the authors in connection with the subject of sequential circuits. Many computer programs were written to answer this question; these programs grew larger and larger as more and more criteria for stoppers were covered. These programs were the results of co-operative efforts of experienced mathematicians and skilled programmers, and were run on some of the finest existing computers. Yet this extremely primitive-looking problem was still unsolved when this paper was presented, and '''probably most of the participants in the studies felt that perhaps it would always remain so'''. But since then, this problem has been solved by [[Tibor Radó|T. Rado]] and one of his graduate students, [[Shen Lin|S. Lin]]."

'''Source''': R. W. House & [[Tibor Radó]], An Approach to Artificial Intelligence, IEEE Special Publication S-142, January 1963.

== BB(2) to BB(3) and BB(4) ==
[[File:Capture d’écran 2024-10-03 à 11.45.55.png|thumb|Original source where [[Tibor Radó]] says that solving BB(4) is hopeless at present (1962).]]"In any case, even though skilled mathematicians and experienced programmers attempted to evaluate Σ(3) and S(3), there is '''no evidence that any presently known approach will yield the answer''', even if we avail ourselves of high-speed computers and elaborate programs. As regards Σ(4), S(4), '''the situation seems to be entirely hopeless at present'''."—Tibor Radó, 1963.

'''Source:''' [[Tibor Radó]]. [https://docs.bbchallenge.org/papers/Rado1963.pdf "On a simple source for non-computable functions"], Proceedings of the Symposium on Mathematical Theory of Automata, New York, April 1962, Polytechnic Press of the polytechnique Institue of Brooklyn 1963.<ref>Radó, T. [https://docs.bbchallenge.org/papers/Rado1963.pdf "On a simple source for non-computable functions"], Proceedings of the Symposium on Mathematical Theory of Automata, New York, April 1962, Polytechnic Press of the polytechnique Institue of Brooklyn 1963. </ref>

Quoted in: Brady, Allen H.. [https://docs.bbchallenge.org/papers/Brady1983.pdf “The determination of the value of Rado’s noncomputable function Σ(4) for four-state Turing machines.”] Mathematics of Computation 40 (1983): 647-665.<ref>Brady, Allen H.. [https://docs.bbchallenge.org/papers/Brady1983.pdf “The determination of the value of Rado’s noncomputable function Σ(4) for four-state Turing machines.”] Mathematics of Computation 40 (1983): 647-665.</ref>

== BB(4) to BB(5) and BB(6) ==

* "Even though it might appear now that the five-state problem is within grasp, there is a distinct possibility that the limit of practical solvability has in fact been reached. While we can follow Uhing's current champion machines until they halt, it is not clear at all how the machines work. Any cleverness in their construction is not the result of human creation, so there is a conspicuous absence of documentation! In light of Green's results it was easy to accept that the turning point for the Busy Beaver Game might occur at k = 6, but such magnitudes as have now been produced for k = 5 had never been anticipated. Any hope for solving the problem at this level will require computer programs endowed with a level of intelligence that we have"
* "Prediction 5. It will never be proved that Σ(5) = 1,915 and S(5) = 2, 358, 064. (Or, if any larger lower bounds are ever found, the new values may be substituted into the prediction.)"

'''Source:''' Brady, Allen H, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), ''The Universal Turing Machine: A Half-Century Survey'' (Oxford, 1990), <nowiki>https://doi.org/10.1093/oso/9780198537748.003.0009</nowiki>, accessed 26 Sept. 2024.<ref name=":0">Brady, Allen H, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), ''The Universal Turing Machine: A Half-Century Survey'' (Oxford, 1990), <nowiki>https://doi.org/10.1093/oso/9780198537748.003.0009</nowiki>, accessed 26 Sept. 2024. </ref>

Arnold Oberschelp who reviewed the above paper by Brady, went even further:

"The hard case is for n = 5. When computers became cheaper and faster many high-scoring and long-running (5 x 2)-machines were found, the best reported here (by Uhing) showing Σ(5) ≥ 1,915 and S(5) > 2.3 x 106. The author points out that when looking at such tricky machines found by computer one can verify that they stop but one has virtually no idea why they stop. And since whatever bounds on space and time are fixed for a computer search, there are left in the search space immensely many machines that must be treated individually, it will probably never be possible to prove mathematically that they will not stop. Even if one does get the exact value for n = 5, one might never be able to prove it rigorously. The case n = 6 is quite intractable."

'''Source:''' Oberschelp, A, review published in The Journal of Symbolic Logic / Volume 56 / Issue 03 / September 1991, pp 1091 - 1091, [https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/allen-h-brady-the-busy-beaver-game-and-the-meaning-of-life-the-universal-turing-machine-a-halfcentury-survey-edited-by-rolf-herken-kammerer-unverzagt-hamburg-and-berlin-and-oxford-university-press-oxford-and-new-york-1988-pp-259277/CB4DC8CF087389ADDD6B42CB0625A9A4 URL]<ref>Oberschelp, A, review published in The Journal of Symbolic Logic / Volume 56 / Issue 03 / September 1991, pp 1091 - 1091, [https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/allen-h-brady-the-busy-beaver-game-and-the-meaning-of-life-the-universal-turing-machine-a-halfcentury-survey-edited-by-rolf-herken-kammerer-unverzagt-hamburg-and-berlin-and-oxford-university-press-oxford-and-new-york-1988-pp-259277/CB4DC8CF087389ADDD6B42CB0625A9A4 URL]</ref>

'''Second-hand report:''' "Brady predicted that there will never be a proof of the values of Sigma(5) and S(5). We are just slightly more optimistic, and are lead to recast a parable due to Erdos (who spoke in the context of determining Ramsey numbers): suppose a vastly superior alien force lands and announces that they will destroy the planet unless we provide a value of the S function, along with a proof of its correctness. If they ask for S(5) we should put all of our mathematicians, computer scientists, and computers to the task, but if they ask for S(6) we should immediately attack because the task is hopeless."

'''Source''': From Machlin & Stout (1990) https://web.eecs.umich.edu/~qstout/abs/busyb.html<ref>Machlin, Rona, Stout, Quentin F. (1990/06)."The complex behavior of simple machines." Physica D: Nonlinear Phenomena 42(1-3): 85-98.</ref>

== BB(5) ==
=== Brady on level of intelligence required ===
Even though it might appear now that the five-state problem is within grasp, there is a distinct possibility that the limit of practical solvability has in fact been reached. While we can follow Uhing's current champion machines [resp. σ = 1,915, s = 2,133,492, and σ = 1,471, s = 2,358,064] until they halt, it is not clear at all how the machines work. Any cleverness in their construction is not the result of human creation, so there is a conspicuous absence of documentation! In light of Green's results it was easy to accept that the turning point for the Busy Beaver Game might occur at k = 6, but such magnitudes as have now been produced for k = 5 had never been anticipated. Any hope for solving the problem at this level will require computer programs endowed with a level of intelligence that we have not seen in anything done previously by a machine. Can it be decided by a computer program or will it be necessary to assign one mathematician per unresolved five-state Turing Machine?

Source: Allen Brady, 1988, "The Busy Beaver Game and the Meaning of Life" [https://archive.org/details/universalturingm0000unse/page/262/mode/2up?view=theater Pages 263-264]<ref name=":0" />

=== Brady's Prediction 5 ===
''Prediction 5.'' It will never be proved that S(5) = 2,358,064 and Σ(5) = 1,915. (Or, if any larger lower bounds are ever found, the new values may be substituted into the prediction.)

Reason: Nature has probably embedded among the five-state holdout machines one or more problems as illusive as the ''Goldbach Conjecture''. Or, in other terms, there will likely be nonstopping recursive patterns which are beyond our powers of recognition.

'''Source''': Allen Brady, 1988, "The Busy Beaver Game and the Meaning of Life" [https://archive.org/details/universalturingm0000unse/page/274/mode/2up?view=theater Page 274]

Repeated: Allen Brady, 1990, "The Busy Beaver Game and the Meaning of Life", pages 251-252 <ref name=":0" />

== BB(6) ==
=== Brady's Prediction 6 ===

''Prediction 6.'' From known results for k = 5 a six-state machine will be constructed for which it can be "proved" that its shift number (and thus a lower bound for S(6)) is an incomprehensibly large value which is in itself difficult to describe.

Reason: It is now clear that determining Σ(6) and S(6) is intractable. At this level one can speculate with impunity, and we shall.

Some students of the author were readily convinced after extensive examination and computer testing that Uhing's champion machine for S(5) would never halt. Seeking assurance one student ran her simulator to a point just short of two million moves! From an amusing experience such as this, one is led to consider the possibility that someday a machine of six states (or a just a few more) will be presented by a group of mathematicians along with a "proof" that it will never halt. Suppose then an efficient simulator for the machine were built on the leading but slightly jagged edge of technology and run for an extensive period of time. And then suppose it were to halt! The mathematicians, with solid reasoning to back them up, could make a valid claim that the machine malfunctioned.

But now suppose that instead of building a machine, another group of equivalently qualified thinkers, supported by a great body of mathematical knowledge, countered with a different "proof" that after some unimaginable number of moves the proposed machine would in fact halt. Their number would be so large that building a simulator to check the result would be inconceivable. What then? (It is only speculation, of course!)

For k = 6 the problem transcends mechanism. One reaches a point where it becomes impossible to distinguish between the finite and the infinite. Is there a point at which it will transcend logic? Rado's question remains open.

'''Source''': Allen Brady, 1988, "The Busy Beaver Game and the Meaning of Life" [https://archive.org/details/universalturingm0000unse/page/274/mode/2up?view=theater Page 274-275] <ref name=":0" />

== BB(1963) ==

Should one attempt to apply the method described above to the problem BB-1963, for example, then difficulties of prohibitive character are bound to arise. In the first place, the number of cases becomes astronomical, and the storage and execution for the computer programs involved will defeat any efforts to use existing computers. Even if we assume that somehow we managed to squeeze through the computer the portion of our approach involving partial recurrence patterns, the number of "holdouts" may be expected to be enormous. Over and beyond such "physical" difficulties, there is the basic fact of the non-computability of Σ(n), which implies that no single finite computer program exists that will furnish the value of Σ(n) for every n. Accordingly, there seems to be at present no justification for the assumption that Σ(n) is effectively calculable for each individual n. Evidently, these comments suggests a number of questions relating to the BB-n problem which seem to be beyond the reach of presently known methods, Thus it appears that clarification of the idea of a "given" non-negative integer may be a fruitful and certainly difficult enterprise.

'''Source''': [[Shen Lin]], 1963, "Computer Studies of Turing Machine Problems" (a PhD dissertation) <ref>Lin, Shen. "Computer studies of Turing machine problems /." Doctoral dissertation, Ohio State University, 1963. <nowiki>http://rave.ohiolink.edu/etdc/view?acc_num=osu1486554418657614</nowiki></ref>

== BB(5) to BB(6) and BB(7) ==

"Basically, if and when artificial superintelligences take over the world, they can worry about the value of BB(6). And then God can worry about the value of BB(7)."

'''Source''': Scott Aaronson, 2024, "BusyBeaver(5) is now known to be 47,176,870" <ref>Aaronson, Scott. "BusyBeaver(5) is now known to be 47,176,870", 2024. https://scottaaronson.blog/?p=8088</ref>

== References ==

Busy beaver lack of hope recurrence

2025-12-14T07:06:25Z

Ighwhenever:

Reading through old Busy Beaver papers, there is a common recurring theme in which someone working on solving BB(n-1) believes BB(n) to be impossible. We document here the quotes demonstrating this phenomenon.

== BB(2) to BB(3) ==
'''1.5th-hand report:''' "Suppose that, just to gain experience, we simplify the situation by merely asking whether a given 3-card machine will ever stop if started (with its card 1) on an all-zero tape. This particular question has been studied extensively by the authors in connection with the subject of sequential circuits. Many computer programs were written to answer this question; these programs grew larger and larger as more and more criteria for stoppers were covered. These programs were the results of co-operative efforts of experienced mathematicians and skilled programmers, and were run on some of the finest existing computers. Yet this extremely primitive-looking problem was still unsolved when this paper was presented, and '''probably most of the participants in the studies felt that perhaps it would always remain so'''. But since then, this problem has been solved by [[Tibor Radó|T. Rado]] and one of his graduate students, [[Shen Lin|S. Lin]]."

'''Source''': R. W. House & [[Tibor Radó]], An Approach to Artificial Intelligence, IEEE Special Publication S-142, January 1963.

== BB(2) to BB(3) and BB(4) ==
[[File:Capture d’écran 2024-10-03 à 11.45.55.png|thumb|Original source where [[Tibor Radó]] says that solving BB(4) is hopeless at present (1962).]]"In any case, even though skilled mathematicians and experienced programmers attempted to evaluate Σ(3) and S(3), there is '''no evidence that any presently known approach will yield the answer''', even if we avail ourselves of high-speed computers and elaborate programs. As regards Σ(4), S(4), '''the situation seems to be entirely hopeless at present'''."—Tibor Radó, 1963.

'''Source:''' [[Tibor Radó]]. [https://docs.bbchallenge.org/papers/Rado1963.pdf "On a simple source for non-computable functions"], Proceedings of the Symposium on Mathematical Theory of Automata, New York, April 1962, Polytechnic Press of the polytechnique Institue of Brooklyn 1963.<ref>Radó, T. [https://docs.bbchallenge.org/papers/Rado1963.pdf "On a simple source for non-computable functions"], Proceedings of the Symposium on Mathematical Theory of Automata, New York, April 1962, Polytechnic Press of the polytechnique Institue of Brooklyn 1963. </ref>

Quoted in: Brady, Allen H.. [https://docs.bbchallenge.org/papers/Brady1983.pdf “The determination of the value of Rado’s noncomputable function Σ(4) for four-state Turing machines.”] Mathematics of Computation 40 (1983): 647-665.<ref>Brady, Allen H.. [https://docs.bbchallenge.org/papers/Brady1983.pdf “The determination of the value of Rado’s noncomputable function Σ(4) for four-state Turing machines.”] Mathematics of Computation 40 (1983): 647-665.</ref>

== BB(4) to BB(5) and BB(6) ==

* "Even though it might appear now that the five-state problem is within grasp, there is a distinct possibility that the limit of practical solvability has in fact been reached. While we can follow Uhing's current champion machines until they halt, it is not clear at all how the machines work. Any cleverness in their construction is not the result of human creation, so there is a conspicuous absence of documentation! In light of Green's results it was easy to accept that the turning point for the Busy Beaver Game might occur at k = 6, but such magnitudes as have now been produced for k = 5 had never been anticipated. Any hope for solving the problem at this level will require computer programs endowed with a level of intelligence that we have"
* "Prediction 5. It will never be proved that Σ(5) = 1,915 and S(5) = 2, 358, 064. (Or, if any larger lower bounds are ever found, the new values may be substituted into the prediction.)"

'''Source:''' Brady, Allen H, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), ''The Universal Turing Machine: A Half-Century Survey'' (Oxford, 1990), <nowiki>https://doi.org/10.1093/oso/9780198537748.003.0009</nowiki>, accessed 26 Sept. 2024.<ref name=":0">Brady, Allen H, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), ''The Universal Turing Machine: A Half-Century Survey'' (Oxford, 1990), <nowiki>https://doi.org/10.1093/oso/9780198537748.003.0009</nowiki>, accessed 26 Sept. 2024. </ref>

Arnold Oberschelp who reviewed the above paper by Brady, went even further:

"The hard case is for n = 5. When computers became cheaper and faster many high-scoring and long-running (5 x 2)-machines were found, the best reported here (by Uhing) showing Σ(5) ≥ 1,915 and S(5) > 2.3 x 106. The author points out that when looking at such tricky machines found by computer one can verify that they stop but one has virtually no idea why they stop. And since whatever bounds on space and time are fixed for a computer search, there are left in the search space immensely many machines that must be treated individually, it will probably never be possible to prove mathematically that they will not stop. Even if one does get the exact value for n = 5, one might never be able to prove it rigorously. The case n = 6 is quite intractable."

'''Source:''' Oberschelp, A, review published in The Journal of Symbolic Logic / Volume 56 / Issue 03 / September 1991, pp 1091 - 1091, [https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/allen-h-brady-the-busy-beaver-game-and-the-meaning-of-life-the-universal-turing-machine-a-halfcentury-survey-edited-by-rolf-herken-kammerer-unverzagt-hamburg-and-berlin-and-oxford-university-press-oxford-and-new-york-1988-pp-259277/CB4DC8CF087389ADDD6B42CB0625A9A4 URL]<ref>Oberschelp, A, review published in The Journal of Symbolic Logic / Volume 56 / Issue 03 / September 1991, pp 1091 - 1091, [https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/allen-h-brady-the-busy-beaver-game-and-the-meaning-of-life-the-universal-turing-machine-a-halfcentury-survey-edited-by-rolf-herken-kammerer-unverzagt-hamburg-and-berlin-and-oxford-university-press-oxford-and-new-york-1988-pp-259277/CB4DC8CF087389ADDD6B42CB0625A9A4 URL]</ref>

'''Second-hand report:''' "Brady predicted that there will never be a proof of the values of Sigma(5) and S(5). We are just slightly more optimistic, and are lead to recast a parable due to Erdos (who spoke in the context of determining Ramsey numbers): suppose a vastly superior alien force lands and announces that they will destroy the planet unless we provide a value of the S function, along with a proof of its correctness. If they ask for S(5) we should put all of our mathematicians, computer scientists, and computers to the task, but if they ask for S(6) we should immediately attack because the task is hopeless."

'''Source''': From Machlin & Stout (1990) https://web.eecs.umich.edu/~qstout/abs/busyb.html<ref>Machlin, Rona, Stout, Quentin F. (1990/06)."The complex behavior of simple machines." Physica D: Nonlinear Phenomena 42(1-3): 85-98.</ref>

== BB(5) ==
=== Brady on level of intelligence required ===
Even though it might appear now that the five-state problem is within grasp, there is a distinct possibility that the limit of practical solvability has in fact been reached. While we can follow Uhing's current champion machines [resp. σ = 1,915, s = 2,133,492, and σ = 1,471, s = 2,358,064] until they halt, it is not clear at all how the machines work. Any cleverness in their construction is not the result of human creation, so there is a conspicuous absence of documentation! In light of Green's results it was easy to accept that the turning point for the Busy Beaver Game might occur at k = 6, but such magnitudes as have now been produced for k = 5 had never been anticipated. Any hope for solving the problem at this level will require computer programs endowed with a level of intelligence that we have not seen in anything done previously by a machine. Can it be decided by a computer program or will it be necessary to assign one mathematician per unresolved five-state Turing Machine?

Source: Allen Brady, 1988, "The Busy Beaver Game and the Meaning of Life" [https://archive.org/details/universalturingm0000unse/page/262/mode/2up?view=theater Pages 263-264]<ref name=":0" />

=== Brady's Prediction 5 ===
''Prediction 5.'' It will never be proved that S(5) = 2,358,064 and Σ(5) = 1,915. (Or, if any larger lower bounds are ever found, the new values may be substituted into the prediction.)

Reason: Nature has probably embedded among the five-state holdout machines one or more problems as illusive as the ''Goldbach Conjecture''. Or, in other terms, there will likely be nonstopping recursive patterns which are beyond our powers of recognition.

'''Source''': Allen Brady, 1988, "The Busy Beaver Game and the Meaning of Life" [https://archive.org/details/universalturingm0000unse/page/274/mode/2up?view=theater Page 274]

Repeated: Allen Brady, 1990, "The Busy Beaver Game and the Meaning of Life", pages 251-252 <ref name=":0" />

== BB(6) ==
=== Brady's Prediction 6 ===

''Prediction 6.'' From known results for k = 5 a six-state machine will be constructed for which it can be "proved" that its shift number (and thus a lower bound for S(6)) is an incomprehensibly large value which is in itself difficult to describe.

Reason: It is now clear that determining Σ(6) and S(6) is intractable. At this level one can speculate with impunity, and we shall.

Some students of the author were readily convinced after extensive examination and computer testing that Uhing's champion machine for S(5) would never halt. Seeking assurance one student ran her simulator to a point just short of two million moves! From an amusing experience such as this, one is led to consider the possibility that someday a machine of six states (or a just a few more) will be presented by a group of mathematicians along with a "proof" that it will never halt. Suppose then an efficient simulator for the machine were built on the leading but slightly jagged edge of technology and run for an extensive period of time. And then suppose it were to halt! The mathematicians, with solid reasoning to back them up, could make a valid claim that the machine malfunctioned.

But now suppose that instead of building a machine, another group of equivalently qualified thinkers, supported by a great body of mathematical knowledge, countered with a different "proof" that after some unimaginable number of moves the proposed machine would in fact halt. Their number would be so large that building a simulator to check the result would be inconceivable. What then? (It is only speculation, of course!)

For k = 6 the problem transcends mechanism. One reaches a point where it becomes impossible to distinguish between the finite and the infinite. Is there a point at which it will transcend logic? Rado's question remains open.

'''Source''': Allen Brady, 1988, "The Busy Beaver Game and the Meaning of Life" [https://archive.org/details/universalturingm0000unse/page/274/mode/2up?view=theater Page 274-275] <ref name=":0" />

== BB(1963) ==

Should one attempt to apply the method described above to the problem BB-1963, for example, then difficulties of prohibitive character are bound to arise. In the first place, the number of cases becomes astronomical, and the storage and execution for the computer programs involved will defeat any efforts to use existing computers. Even if we assume that somehow we managed to squeeze through the computer the portion of our approach involving partial recurrence patterns, the number of "holdouts" may be expected to be enormous. Over and beyond such "physical" difficulties, there is the basic fact of the non-computability of Σ(n), which implies that no single finite computer program exists that will furnish the value of Σ(n) for every n. Accordingly, there seems to be at present no justification for the assumption that Σ(n) is effectively calculable for each individual n. Evidently, these comments suggests a number of questions relating to the BB-n problem which seem to be beyond the reach of presently known methods, Thus it appears that clarification of the idea of a "given" non-negative integer may be a fruitful and certainly difficult enterprise.

'''Source''': [[Shen Lin]], 1963, "Computer Studies of Turing Machine Problems" (a PhD dissertation) <ref>Lin, Shen. "Computer studies of Turing machine problems /." Doctoral dissertation, Ohio State University, 1963. <nowiki>http://rave.ohiolink.edu/etdc/view?acc_num=osu1486554418657614</nowiki></ref>

== BB(6) and BB(7) ==

"Basically, if and when artificial superintelligences take over the world, they can worry about the value of BB(6). And then God can worry about the value of BB(7)."

'''Source''': Scott Aaronson, 2024, "BusyBeaver(5) is now known to be 47,176,870" <ref>Aaronson, Scott. "BusyBeaver(5) is now known to be 47,176,870", 2024. https://scottaaronson.blog/?p=8088</ref>

== References ==

Holdouts lists

2025-08-18T14:55:03Z

Ighwhenever:

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. 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.

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.

{| class="wikitable"
|+Number of holdouts
!
!2-state
!3-state
!4-state
!5-state
!6-state
!7-state
|-
!2-symbol
|0
|0
|0
|0
|2,728
|85,853,789
|-
!3-symbol
|0
|6
|460,916,384
|
|
|
|-
!4-symbol
|0
|434,787,751
|
|
|
|
|-
!5-symbol
|83
|
|
|
|
|
|-
!6-symbol
|22,302,296
|
|
|
|
|
|}

== Downloadable Holdout Lists ==
{| class="wikitable sortable"
|+
!BB space
!Date
!Shared by
!Number of holdouts
!File
!Notes
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1399783936019664896 July 29 2025]
|@mxdys
|2,728
|[[:File:BB6 holdouts 2728.txt|BB6 holdouts 2728.txt]]
|
|-
|[[BB(2,5)]]
|[https://discord.com/channels/960643023006490684/1259770421046411285/1355593937531961365 March 29 2025]
|@mxdys
|83
|[[:File:BB2x5 Coq holdouts 83.txt]]
|-
|[[BB(4,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1320172124509311004 December 21, 2024]
|@tjligocki
|460,916,384
|[https://drive.google.com/file/d/1hKy0TuPuI62rN95j6ZLjXgE-Pue8tRsK/view?usp=drive_link 4x3_holdouts_460916384.txt.gz]
|[https://drive.google.com/drive/folders/1HBPZ17llVE_8wCy5FvRUFQ5MJsaYXAW-?usp=drive_link Google Drive directory for 4x3 TMs]
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1310648046576730124 November 25, 2024 (@icy)]
|@tjligocki
|4,319
|[https://docs.google.com/spreadsheets/d/1grhW_0neb2I8TfceN5-v70_3W42Z2U159r9L6FhPGf8/edit?usp=sharing Spreadsheet of holdouts]
|Keeping track of BB(6) progress - informal.
|-
|[[BB(3,3)]]
|November 10, 2024
|
|6
|[[:File:3x3 holdout 6.txt|3x3 holdout 6.txt]]
|
|-
|[[BB(6)]]
|[https://discordapp.com/channels/960643023006490684/1239205785913790465/1304303803213942846 November 8, 2024]
|@mxdys
|4,408
|[[:File:BB6 holdouts 4408.txt|BB6_holdouts_4408.txt]]
|
|-
|[[BB(2,6)]]
|[https://discord.com/channels/960643023006490684/960643023530762341/1303219184221683733 November 4, 2024]
|@tjligocki
|22,302,296
|[https://drive.google.com/file/d/1xRLIjdiqImFP2SL38gvhxVlAaX0L1cYO/view?usp=drive_link 2x6_holdouts_22302296.txt.gz]
|[https://drive.google.com/drive/folders/1p9b5g-Id3WEMUYIwEnaKWRBGIW66ADjM?usp=drive_link Google Drive directory for 2x6 TMs]
|-
|[[BB(3,4)]]
|[https://discord.com/channels/960643023006490684/960643023530762341/1302767449476694188 November 3, 2024]
|@tjligocki
|434,787,751
|[https://drive.google.com/file/d/1PLzN3wLw-MRgk1OFmYh4RTwNc30nflR7/view?usp=drive_link 3x4_holdouts_434787751.txt.gz]
|[https://drive.google.com/drive/folders/1bZxl7jg5q9IVvHQNZwItx1kPusAWznZk?usp=drive_link Google Drive directory for 3x4 TMs]
|-
|[[BB(6)]]
|[https://discordapp.com/channels/960643023006490684/1239205785913790465/1280185195877634098 September 2, 2024]
|@mxdys
|5394
|[[:File:BB6 holdouts 5394.txt]]
|
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1269612923127599164 August 4, 2024]
|@mxdys
|5877
|[[:File:BB6 holdouts 5877.txt]]
|
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1259131753176498216 July 6, 2024]
|@mxdys
|7296
|[[:File:BB6 holdouts 7296.txt]]
|
|-
|[[BB(2,5)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1252989316175499284 June 19, 2024]
|@mxdys
|217
|[[:File:2x5_holdouts_217.txt]]
|273 holdouts minus machines solved by CTL
|-
|[[BB(2,5)]]
|June 15th 2024
|@dyuan01
| 273
|[[:File:2x5_holdouts_273.txt]]
|@Justin Blanchard's 499 holdouts minus machines solved by @mxdys
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1250895665719148595 June 13, 2024]
|@tjligocki
| 12,091
|[[:File:BB6 holdouts 12091.txt]]
|Work done with @Shawn Ligocki
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1249142547217907772 June 9, 2024]
|@Justin Blanchard
|22
|[[:File:3x3.todo.txt]], [[:File:Mugshots small.pdf]]
|
|-
|BB(6)
|[https://discord.com/channels/960643023006490684/1239205785913790465/1248708916381220954 June 7, 2024]
|@mxdys
|12,325
|[[:File:BB6 holdouts 12325.txt]]
|Some equivalent machines are removed.
|-
|[[BB(5)]]
|June 2024
|BBChallenge
|0
|
|'''BB(5) is SOLVED!'''
|-
|[[BB(2,5)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1242679236142170203 May 22, 2024]
|@Justin Blanchard
|499
|[[:File:2x5.todo.txt]]
|
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1116351783040716830 June 8, 2023]
|@Iijil
|925
|[[:File:2023 06 08.3x3.holdouts intersect sligocki iijil 925.txt]]
|Intersection of @sligocki and @Iijil from below
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1116351783040716830 June 8, 2023]
|@Iijil
|2,480
|[[:File:2023 06 08.3x3.holdouts iijil 2380.txt]]
|
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1116178334620070000 June 7, 2023]
|@sligocki
|2,417
|[[:File:2023 06 07.3x3.holdouts 2417.txt]]
|
|-
|[[BB(6)]]
|May 27, 2023
|@sligocki
|181,851
|[https://drive.google.com/file/d/1YNwFCN6XJeDNKxxK5KbGHOAFOdIBvDb6/view?usp=drive_link 6x2.holdouts_181851.txt.gz]
|This was posted to the BBChallenge Forum (before Discord)
|-
|[[BB(6)]]
|May 10, 2023
|@sligocki
|1,458,704
|[https://drive.google.com/file/d/14bDnBt0OwuHATFBiubc_5jub0220EyXf/view?usp=drive_link 6x2.holdouts_1458704.txt.gz]
|This was posted to the BBChallenge Forum (before Discord)
|-
|[[BB(5)]]
|[https://skelet.ludost.net/bb/nreg.html circa May 13th, 2003]
|Georgi Georgiev (Skelet)
|43
|[https://bbchallenge.org/skelet List of 43 holdouts]
|
|}

Holdouts lists

2025-08-18T14:53:37Z

Ighwhenever: Undo revision 3258 by Ighwhenever (talk)

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. 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.

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.

{| class="wikitable"
|+Number of holdouts
!
!2-state
!3-state
!4-state
!5-state
!6-state
|-
!2-symbol
|0
|0
|0
|0
|2,728
|-
!3-symbol
|0
|6
|460,916,384
|
|
|-
!4-symbol
|0
|434,787,751
|
|
|
|-
!5-symbol
|83
|
|
|
|
|-
!6-symbol
|22,302,296
|
|
|
|
|}

== Downloadable Holdout Lists ==
{| class="wikitable sortable"
|+
!BB space
!Date
!Shared by
!Number of holdouts
!File
!Notes
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1399783936019664896 July 29 2025]
|@mxdys
|2,728
|[[:File:BB6 holdouts 2728.txt|BB6 holdouts 2728.txt]]
|-
|[[BB(2,5)]]
|[https://discord.com/channels/960643023006490684/1259770421046411285/1355593937531961365 March 29 2025]
|@mxdys
|83
|[[:File:BB2x5 Coq holdouts 83.txt]]
|-
|[[BB(4,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1320172124509311004 December 21, 2024]
|@tjligocki
|460,916,384
|[https://drive.google.com/file/d/1hKy0TuPuI62rN95j6ZLjXgE-Pue8tRsK/view?usp=drive_link 4x3_holdouts_460916384.txt.gz]
|[https://drive.google.com/drive/folders/1HBPZ17llVE_8wCy5FvRUFQ5MJsaYXAW-?usp=drive_link Google Drive directory for 4x3 TMs]
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1310648046576730124 November 25, 2024 (@icy)]
|@tjligocki
|4,319
|[https://docs.google.com/spreadsheets/d/1grhW_0neb2I8TfceN5-v70_3W42Z2U159r9L6FhPGf8/edit?usp=sharing Spreadsheet of holdouts]
|Keeping track of BB(6) progress - informal.
|-
|[[BB(3,3)]]
|November 10, 2024
|
|6
|[[:File:3x3 holdout 6.txt|3x3 holdout 6.txt]]
|
|-
|[[BB(6)]]
|[https://discordapp.com/channels/960643023006490684/1239205785913790465/1304303803213942846 November 8, 2024]
|@mxdys
|4,408
|[[:File:BB6 holdouts 4408.txt|BB6_holdouts_4408.txt]]
|
|-
|[[BB(2,6)]]
|[https://discord.com/channels/960643023006490684/960643023530762341/1303219184221683733 November 4, 2024]
|@tjligocki
|22,302,296
|[https://drive.google.com/file/d/1xRLIjdiqImFP2SL38gvhxVlAaX0L1cYO/view?usp=drive_link 2x6_holdouts_22302296.txt.gz]
|[https://drive.google.com/drive/folders/1p9b5g-Id3WEMUYIwEnaKWRBGIW66ADjM?usp=drive_link Google Drive directory for 2x6 TMs]
|-
|[[BB(3,4)]]
|[https://discord.com/channels/960643023006490684/960643023530762341/1302767449476694188 November 3, 2024]
|@tjligocki
|434,787,751
|[https://drive.google.com/file/d/1PLzN3wLw-MRgk1OFmYh4RTwNc30nflR7/view?usp=drive_link 3x4_holdouts_434787751.txt.gz]
|[https://drive.google.com/drive/folders/1bZxl7jg5q9IVvHQNZwItx1kPusAWznZk?usp=drive_link Google Drive directory for 3x4 TMs]
|-
|[[BB(6)]]
|[https://discordapp.com/channels/960643023006490684/1239205785913790465/1280185195877634098 September 2, 2024]
|@mxdys
|5394
|[[:File:BB6 holdouts 5394.txt]]
|
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1269612923127599164 August 4, 2024]
|@mxdys
|5877
|[[:File:BB6 holdouts 5877.txt]]
|
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1259131753176498216 July 6, 2024]
|@mxdys
|7296
|[[:File:BB6 holdouts 7296.txt]]
|
|-
|[[BB(2,5)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1252989316175499284 June 19, 2024]
|@mxdys
|217
|[[:File:2x5_holdouts_217.txt]]
|273 holdouts minus machines solved by CTL
|-
|[[BB(2,5)]]
|June 15th 2024
|@dyuan01
| 273
|[[:File:2x5_holdouts_273.txt]]
|@Justin Blanchard's 499 holdouts minus machines solved by @mxdys
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1250895665719148595 June 13, 2024]
|@tjligocki
| 12,091
|[[:File:BB6 holdouts 12091.txt]]
|Work done with @Shawn Ligocki
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1249142547217907772 June 9, 2024]
|@Justin Blanchard
|22
|[[:File:3x3.todo.txt]], [[:File:Mugshots small.pdf]]
|
|-
|BB(6)
|[https://discord.com/channels/960643023006490684/1239205785913790465/1248708916381220954 June 7, 2024]
|@mxdys
|12,325
|[[:File:BB6 holdouts 12325.txt]]
|Some equivalent machines are removed.
|-
|[[BB(5)]]
|June 2024
|BBChallenge
|0
|
|'''BB(5) is SOLVED!'''
|-
|[[BB(2,5)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1242679236142170203 May 22, 2024]
|@Justin Blanchard
|499
|[[:File:2x5.todo.txt]]
|
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1116351783040716830 June 8, 2023]
|@Iijil
|925
|[[:File:2023 06 08.3x3.holdouts intersect sligocki iijil 925.txt]]
|Intersection of @sligocki and @Iijil from below
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1116351783040716830 June 8, 2023]
|@Iijil
|2,480
|[[:File:2023 06 08.3x3.holdouts iijil 2380.txt]]
|
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1116178334620070000 June 7, 2023]
|@sligocki
|2,417
|[[:File:2023 06 07.3x3.holdouts 2417.txt]]
|
|-
|[[BB(6)]]
|May 27, 2023
|@sligocki
|181,851
|[https://drive.google.com/file/d/1YNwFCN6XJeDNKxxK5KbGHOAFOdIBvDb6/view?usp=drive_link 6x2.holdouts_181851.txt.gz]
|This was posted to the BBChallenge Forum (before Discord)
|-
|[[BB(6)]]
|May 10, 2023
|@sligocki
|1,458,704
|[https://drive.google.com/file/d/14bDnBt0OwuHATFBiubc_5jub0220EyXf/view?usp=drive_link 6x2.holdouts_1458704.txt.gz]
|This was posted to the BBChallenge Forum (before Discord)
|-
|[[BB(5)]]
|[https://skelet.ludost.net/bb/nreg.html circa May 13th, 2003]
|Georgi Georgiev (Skelet)
|43
|[https://bbchallenge.org/skelet List of 43 holdouts]
|
|}

Holdouts lists

2025-08-18T14:49:14Z

Ighwhenever:

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. 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.

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.

{| class="wikitable"
|+Number of holdouts
!
!2-state
!3-state
!4-state
!5-state
!6-state
!7-state
|-
!2-symbol
|0
|0
|0
|0
|2,728
|85,853,789
|-
!3-symbol
|0
|6
|460,916,384
|
|
|
|-
!4-symbol
|0
|434,787,751
|
|
|
|
|-
!5-symbol
|83
|
|
|
|
|
|-
!6-symbol
|22,302,296
|
|
|
|
|
|}

== Downloadable Holdout Lists ==
{| class="wikitable sortable"
|+
!BB space
!Date
!Shared by
!Number of holdouts
!File
!Notes
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1399783936019664896 July 29 2025]
|@mxdys
|2,728
|[[:File:BB6 holdouts 2728.txt|BB6 holdouts 2728.txt]]
|
|-
|[[BB(7)]]
|[https://discord.com/channels/960643023006490684/1369339127652159509/1399265628900294686 July 28 2025]
|@tjligocki
|85,853,789
|
|
|-
|[[BB(2,5)]]
|[https://discord.com/channels/960643023006490684/1259770421046411285/1355593937531961365 March 29 2025]
|@mxdys
|83
|[[:File:BB2x5 Coq holdouts 83.txt]]
|-
|[[BB(4,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1320172124509311004 December 21, 2024]
|@tjligocki
|460,916,384
|[https://drive.google.com/file/d/1hKy0TuPuI62rN95j6ZLjXgE-Pue8tRsK/view?usp=drive_link 4x3_holdouts_460916384.txt.gz]
|[https://drive.google.com/drive/folders/1HBPZ17llVE_8wCy5FvRUFQ5MJsaYXAW-?usp=drive_link Google Drive directory for 4x3 TMs]
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1310648046576730124 November 25, 2024 (@icy)]
|@tjligocki
|4,319
|[https://docs.google.com/spreadsheets/d/1grhW_0neb2I8TfceN5-v70_3W42Z2U159r9L6FhPGf8/edit?usp=sharing Spreadsheet of holdouts]
|Keeping track of BB(6) progress - informal.
|-
|[[BB(3,3)]]
|November 10, 2024
|
|6
|[[:File:3x3 holdout 6.txt|3x3 holdout 6.txt]]
|
|-
|[[BB(6)]]
|[https://discordapp.com/channels/960643023006490684/1239205785913790465/1304303803213942846 November 8, 2024]
|@mxdys
|4,408
|[[:File:BB6 holdouts 4408.txt|BB6_holdouts_4408.txt]]
|
|-
|[[BB(2,6)]]
|[https://discord.com/channels/960643023006490684/960643023530762341/1303219184221683733 November 4, 2024]
|@tjligocki
|22,302,296
|[https://drive.google.com/file/d/1xRLIjdiqImFP2SL38gvhxVlAaX0L1cYO/view?usp=drive_link 2x6_holdouts_22302296.txt.gz]
|[https://drive.google.com/drive/folders/1p9b5g-Id3WEMUYIwEnaKWRBGIW66ADjM?usp=drive_link Google Drive directory for 2x6 TMs]
|-
|[[BB(3,4)]]
|[https://discord.com/channels/960643023006490684/960643023530762341/1302767449476694188 November 3, 2024]
|@tjligocki
|434,787,751
|[https://drive.google.com/file/d/1PLzN3wLw-MRgk1OFmYh4RTwNc30nflR7/view?usp=drive_link 3x4_holdouts_434787751.txt.gz]
|[https://drive.google.com/drive/folders/1bZxl7jg5q9IVvHQNZwItx1kPusAWznZk?usp=drive_link Google Drive directory for 3x4 TMs]
|-
|[[BB(6)]]
|[https://discordapp.com/channels/960643023006490684/1239205785913790465/1280185195877634098 September 2, 2024]
|@mxdys
|5394
|[[:File:BB6 holdouts 5394.txt]]
|
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1269612923127599164 August 4, 2024]
|@mxdys
|5877
|[[:File:BB6 holdouts 5877.txt]]
|
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1259131753176498216 July 6, 2024]
|@mxdys
|7296
|[[:File:BB6 holdouts 7296.txt]]
|
|-
|[[BB(2,5)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1252989316175499284 June 19, 2024]
|@mxdys
|217
|[[:File:2x5_holdouts_217.txt]]
|273 holdouts minus machines solved by CTL
|-
|[[BB(2,5)]]
|June 15th 2024
|@dyuan01
| 273
|[[:File:2x5_holdouts_273.txt]]
|@Justin Blanchard's 499 holdouts minus machines solved by @mxdys
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1250895665719148595 June 13, 2024]
|@tjligocki
| 12,091
|[[:File:BB6 holdouts 12091.txt]]
|Work done with @Shawn Ligocki
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1249142547217907772 June 9, 2024]
|@Justin Blanchard
|22
|[[:File:3x3.todo.txt]], [[:File:Mugshots small.pdf]]
|
|-
|BB(6)
|[https://discord.com/channels/960643023006490684/1239205785913790465/1248708916381220954 June 7, 2024]
|@mxdys
|12,325
|[[:File:BB6 holdouts 12325.txt]]
|Some equivalent machines are removed.
|-
|[[BB(5)]]
|June 2024
|BBChallenge
|0
|
|'''BB(5) is SOLVED!'''
|-
|[[BB(2,5)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1242679236142170203 May 22, 2024]
|@Justin Blanchard
|499
|[[:File:2x5.todo.txt]]
|
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1116351783040716830 June 8, 2023]
|@Iijil
|925
|[[:File:2023 06 08.3x3.holdouts intersect sligocki iijil 925.txt]]
|Intersection of @sligocki and @Iijil from below
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1116351783040716830 June 8, 2023]
|@Iijil
|2,480
|[[:File:2023 06 08.3x3.holdouts iijil 2380.txt]]
|
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1116178334620070000 June 7, 2023]
|@sligocki
|2,417
|[[:File:2023 06 07.3x3.holdouts 2417.txt]]
|
|-
|[[BB(6)]]
|May 27, 2023
|@sligocki
|181,851
|[https://drive.google.com/file/d/1YNwFCN6XJeDNKxxK5KbGHOAFOdIBvDb6/view?usp=drive_link 6x2.holdouts_181851.txt.gz]
|This was posted to the BBChallenge Forum (before Discord)
|-
|[[BB(6)]]
|May 10, 2023
|@sligocki
|1,458,704
|[https://drive.google.com/file/d/14bDnBt0OwuHATFBiubc_5jub0220EyXf/view?usp=drive_link 6x2.holdouts_1458704.txt.gz]
|This was posted to the BBChallenge Forum (before Discord)
|-
|[[BB(5)]]
|[https://skelet.ludost.net/bb/nreg.html circa May 13th, 2003]
|Georgi Georgiev (Skelet)
|43
|[https://bbchallenge.org/skelet List of 43 holdouts]
|
|}