Get the top HN stories in your inbox every day.
v64
SilasX
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).
H8crilA
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 :)
v64
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.
stouset
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.
P_v ~ 4.65e185
P_v < G_64
P_v < log10(G_64)
P_v < log10^(2)(G_64)
…
P_v < log10^(P_v)(G_64)
G_64 < BB(18)
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.
actually_a_dog
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.
---
[0]: https://en.wikipedia.org/wiki/Ramsey%27s_theorem
[1]: https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Computation...
[2]: https://blogs.scientificamerican.com/roots-of-unity/moores-l...
galaxyLogic
> 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.
perl4ever
The word on this, I believe, is:
'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'
dandanua
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)).
tromp
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.
dwohnitmok
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}).
dandanua
That's what I'm talking about, you can't say that BB(748) is uncomputable.
danielheath
Computability is not the same thing as proof. “Not computable” means “no program which is known to halt can answer this”.
dandanua
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.
SilasX
Yes! The comment is also wrong because defining BB(748) requires defining busy beaver functions, which take more than those seven characters.
I was going to reply to say that on the Reddit thread but it’s over a year old and doesn’t accept new comments.
undefined
auggierose
Here is the link to the journal version of this (I like my DOI's): https://doi.org/10.25088/ComplexSystems.25.4.297
chime
Computerphile made a good video on BB Turing Machines: https://www.youtube.com/watch?v=CE8UhcyJS0I
thriftwy
You can go the other way, what's the simplest yet unprovable axiom set relevant for the turing machine? You can try encoding this one.
undefined
Get the top HN stories in your inbox every day.
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.
[1] https://scottaaronson.blog/?p=4916
[2] https://turingmachinesimulator.com/shared/vgimygpuwi
[3] https://www.reddit.com/r/math/comments/gdfes1/a_turing_machi...