Busy beaver lack of hope recurrence - Revision history

Polygon: Moved BB(1963) to the bottom

2026-02-28T12:04:57Z

Moved BB(1963) to the bottom

← Older revision		Revision as of 12:04, 28 February 2026
Line 59:		Line 59:

	'''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" />		'''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(5) to BB(6) and BB(7) ==

			"Basically, if and when artificial superintelligences take over the world, <i>they</i> 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>

	== BB(1963) ==		== BB(1963) ==
Line 65:		Line 71:

	'''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>		'''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, <i>they</i> 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 ==		== References ==

Ighwhenever at 07:08, 14 December 2025

2025-12-14T07:08:24Z

← Older revision		Revision as of 07:08, 14 December 2025
Line 66:		Line 66:
	'''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>		'''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) ==		== BB(5) to BB(6) and BB(7) ==

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

Ighwhenever at 07:06, 14 December 2025

2025-12-14T07:06:25Z

← Older revision		Revision as of 07:06, 14 December 2025
Line 65:		Line 65:

	'''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>		'''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, <i>they</i> 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 ==		== References ==

Sligocki: Link Tibor Radó

2025-12-04T21:40:30Z

Link Tibor Radó

← Older revision		Revision as of 21:40, 4 December 2025
Line 2:		Line 2:

	== BB(2) to BB(3) ==		== 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, [[Shen Lin\|S. Lin]]."		'''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 & ~~T. Rado~~, An Approach to Artificial Intelligence, IEEE Special Publication S-142, January 1963.		'''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) ==		== 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 ~~Rado~~, 1963.		[[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:''' 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>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>		'''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>		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>

Sligocki: Link Shen Lin

2025-12-04T17:42:12Z

Link Shen Lin

← Older revision		Revision as of 17:42, 4 December 2025
Line 2:		Line 2:

	== BB(2) to BB(3) ==		== 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."		'''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, [[Shen Lin\|S. Lin]]."

	'''Source''': R. W. House & T. Rado, An Approach to Artificial Intelligence, IEEE Special Publication S-142, January 1963.		'''Source''': R. W. House & T. Rado, An Approach to Artificial Intelligence, IEEE Special Publication S-142, January 1963.
Line 64:		Line 64:
	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.		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) <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>		'''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>

	== References ==		== References ==

C7X: Fix character /* BB(4) to BB(5) and BB(6) */

2025-01-10T18:06:42Z

Fix character BB(4) to BB(5) and BB(6)

← Older revision		Revision as of 18:06, 10 January 2025
Line 16:		Line 16:

	* "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"		* "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.)"		* "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>		'''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>

Cosmo at 11:46, 10 January 2025

2025-01-10T11:46:25Z

← Older revision		Revision as of 11:46, 10 January 2025
Line 65:		Line 65:

	'''Source''': 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>		'''Source''': 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>

			== References ==

Cosmo at 11:45, 10 January 2025

2025-01-10T11:45:43Z

Cosmo at 11:39, 10 January 2025

2025-01-10T11:39:42Z

← Older revision		Revision as of 11:39, 10 January 2025
Line 14:		Line 14:

	== BB(4) to BB(5) and BB(6) ==		== BB(4) to BB(5) and BB(6) ==
	[[File:BradyBB(5)isHopeless.png\|alt=Allen H. Brady (who proved BB(4) = 107) is saying that ever proving BB(5) is unlikely\|thumb\|Original source where Allen H. Brady says that solving BB(5) rigorously is unlikely to happen (1990).]]"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<sup>6</sup>. 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."—Allen Brady, 1990

	'''Source:''' Brady, Allen H~~, and the Meaning of Life~~, '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		* "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), <nowiki>https://doi.org/10.1093/oso/9780198537748.003.0009</nowiki>, 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<sup>6</sup>. 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]

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

Sligocki: /* Brady on level of intelligence required */

2025-01-09T18:55:39Z

Brady on level of intelligence required

← Older revision		Revision as of 18:55, 9 January 2025
Line 20:		Line 20:
	'''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."		'''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		'''Source''': From Machlin & Stout (1990) https://web.eecs.umich.edu/~qstout/abs/busyb.html

	== BB(5) ==		== BB(5) ==
Line 26:		Line 26:
	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?		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"		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]

	=== Brady's Prediction 5 ===		=== Brady's Prediction 5 ===
Line 33:		Line 33:
	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.		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, 1990, "The Busy Beaver Game and the Meaning of Life", pages 251-252		'''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

	== BB(6) ==		== BB(6) ==
Line 47:		Line 49:

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

	== BB(1963) ==		== BB(1963) ==
Line 52:		Line 56:
	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.		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.

	Lin, 1963, "Computer Studies of Turing Machine Problems" (a PhD dissertation)		'''Source''': Lin, 1963, "Computer Studies of Turing Machine Problems" (a PhD dissertation)

← Older revision		Revision as of 11:45, 10 January 2025
Line 9:		Line 9:
	[[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 Rado, 1963.		[[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 Rado, 1963.

	'''Source:''' 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.		'''Source:''' 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>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.		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) ==		== BB(4) to BB(5) and BB(6) ==
Line 18:		Line 18:
	* "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.)"		* "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), <nowiki>https://doi.org/10.1093/oso/9780198537748.003.0009</nowiki>, accessed 26 Sept. 2024		'''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:		Arnold Oberschelp who reviewed the above paper by Brady, went even further:
Line 24:		Line 24:
	"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<sup>6</sup>. 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."		"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<sup>6</sup>. 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]		'''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."		'''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		'''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) ==		== BB(5) ==
Line 34:		Line 34:
	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?		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]		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 ===		=== Brady's Prediction 5 ===
Line 43:		Line 43:
	'''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]		'''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		Repeated: Allen Brady, 1990, "The Busy Beaver Game and the Meaning of Life", pages 251-252 <ref name=":0" />

	== BB(6) ==		== BB(6) ==
Line 58:		Line 58:
	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.		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]		'''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) ==		== BB(1963) ==
Line 64:		Line 64:
	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.		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)		'''Source''': 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>