Note that this bound has since been improved to 748 [1] and you can actually view and run this 748 state turing machine here [2]. This comment on reddit [3] is a good attempt at condensing all the information down and explaining why this means proving the value of BB(748) is independent from ZFC.
If you already know the background knowledge, the Reddit comment’s key point is:
There’s a 748-state Turing machine that (is isomorphic to a program that) grinds out all the provable theorems of ZFC and halts if it proves contradictory theorems.
Calculating BB(748) under ZFC requires proving that this program never halts, which would double as a proof of ZFC’s — and therefore its own — consistency. By Gödel’s Incompleteness, you can’t do that (as a system can’t prove it’s own consistency).
Sorry for a low quality/content comment, but this area has always seemed to me the most beautiful part of mathematics (not just theoretical computer science). The joke about robot overlords still pondering on BB(<low double digit number>) billions of years into the future is a good summary of this feeling :)
Even calculating BB(30) exhaustively would require more energy than we have in the observable universe. The fact that functions like BB() have actual, finite values, but that they're unknowable both due to our physical and logical limitations, is humbling in an ineffable way.
By physical limitations, we also include space. If you could represent each digit of Graham’s number (G_64) in a Planck volume, you couldn’t fit even an incomprehensibly tiny fraction of it in the observable universe.
No only that, but the number of digits in G_64 (~log10(G_64)) exceeds the number of Planck volumes (V_p) in our universe too. As does the number of digits in that number (~log10^2(G_64)). And so on and so on, for a number of times itself exceeding the number of Planck volumes in the universe.
That said, we can grow bigger still. Scott Aaron defined a closely-related concept called a Beeping Busy Beaver that grows uncomputably even if we had an oracle for BB(n). That is, even if we had access to a magic genie that could tell us any BB(n), this function BBB(n) even still grows uncomputably. It’s almost as if there’s “sizes” of uncomputability much the same as there are distinct sizes of infinity.
Note that these are measured in bits, and that it would take
18 * 2 * (2 + ceil(log(18))) = 252 bits to represent the 18-state TM computing G_64.
The 847 state TM whose halting is known to be unprovable in ZFC takes 847 * 2 * (2 + ceil(log(847)) = 20328 bits to describe.
Meanwhile, in a mere 215 bits, we can encode a Laver table program [2] whose halting is not known to be provable in ZFC [3]. I.e. it may or may not be unprovable, we don't know yet.
> It’s almost as if there’s “sizes” of uncomputability much the same as there are distinct sizes of infinity.
There is, isn't there? A TM plus an oracle can solve the halting problem for the original TM but is just as susceptible to a halting problem of its own, and this goes on ad infinitum.
This very much reminds me of the following story told by Joel Spencer regarding Ramsey numbers[0]:
> Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens. [1]
Although Ramsey numbers are computable, they are really, really hard to compute exactly, and we don't have great upper or lower bounds for them, either.
Edit: I found the version of the story that I was more familiar with that had a 1 year time limit on it[2]:
> Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack.
> The joke about robot overlords still pondering on BB
This starts to sound like Hitchhiker's Guide to Galaxy.
I always thought the answer 42 was just an absurd joke
but now I'm starting to think that Douglas Adams must
have known about Busy Beaver.
'The first strong law of small numbers (Gardner 1980, Guy 1988, 1990) states "There aren't enough small numbers to meet the many demands made of them."
The second strong law of small numbers (Guy 1990) states that "When two numbers look equal, it ain't necessarily so."'
'...the first few values of the interpolating polynomial (n^4-6n^3+23n^2-18n+24)/24 (erroneously given in Guy (1990) with a coefficient 24 instead of 23) for n=1, 2, ... are 1, 2, 4, 8, 16, .... Thus, the polynomial appears to give the powers of 2, but then continues 31, 57, 99, ... (OEIS A000127). In fact, this sequence gives the maximal number of regions obtained by joining n points around a circle by chords'
That reddit comment is very nice, though a little bit misleading at the end.
> I can define this finite integer with only 7 characters, BB(748), but it can't be computed at all!
is not true. The correct value of BB(748) can't be proved in ZFC, that's true. But we can use a stronger theory. For example, we can take the statement that ZFC is consistent, denoted by Con(ZFC), and add it to ZFC. The new theory ZFC+Con(ZFC) is stronger. So, it could be that ZFC+Con(ZFC) can prove BB(748).
If necessary, we can consider even stronger theory, e.g. ZFC+Con(ZFC)+Con(ZFC+Con(ZFC)).
BB(748) is a finite integer, and all things finite can by definition be computed (in computational theory). Uncomputable things must be of an infinite nature, such as functions from the natural numbers to a boolean, or languages of binary strings.
Strictly speaking saying a single natural number is "computable" is a category error. Only functions can be computable or noncomputable. All other notions of computability must be reduced to a function on the natural numbers (e.g. recognition problems are shorthand for functions on the natural numbers that have a range of {0, 1}).
Surely “uncomputable” here means “uncomputable in ZFC”, no? The fact that you’ve found it in a stronger theory doesn’t matter, because the value now depends on that stronger theory and may be wrong in ZFC.
The value of every BB(n) is well-defined in ZFC. It can't change if we consider a stronger (and consistent) theory than ZFC. Proving that BB(n) equals to a concrete integer is a different matter – it's either possible or not within your theory.
When I say "the value now depends" I mean the value you computed in that stronger theory is not computable in the weaker one, and therefore the computation depends on the stronger theory, and therefore the value is only correct if the stronger theory is consistent.
No, "not computable" is a property of functions that can accept infinite number of inputs. We can't say that a particular function value is uncomputable, there is no such definition. BB is uncomputable as a function. Yet, we can prove some of its values, because we can prove that some small Turing machines are not halting. To show that something runs forever you have to prove it.
First, programs are defined to be finite in length. Second, for a program to be said to compute a function, it must do so for all possible inputs.
That’s by definition, but there are good reasons why these definitions are useful: if we accept infinite or incomplete programs, everything would be considered computable.
Anyway, your program can only compute BB for a finite number of inputs (depending on how far you bother to expand the “else …” part).
[1] https://scottaaronson.blog/?p=4916
[2] https://turingmachinesimulator.com/shared/vgimygpuwi
[3] https://www.reddit.com/r/math/comments/gdfes1/a_turing_machi...