Graham's Number is notable for being one of the first, being an actual relevant bound in an unrelated proof (not just the output of a function), of teaching people the Up Arrow Notation.
To me, BB(10), TREE(3) etc. being so large is only minorly more impressive than GG(1) where I define I define GG(x) as "Graham's Number + X"
One problem with LLMs in academic contexts is that because you're paying 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.
I'm wondering - have you asked an LLM to flesh-out the paper for you? Or walk you through the details?
I've been hearing stories of mathematicians who are developing a new found appreciation for LLMs by having them explain the other LLM's paper. I guess the paper has the necessary details but possibly not the best exposition.
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.
BB(5) is also computable in the intuitive sense, because we proved its value: 47,176,870. In this sense BB(5) is just as computable as Graham's number. However there is likely a Busy Beaver number >5 that is intuitively uncomputable, such that there is no non-cheating algorithm which computes it. A cheating algorithm would be one that requires the knowledge of the result in advance to write the algorithm, in which case we wouldn't be able to come up with the algorithm in the first place, and we wouldn't know that the result is correct.
There is also a proof that the function BB(n) (with the free argument n) is uncomputable. However, this alone doesn't mean that e.g. BB(6) (a function with no free parameter) is or isn't intuitively computable. Though if you allow cheating, which is the case for the conventional academic definition of "computability", every particular constant function (that is, without a free parameter) would be considered "computable". Though that definition doesn't mean it is intuitively computable, because if you cheat, you aren't really computing something something, you are just reporting something without having computed it.
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?
The BB sequence still has infinitely many entries. Any turing machine will either halt or not halt. For any N, there is a finite set of N-state turing machines which halt, and there is therefore a finite number of steps after which all halting N-state turing machines would halt.
There is a point where these values become uncomputable, but they still exist (for some definition of exist).
Where did you get that the BB sequence would have finitely many entries? You can choose any integer n for BB(n), and there are infinitely many integers.
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.
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, the point stands that 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 write a program that computes BB(n) for arbitrary n, because doing so is equivalent to the halting problem.
And worse, there are some Turing machines where "proving the Turing machine stops" means "proving that a given set of axioms is consistent", where Gödel's incompleteness theorem says that it's impossible to build such a proof. So, that is how there is some n after which the busy beaver number is defined, but is not computable at all.
What I mean is that any given integer is trivially computable.
The busy beaver sequence is not computable (I am aware that somewhere around BB(700), you've encoded the consistency of ZFC). You cannot necessarily compute that BB(n) is a given number. But you can compute larger numbers. There is no such thing as integer that is too large to be computable.
I did slightly fuck up--the English language "every BB(n) is computable" is a bit ambiguous. What I should say is: "for all n, BB(n) is trivially computable, since it is a single integer".
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:
Consider TREE(3) -> https://www.youtube.com/watch?v=3P6DWAwwViU
Graham's Number is notable for being one of the first, being an actual relevant bound in an unrelated proof (not just the output of a function), of teaching people the Up Arrow Notation.
To me, BB(10), TREE(3) etc. being so large is only minorly more impressive than GG(1) where I define I define GG(x) as "Graham's Number + X"
And this is a fine example of this.
I've been hearing stories of mathematicians who are developing a new found appreciation for LLMs by having them explain the other LLM's paper. I guess the paper has the necessary details but possibly not the best exposition.
EDIT:
Here's a link explaining this paper:
https://claude.ai/share/81b1380d-ca03-4ecb-8475-8e0bb95ea87e
I've had a lot of success answering questions like this by asking an LLM. It turns out they understand each other and do a great job explaining.
Here's a link for this paper:
https://claude.ai/share/81b1380d-ca03-4ecb-8475-8e0bb95ea87e
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.
Graham's number is not a sequence, so it doesn't matter that the BB sequence grows faster than any computable sequence.
Since f(n) is trivially computable, we know that BB(n) grows faster than f(n). It follows that there must be some n such that BB(n) > C.
> Since f(n) is trivially computable
That only is true if C is computable.
There is also a proof that the function BB(n) (with the free argument n) is uncomputable. However, this alone doesn't mean that e.g. BB(6) (a function with no free parameter) is or isn't intuitively computable. Though if you allow cheating, which is the case for the conventional academic definition of "computability", every particular constant function (that is, without a free parameter) would be considered "computable". Though that definition doesn't mean it is intuitively computable, because if you cheat, you aren't really computing something something, you are just reporting something without having computed it.
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
There is a point where these values become uncomputable, but they still exist (for some definition of exist).
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.
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, the point stands that 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 write a program that computes BB(n) for arbitrary n, because doing so is equivalent to the halting problem.
And worse, there are some Turing machines where "proving the Turing machine stops" means "proving that a given set of axioms is consistent", where Gödel's incompleteness theorem says that it's impossible to build such a proof. So, that is how there is some n after which the busy beaver number is defined, but is not computable at all.
The busy beaver sequence is not computable (I am aware that somewhere around BB(700), you've encoded the consistency of ZFC). You cannot necessarily compute that BB(n) is a given number. But you can compute larger numbers. There is no such thing as integer that is too large to be computable.
I did slightly fuck up--the English language "every BB(n) is computable" is a bit ambiguous. What I should say is: "for all n, BB(n) is trivially computable, since it is a single integer".
It is not computable, because for high enough n you can't prove that you got the right integer.
And also you can prove that if a sequence a_n is always larger than BB(n) for some n, that sequence a_n is also not computable.