←back to thread

BusyBeaver(6) Is Quite Large

(scottaaronson.blog)
271 points bdr | 1 comments | | HN request time: 0.199s | 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 #
1. red75prime ◴[] No.44408495[source]
> It boggles my mind that a number (an uncomputable number, granted) like BB(748) can be "independent of ZFC".

It's BB(n) that is incomputable (that is there's no algorithm that outputs the value of BB(n) for arbitrary n).

BB(748) is computable. It's, by definition, a number of ones written by some Turing machine with 748 states. That is this machine computes BB(748).

> It feels like a category error or something.

The number itself is just a literally unimaginably large number. Independence of ZFC comes in when we try to prove that this number is the number we seek. And to do that you need theory more powerful than ZFC to capture properties of a Turing machine with 748 states.