←back to thread

BusyBeaver(6) Is Quite Large

(scottaaronson.blog)
271 points bdr | 1 comments | | HN request time: 0.31s | 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 #
tromp ◴[] 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 ◴[] 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 #
1. zmgsabst ◴[] No.44409070[source]
You’d know the value in a more powerful system than ZFC (as it includes such an oracle) — but you can already reason about ZFC in a more powerful system.

We already have more powerful systems, but what causes the inability to self-reason is exactly that power: only first order logic can prove its own consistency. Once you get powerful enough to model arithmetic, you can build statements with self-referential weirdness.

I don’t see it as a paradox, but as growth: a sufficiently rich system can pose questions which suggest a richer system — and thereby scaffold up the universe hierarchy.