One problem with LLMs in academic contexts is that because you're being paid by the token, it's resulting in extremely short papers that don't adequately explain the context. It's the same problem with long-standing short papers.
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.
And this is a fine example of this.
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.
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
Source: https://wiki.bbchallenge.org/wiki/Logical_independence
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.
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.
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.