←back to thread

BusyBeaver(6) Is Quite Large

(scottaaronson.blog)
271 points bdr | 1 comments | | HN request time: 0.21s | source
Show context
Scarblac ◴[] 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 #
ChadNauseam ◴[] No.44406574[source]
The number itself is not independent of ZFC. (Every integer can be expressed in ZFC.) What's independent of ZFC is the process of computing BB(748).
replies(3): >>44406611 #>>44407419 #>>44407440 #
bo1024 ◴[] No.44407440[source]
I think the more correct statement is that there are different models of ZFC in which BB(748) are different numbers. People find that weird because they don't think about non-standard models, as arguably they shouldn't.
replies(3): >>44408558 #>>44408970 #>>44409119 #
Strilanc ◴[] No.44408970[source]
Isn't that incompatible with the models being consistent?

Suppose model A proves BB(748) = X and model B proves BB(748) = Y > X. But presumably the models can interpret running all size 748 Turing machines for Y steps. Either one of the machines halts at step Y (forming a proof within A that BB(748) >= Y contradicting the assumed proof within A that BB(748) = X < Y) or none of the machines halts at step Y (forming a proof within B that BB(748) != Y contradicting the assumed proof within B that BB(748) = Y).

I'm guessing the only way this could ever work would be some kind of nastiness like X and Y aren't nailed down integers, so you can't tell if you've reached them or not, and somehow also there's a proof they aren't equal.

replies(1): >>44409368 #
1. Kranar ◴[] No.44409368[source]
The issue is that X and Y are not actual natural numbers. They are mathematical objects that satisfy all the ZFC axioms and Peano arithmetic but are infinitely large. The issue is that ZFC underspecifies natural numbers.