Busy beaver lack of hope recurrence

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 T. Rado and one of his graduate students, S. Lin."

Source: R. W. House & T. Rado, An Approach to Artificial Intelligence, IEEE Special Publication S-142, January 1963.

BB(2) to BB(3) and BB(4)

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 Rado, 1963.

Source: Radó, T. "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.

Quoted in: Brady, Allen H.. “The determination of the value of Rado’s noncomputable function Σ(4) for four-state Turing machines.” Mathematics of Computation 40 (1983): 647-665.

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 4(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), https://doi.org/10.1093/oso/9780198537748.003.0009, accessed 26 Sept. 2024.

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 10⁶. 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, URL

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

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" Pages 263-264

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" Page 274

Repeated: Allen Brady, 1990, "The Busy Beaver Game and the Meaning of Life", pages 251-252

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" Page 274-275

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: Lin, 1963, "Computer Studies of Turing Machine Problems" (a PhD dissertation)