Busy beaver lack of hope recurrence: Difference between revisions
No edit summary |
No edit summary |
||
Line 10: | Line 10: | ||
'''Original 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; online edn, Oxford Academic, 31 Oct. 2023), <nowiki>https://doi.org/10.1093/oso/9780198537748.003.0009</nowiki>, accessed 26 Sept. 2024 | '''Original 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; online edn, Oxford Academic, 31 Oct. 2023), <nowiki>https://doi.org/10.1093/oso/9780198537748.003.0009</nowiki>, accessed 26 Sept. 2024 | ||
[[File:BradyBB(5)isHopeless.png|alt=Allen H. Brady (who proved BB(4) = 107) is saying that ever proving BB(5) is unlikely|thumb]] | [[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.]] |
Revision as of 21:30, 26 September 2024
People working on BB(n-1) believed BB(n) was impossible:
BB(3) to BB(4)
Second-hand report: "In any case, even though skilled mathematicians and experienced programmers attempted to evaluate 2(3) and 5(3), there is no evidence that any known approach will yield the answer, even if we avail ourselves of high-speed computers and elaborate programs. As regards \Sigma(4), S(4), the situation seems to be entirely hopeless at present."—Tibor Rado, 1963. Source: 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)
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
Original 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; online edn, Oxford Academic, 31 Oct. 2023), https://doi.org/10.1093/oso/9780198537748.003.0009, accessed 26 Sept. 2024
