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
I think the idea here is: how do you write as many 1s as you can - without going into an infinite loop. You gotta stop. You only have 10 states in a state machine to "program" with.
That's BB(10).
The naive way to solve this is to generate all possible 10 state state-machines and see what they produce - take the biggest one.
Except many of those will go into an infinite loop - and you cannot easily detect that (or detect it at all for arbitrary n - see also: halting problem) so you go into an infinite loop too.
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.
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:
There is some notational subtletly here. Strictly speaking, BB(n) represents the output of the BB function for the input n. In that sense BB(n) is computable.
However, the BB function itself is not computable. It makes sense to ask "for what inputs is the BB function computable?". When people talk about BB(n) not being computable, they are really talking about the computability of the BB function at n, not the computability of the integer that happens to be BB(n).
BB(10) is computable. That doesn’t mean anyone can actually figure out what it is. It doesn’t even mean it’s theoretically possible to do so. Computable just means that there exists a turing machine that will output the digits.
It's hard or maybe impossible to figure out what BB(10) is. But abstractly, it is some finite integer. That finite integer is trivially computable: make a turing machine that hardcodes all the digits and outputs them one by one. You can't know that this machine actually produces BB(10) if you don't know what BB(10) is, but that's separate from the question of whether the number itself is computable.
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).
As others have said, the sequence is infinite, though unknowable. Even if math can't say what the precise value is, it can still prove things about the shape of the sequence.
As a simple example, we know that BB(1000) <= BB(1001) (since you can encode the longest running 1000-TM with an extra, unused state as a 1001-TM) even though we will never know either of those values.
The argument that it grows faster than any computable function is similar in that it proves things without knowing concrete numbers. (I'd have to look up the details of the proof to say more)
You should be able to prove it by showing that the existence of a faster-growing computable function lets you solve the halting problem.
Assume f(x) is computable and grows faster than BB(x). We can create a computable g(x) where g(x) > BB(x) for all x, by setting g(x) = f(x) + C for some suitable constant.
Now we create a computer program that does the following. 1. Get the size of the input program and compute g(n). 2. Run the input program for g(n) steps. 3. If it stopped, return true. If it's still running, return false.
This solves the halting problem. Since a computer program can't solve the halting problem, this program can't exist. Everything except "compute g(n)" is straightforward, so there must be no such function g, and no such function f.
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.
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 the result, you are just reporting something without having computed it.
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".
The busy beaver function is uncomputable. That is well understood. However, for any given n, there is a number BB(n). Since that number is an integer, it is computable, even though it is the value of an incomputable function applied to a particular n. In particular, for numbers > 5, we have no idea what that number is. But whatever number it is, that number is computable.
Look at the post that I was responding to. It made the bad inference that because Graham's Number is computable, it ought to be smaller than BB(10). That confuses computability of a given number with computability of a function.
Computable doesn't mean that you can write it down the number that is the value, given an oracle that tells you the value. It means that you know that it the number you are writing down is the right one, because you computed it.
You can always exhaustively run all Turing machines of a given size, at each step comparing the state & tape to all previous steps. If they ever reach the same state with the same tape as a previous step, they're in an infinite loop and never halt. If not, they eventually reach the halt state. BB(n) is computable. But BB is not computable, because there's no general algorithm requiring finite storage and time which computes the results of BB(n) for all n. You have to brute-force it for every positive integer n, which takes infinite time (and space) and is therefore not computable.
There is no requirement to have a recurring state when not halting. Indeed, the most trivial machine "write 1 and move right", will never have the same tape state.
First, TMs don't have a stack. Second, still no recurrent state needed.
Extending a state with additional variables doesn't make a unique state less unique anyway, so "total state" is always more or same unique as "just tape".
Some turing machine variants have multiple tapes, effectively registers.
If the tape, instruction position, and all other variables are the same as any previous step, then the deterministic machine is going to continue to find itself in that loop, and never halt.
Think Collatz like functions - if the output starts into a loop, you know the end result.
However, any program trying to detect all loops by maintaining a bloom filter of every previous state doesnt work, that drags any computation down by a scale of its inputs^runtime.
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"
I don’t think such a bound in itself is interesting, unless the proof reveals some strategy to prove more. There are infinitely potential bounds to BB(n), why is this particular case BB(10) > G useful for understanding fast growing functions?
First, an upper bound would be more useful to understand BB. But second, out of all large numbers, does this one give any information? We’ll have to see. The fact in itself is useless.
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.
And nowadays LLMs are the experts. So. It will explain it to you if you ask. And it does a very nice job. You'll probably need to lose the attitude, tho.
The cost of the tokens used to output a typical academic paper length document is on the order of cents, even for frontier models. The vast majority of the cost is in the discussion leading up to that final output - there's no reason someone would try to produce a shorter paper just to save tokens.
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
The function BB() is necessarily larger than any function you can compute. It's a surprising/fascinating result.
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
Thanks, I enjoyed that explanation quite a bit (didn't understand everything, but enough to get a major clue).
I think the idea here is: how do you write as many 1s as you can - without going into an infinite loop. You gotta stop. You only have 10 states in a state machine to "program" with.
That's BB(10).
The naive way to solve this is to generate all possible 10 state state-machines and see what they produce - take the biggest one.
Except many of those will go into an infinite loop - and you cannot easily detect that (or detect it at all for arbitrary n - see also: halting problem) so you go into an infinite loop too.
Computation theory is fun.
Why is math interesting or relevant at all? Why do anything indeed other than sex and eating?
Crumbs
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.
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:
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'm not sure what you mean, Graham's number is trivially computable since it is a natural number (finite).
Graham's number is not a sequence, so it doesn't matter that the BB sequence grows faster than any computable sequence.
Given a constanct C, you can construct a constant sequence f(n) = C.
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.
> Given a constanct C, you can construct a constant sequence f(n) = C.
> Since f(n) is trivially computable
That only is true if C is computable.
Integers are what's relevant to BB, and all integers are computable.
So what if we set C = BB(10)?
The integer C is computable. However, we do not know what integer C is without first computing BB(10); and doing that might be not be possible.
But BB(10) is also just an integer. So it should be computable?
There is some notational subtletly here. Strictly speaking, BB(n) represents the output of the BB function for the input n. In that sense BB(n) is computable.
However, the BB function itself is not computable. It makes sense to ask "for what inputs is the BB function computable?". When people talk about BB(n) not being computable, they are really talking about the computability of the BB function at n, not the computability of the integer that happens to be BB(n).
BB(10) is computable. That doesn’t mean anyone can actually figure out what it is. It doesn’t even mean it’s theoretically possible to do so. Computable just means that there exists a turing machine that will output the digits.
It's hard or maybe impossible to figure out what BB(10) is. But abstractly, it is some finite integer. That finite integer is trivially computable: make a turing machine that hardcodes all the digits and outputs them one by one. You can't know that this machine actually produces BB(10) if you don't know what BB(10) is, but that's separate from the question of whether the number itself is computable.
Ah I see now, thank you.
Would we expect that Graham's number is less than 47,176,870, since BB(5) = 47,176,870?
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?
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).
> Any turing machine will either halt or not halt.
I guess this is the crux of the issue for me and what I'm struggling with. This does not seem obvious to me.
What other option is there?
As others have said, the sequence is infinite, though unknowable. Even if math can't say what the precise value is, it can still prove things about the shape of the sequence.
As a simple example, we know that BB(1000) <= BB(1001) (since you can encode the longest running 1000-TM with an extra, unused state as a 1001-TM) even though we will never know either of those values.
The argument that it grows faster than any computable function is similar in that it proves things without knowing concrete numbers. (I'd have to look up the details of the proof to say more)
You should be able to prove it by showing that the existence of a faster-growing computable function lets you solve the halting problem.
Assume f(x) is computable and grows faster than BB(x). We can create a computable g(x) where g(x) > BB(x) for all x, by setting g(x) = f(x) + C for some suitable constant.
Now we create a computer program that does the following. 1. Get the size of the input program and compute g(n). 2. Run the input program for g(n) steps. 3. If it stopped, return true. If it's still running, return false.
This solves the halting problem. Since a computer program can't solve the halting problem, this program can't exist. Everything except "compute g(n)" is straightforward, so there must be no such function g, and no such function f.
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.
To me it seems like the sequence is basically (made up but i hope its clear what I mean) 1, 5, 100, 10000000, NaN, NaN, NaN, NaN...
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 the result, you are just reporting something without having computed it.
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.
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".
> 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.
See https://news.ycombinator.com/item?id=50076267.
The busy beaver function is uncomputable. That is well understood. However, for any given n, there is a number BB(n). Since that number is an integer, it is computable, even though it is the value of an incomputable function applied to a particular n. In particular, for numbers > 5, we have no idea what that number is. But whatever number it is, that number is computable.
Look at the post that I was responding to. It made the bad inference that because Graham's Number is computable, it ought to be smaller than BB(10). That confuses computability of a given number with computability of a function.
Computable doesn't mean that you can write it down the number that is the value, given an oracle that tells you the value. It means that you know that it the number you are writing down is the right one, because you computed it.
You can always exhaustively run all Turing machines of a given size, at each step comparing the state & tape to all previous steps. If they ever reach the same state with the same tape as a previous step, they're in an infinite loop and never halt. If not, they eventually reach the halt state. BB(n) is computable. But BB is not computable, because there's no general algorithm requiring finite storage and time which computes the results of BB(n) for all n. You have to brute-force it for every positive integer n, which takes infinite time (and space) and is therefore not computable.
There is no requirement to have a recurring state when not halting. Indeed, the most trivial machine "write 1 and move right", will never have the same tape state.
Total state, not just tape.
Meaning stack, pointer Location, etc.
First, TMs don't have a stack. Second, still no recurrent state needed.
Extending a state with additional variables doesn't make a unique state less unique anyway, so "total state" is always more or same unique as "just tape".
Some turing machine variants have multiple tapes, effectively registers.
If the tape, instruction position, and all other variables are the same as any previous step, then the deterministic machine is going to continue to find itself in that loop, and never halt.
Think Collatz like functions - if the output starts into a loop, you know the end result.
However, any program trying to detect all loops by maintaining a bloom filter of every previous state doesnt work, that drags any computation down by a scale of its inputs^runtime.
Note that this casually solves the halting problem, usually a hint that something is wrong.
I think people are confusing two ideas.
for all n there is some natural number x such that BB(n) = x
x like all natural numbers is trivially computable.
But BB(n) as a function that you could run and _find_ x, is not computable in general, because it would entail solving the halting problem.
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.
But the BB(n) function is essentially the Halting Problem which is not computable?
IMHO an output of a function being bigger than Graham's number isn't particularly impressive.
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"
That is not the reason it is interesting. Rather, it is interesting because it (at least claims) a new bound on BB(10)
I don’t think such a bound in itself is interesting, unless the proof reveals some strategy to prove more. There are infinitely potential bounds to BB(n), why is this particular case BB(10) > G useful for understanding fast growing functions?
It's impressive that a Turing machine of only 10 states can run for Graham's number steps and still halt.
I'd call it absolutely mind boggling, actually.
> why is this particular case BB(10) < G useful for understanding fast growing functions?
it's... not?
it is useful for understanding BB()
First, an upper bound would be more useful to understand BB. But second, out of all large numbers, does this one give any information? We’ll have to see. The fact in itself is useless.
> First, an upper bound would be more useful to understand BB.
you can't have upper bound without breaking Turing and solving halting problem
> But second, out of all large numbers, does this one give any information? The fact in itself is useless.
yes, it gives info of "OMG BIG NUMBER I KNOW ABOUT, THAT'S SO COOL" quality, like all the rest of recreational mathematics :)
Graham's number is simply a nice checkpoint that invites everyone to learn more about function hierarchies
> you can't have upper bound without breaking Turing and solving halting problem
Not in general, no. But for a fixed n, you can. For example, people have settled the exact value of BB(5).
TREE(3) is interesting as it's not very intuitive that it's even a finite number. Graham's Number is obviously finite.
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.
And this is a fine example of this.
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.
EDIT:
Here's a link explaining this paper:
https://claude.ai/share/81b1380d-ca03-4ecb-8475-8e0bb95ea87e
No I haven't. Because the purpose of a paper is communicating the development in the field. If they aren't doing it, they're bad papers.
How do I know when I read Claude's interpretation of the paper that it's not hallucinating.
Papers are written for experts, not the public.
And nowadays LLMs are the experts. So. It will explain it to you if you ask. And it does a very nice job. You'll probably need to lose the attitude, tho.
The cost of the tokens used to output a typical academic paper length document is on the order of cents, even for frontier models. The vast majority of the cost is in the discussion leading up to that final output - there's no reason someone would try to produce a shorter paper just to save tokens.