3 ms·
Further to what other people have said, a weird thing about the Busy Beaver is that it's eventually harder than all of mathematics. https://bbchallenge.org/sto
by schoen 4y ago
Further to what other people have said, a weird thing about the Busy Beaver is that it's eventually harder than all of mathematics.
https://bbchallenge.org/story#what-is-known-about-bb https://bbchallenge.org/story#what-is-known-about-bb
(People have proven in Gödel-style that eventually any given mathematical theory is not strong enough to confirm, by any method, that a specific high-enough BB value is correct.)
And it famously "grows faster than any computable function".
https://en.wikipedia.org/wiki/Busy_beaver#Maximum_shifts_function_S https://en.wikipedia.org/wiki/Busy_beaver#Maximum_shifts_fun...
The people running this challenge believe that confirming with certainty the very next value, BB(6), probably requires answering questions that are, or are equivalent to, mathematical conjectures that humanity will never resolve.
A closely related concept about quantifying the behavior of all Turing machines is Chaitin's omega
https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant
which has similarly bizarre properties about it being as hard as all of the rest of mathematics to calculate digits of this number.
- tromp 4y ago> A closely related concept about quantifying the behavior of all Turing machines is Chaitin's omega More precisely, Chaitin's Omega quantifies the behaviour of all Lisp expressions, since he defined it not in terms of Turing machines, but in terms of a universal lisp interpreter. Not your standard lisp either, but a minimal version geared toward Algorithmic Information Theory [1]. [1] https://www.jucs.org/jucs_2_5/the_limits_of_mathematics/Chaitin_G_J.html https://www.jucs.org/jucs_2_5/the_limits_of_mathematics/Chai...