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 to explain 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 sequence of numbers". Also see Godel's incompleteness. A bit mind-blowing that you have sequences of integers you can't "know" (i.e., compute or verify), but that's about it. There's no chance of this being useful in the system of mathematics we have today.
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."
So then if the BB sequence has finitely many entries. What does it mean that it grows faster than any computable sequence? A finite sequence can't have any asymptotic behavior right?
Essentially yes, but it's simpler and stronger than that: Any oracle that can output BB(n) given n, can be harnessed to solve the halting problem. Exercise! Try to show that: For any computable integer sequence U, BB(n) > U(n) for all but finitely many exceptions.
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.
No, high enough busy beaver numbers are not computable. They can be defined but there's no way to know what they are.
That is because if you could compute BB(n) for arbitrary n, you could run a Turing machine for BB(n)+1 steps and if it hasn't stopped yet then you know that the input corresponds to a machine that never halts. So it's impossible to compute BB(n) for arbitrary n, because doing so is equivalent to the halting problem.
Even for very small n you can create Turing machines where it's incredibly hard to prove that they halt: for n=25 you can create a Turing machine that stops only if the Goldbach conjecture is false. Though that isn't enough to prove it's not computable.
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:
Too many requests
You have exceeded a secondary rate limit.
Please wait a few minutes before you try again;
in some cases this may take up to an hour.
Signing in may provide a higher rate limit if you are not already signed in.
For more on scraping GitHub and how it may affect your rights, please review our Terms of Service.
Ironic how now normal browsing of GitHub and this AI assisted proof is marked as scraping.
I fail to understand why this is interesting or relevant. The README is very non-human-generated and hard to parse or understand.
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
Why is math interesting or relevant at all? Why do anything indeed other than sex and eating?
It's not "relevant" in any sense, but I think many computer folks are fascinated by busy beaver numbers because it's fairly easy to explain 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 sequence of numbers". Also see Godel's incompleteness. A bit mind-blowing that you have sequences of integers you can't "know" (i.e., compute or verify), but that's about it. There's no chance of this being useful in the system of mathematics we have today.
Since Graham's number is computable, it's an expected result even. The Busy Beaver sequence grows faster than any computable sequence.
No, it's not an obvious result. There is a BB(N) > Graham's Number, but in no way N=10 is obvious.
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."
That's correct. In particular, k=8000 is enough (probably much lower)
https://scottaaronson.blog/?p=2725
335 according to https://github.com/jeff87654/busy-beaver/blob/main/ZF/README...
The current "independent of ZF" upper bound seems to be BB(432).
Source: https://wiki.bbchallenge.org/wiki/Logical_independence
So then if the BB sequence has finitely many entries. What does it mean that it grows faster than any computable sequence? A finite sequence can't have any asymptotic behavior right?
Essentially yes, but it's simpler and stronger than that: Any oracle that can output BB(n) given n, can be harnessed to solve the halting problem. Exercise! Try to show that: For any computable integer sequence U, BB(n) > U(n) for all but finitely many exceptions.
Would we expect that Graham's number is less than 47,176,870, since BB(5) = 47,176,870?
I don't follow the logic.
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.
No, high enough busy beaver numbers are not computable. They can be defined but there's no way to know what they are.
That is because if you could compute BB(n) for arbitrary n, you could run a Turing machine for BB(n)+1 steps and if it hasn't stopped yet then you know that the input corresponds to a machine that never halts. So it's impossible to compute BB(n) for arbitrary n, because doing so is equivalent to the halting problem.
Even for very small n you can create Turing machines where it's incredibly hard to prove that they halt: for n=25 you can create a Turing machine that stops only if the Goldbach conjecture is false. Though that isn't enough to prove it's not computable.
Is BB(n) "trivially computable"?
Well, it's computable as in there is a function that computes BB(n) for a specific n, but you'll never know which function it is.
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:
Clicking the author name generates this for me:
Too many requests You have exceeded a secondary rate limit.
Please wait a few minutes before you try again; in some cases this may take up to an hour. Signing in may provide a higher rate limit if you are not already signed in.
For more on scraping GitHub and how it may affect your rights, please review our Terms of Service.
Ironic how now normal browsing of GitHub and this AI assisted proof is marked as scraping.