←back to thread

BusyBeaver(6) Is Quite Large

(scottaaronson.blog)
271 points bdr | 7 comments | 28 Jun 25 16:53 UTC | HN request time: 1.028s | source | bottom
Show context
Scarblac ◴[28 Jun 25 17:29 UTC] No.44406478[source]▶
It boggles my mind that a number (an uncomputable number, granted) like BB(748) can be "independent of ZFC". It feels like a category error or something.
replies(12): >>44406574 #>>44406590 #>>44407165 #>>44407378 #>>44407396 #>>44407448 #>>44407506 #>>44407549 #>>44408495 #>>44409048 #>>44410736 #>>44413092 #
tromp ◴[28 Jun 25 19:20 UTC] No.44407378[source]▶
What makes BB(748) independent of ZFC is not its value, but the fact that one of the 748-state machines (call it TM_ZFC_INC) looks for an inconsistency (proof of FALSE) in ZFC and only halts upon finding one.

Thus, any proof that BB(748) = N must either show that TM_ZF_INC halts within N steps or never halts. By Gödel's famous results, neither of those cases is possible if ZFC is assumed to be consistent.

replies(4): >>44407526 #>>44408279 #>>44409464 #>>44411963 #
Diggsey ◴[28 Jun 25 21:22 UTC] No.44408279[source]▶
I think what's most unintuitive is that most (all?) "paradoxes" or "unknowables" in mathematics involve infinities. When limiting ourselves to finite whole numbers, paradoxes necessarily disappear.

BB(748) is by definition a finite number, and it has some value - we just don't know what it is. If an oracle told us the number, and we ran TM_ZFC_INC that many steps we would know for sure whether ZFC was consistent or not based on whether it terminated.

The execution of the turing machine can be encoded in ZFC, so it really is the value of BB(748) that is the magic ingredient. Somehow even knowledge of the value of this finite number is a more potent axiomatic system than any we've developed.

replies(4): >>44409070 #>>44410462 #>>44410587 #>>44411863 #
raincole ◴[29 Jun 25 04:57 UTC] No.44410462[source]▶
BB(748) is a finite number, but I'd argue its magic also comes from infinites: the fact some Turing Machines run forever and never halt.
replies(1): >>44411047 #
1. joelthelion ◴[29 Jun 25 07:41 UTC] No.44411047[source]▶
Is it? If it's not possible to prove that it's the best solution to bb(748), does it even exist in any meaningful way?
replies(1): >>44412643 #
2. raincole ◴[29 Jun 25 12:41 UTC] No.44412643[source]▶
I'm not sure what you mean. First of all BB(n) is a function so it has value(s).

And in theory we can prove BB(748)=X, where X is a plain big natural number, as long as we just assume ZFC is consistent. It's practically impossible, but not fundamentally impossible like proving Con(ZFC) in ZFC itself.

replies(2): >>44413172 #>>44415709 #
3. gpm ◴[29 Jun 25 13:53 UTC] No.44413172[source]▶
Proving BB(748)=X for some concrete X in ZFC is equivalent to proving Con(ZFC) in ZFC.
replies(1): >>44413196 #
4. raincole ◴[29 Jun 25 13:56 UTC] No.44413196{3}[source]▶
Yes, but I'm not "proving BB(748)=X in ZFC" in my previous comment.

I clearly stated:

> as long as we assume ZFC is consistent

In other words, I'm talking about proving BB(748)=X in ZFC+Con(ZFC), which is not fundamentally impossible. It's practically impossible simply because you need to reason out the sheer amount of TMs with 748 states.

replies(1): >>44413714 #
5. gpm ◴[29 Jun 25 15:02 UTC] No.44413714{4}[source]▶
Is there reason to believe that there's not a similarly sized turing machine that halts iff Con(ZFC + Con(ZFC)) (which is independent of ZFC+Con(ZFC) by godel's)?

Certainly there's some sized machine that does that... it seems to me that all you're doing is playing games with adding axioms to maybe change the exact value of "748"... and I don't even see that you've established that you've successfully changed it.

replies(1): >>44416535 #
6. raincole ◴[29 Jun 25 19:37 UTC] No.44415709[source]▶
(Late Edit: the above comment was rather sloppy. I meant that we don't know if it's impossible to prove BB(748)=X in ZFC+Con(ZFC). It's not necessarily possible either. We just haven't ruled out the possibility.)
7. raincole ◴[29 Jun 25 21:22 UTC] No.44416535{5}[source]▶
Well, yes, my previous comment was sloppy. Of course it's also possible that 748 is such a high upper limit that we can add a lot of axioms to ZFC and BB(748) is still independent to it. We just don't know it.