Busy beaver lack of hope recurrence: Difference between revisions
Jump to navigation
Jump to search
(Created page with "People working on BB(n-1) believed BB(n) was impossible: * BB(3) -> BB(4): "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.. [https://do...") |
(No difference)
|
Revision as of 21:17, 26 September 2024
People working on BB(n-1) believed BB(n) was impossible:
- BB(3) -> BB(4): "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) -> BB(5): "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