Busy beaver numbers are interesting from a computational perspective. They verge in some ways on unknowable, but as this post shows, sometimes there is some knowability, if you will. I've always enjoyed this blog post about them https://www.scottaaronson.com/writings/bignumbers.html
It's not "relevant" in any sense, but I think many computer folks are fascinated by busy beaver numbers because it's fairly easy what the numbers mean - it's just a Turing machine with no icky math.
That said, functionally, they're more or less a restatement of the halting problem, essentially "if the halting problem was a number". Also see Godel's incompleteness. A bit mind-blowing that you have numbers you can't "know" (i.e., compute or verify), but that's about it.
People have been working on them for fun, with no chance of any of this being applicable to anything, so throwing AI at it to produce new results seems a bit tone-deaf to me.
Every BB(n) is trivially computable, since any integer is computable. So for every BB(n), there is a computable sequence that grows faster than the BB numbers through n (annoyingly, given the word "grows", this can just be the constant sequence of BB(n) + 1).
So for any given computable number, the fact that it's computable gives no intrinsic reason to believe it's smaller than BB(n) for any particular n.
I feel like I keep failing to wrap my mind around computability in the same way over and over.
Would the following statement be correct?
"There is a turing machine that cannot be proven whether it will terminate or not. For any n we can construct a proof that it will run longer than n. But we cannot construct a proof that for any n it will run longer than n. Due to this particular turing machine, BB(k) cannot be determined for k large enough to admit that turing machine."
It's code golf played with Turing machines. The game is: Make the smallest Turing machine whose runtime is bigger than Graham's number, but still terminates. The record right now is 10 states. At least 6 states are needed because any Turing machine with at most 5 states, that finishes running, has a runtime of at most 47,176,870, which is less than Graham's number. In summary:
That said, functionally, they're more or less a restatement of the halting problem, essentially "if the halting problem was a number". Also see Godel's incompleteness. A bit mind-blowing that you have numbers you can't "know" (i.e., compute or verify), but that's about it.
People have been working on them for fun, with no chance of any of this being applicable to anything, so throwing AI at it to produce new results seems a bit tone-deaf to me.
Every BB(n) is trivially computable, since any integer is computable. So for every BB(n), there is a computable sequence that grows faster than the BB numbers through n (annoyingly, given the word "grows", this can just be the constant sequence of BB(n) + 1).
So for any given computable number, the fact that it's computable gives no intrinsic reason to believe it's smaller than BB(n) for any particular n.
Would the following statement be correct?
"There is a turing machine that cannot be proven whether it will terminate or not. For any n we can construct a proof that it will run longer than n. But we cannot construct a proof that for any n it will run longer than n. Due to this particular turing machine, BB(k) cannot be determined for k large enough to admit that turing machine."
https://scottaaronson.blog/?p=2725