So, about 88 millions of machines is left to test. We're interested in any, which runs longer than about 47 millions steps. Multiplying we get about 4.2e15 steps at worst. Can't we brute force the solution? It's like 5 million seconds - or less than two months - 1 billion steps a second, which looks doable for a modest system, and we don't even need much memory...
(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".
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
> 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].
I think the problem is that some of the Turing machines are infinite, so getting 47 million steps in is the _entrypoint_ and you must then run until it halts (or you determine it’s not going to halt somehow). So the search space is unbounded, but it seems like you could snapshot the state of each machine at the 47 million steps and then incrementally search a couple thousand steps forward on each one looking for halting? I may be totally off though, I won’t pretend to fully grok this.
If you get < 47M steps out of all possible 5 state machines, they you have proven the conjecture. A 5 state requires at most 47M states. I don't know if that's an upper bound or a precise estimate, but if they all halt, it's true.
"This conjecture says that 47,176,870 is the maximum number of steps that a 5-state Turing machine can run before halting (starting from all-0 memory tape)."
So, we can run up to this number and either the machine will stop - and we'll go to the next one until exhaust the whole set - or the machine won't stop, and we'll refute the conjecture.
Readit News
> the busy beaver game aims at finding a terminating program of a given size that produces the most output possible.
The Busy Beaver Challenge website [2] also has an explainer page with interactive Turing Machines.
[1] https://en.wikipedia.org/wiki/Busy_beaver
[2] https://bbchallenge.org/story
[1] https://www.sligocki.com//2023/02/02/skelet-34.html
[2] https://news.ycombinator.com/item?id=34689068 and
[1] https://oeis.org/draft/A333479
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_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
which has similarly bizarre properties about it being as hard as all of the rest of mathematics to calculate digits of this number.
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/Chai...
"This conjecture says that 47,176,870 is the maximum number of steps that a 5-state Turing machine can run before halting (starting from all-0 memory tape)."
So, we can run up to this number and either the machine will stop - and we'll go to the next one until exhaust the whole set - or the machine won't stop, and we'll refute the conjecture.
Deleted Comment
Deleted Comment