←back to thread

BusyBeaver(6) Is Quite Large

(scottaaronson.blog)
271 points bdr | 1 comments | | HN request time: 0s | 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 #
Straw ◴[] No.44406611[source]
Sure, if someone just gives you the number, ZFC can represent it. But ZFC cannot prove that the value is correct, so how do you know you have the right number? Use a stronger proof system? Go a bit bigger and same issue.
replies(3): >>44406771 #>>44406894 #>>44410514 #
1. thechao ◴[] No.44406894[source]
We need to distinguish between a computer that's equivalent to BB(n), and a computer big enough to compute the value of the number that is BB(n). By (terrible) analogy: a 4004 can be made to write a finite loop that describes how many FLOPs the number 1 supercomputer can compute without, itself, being able to usefully perform the computations of that supercomputer. (The 4004 will run out of memory/addressable disk space.) Similarly, we can no longer build decidable programs in ZFC that can compute the number BB(748). Scott is saying that they now think this "disassociation" might occur at BB(7)!