←back to thread

BusyBeaver(6) Is Quite Large

(scottaaronson.blog)
271 points bdr | 1 comments | 28 Jun 25 16:53 UTC | HN request time: 0.2s | source
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 #
Straw ◴[28 Jun 25 17:39 UTC] No.44406590[source]▶
The category error is in thinking that BB(748) is in fact, a number. It's merely a mathematical concept.
replies(7): >>44406641 #>>44406756 #>>44406982 #>>44407096 #>>44407244 #>>44407342 #>>44428546 #
bmacho ◴[28 Jun 25 19:14 UTC] No.44407342[source]▶
Let S be a statement. S is called semidecidible (also: Turing recognizable, most commonly "recursively enumerable", abbreviated as "r.e.", but I hate that one) if there is a Turing machine that halts if and only if S is true.

With this definition, we can say that "ZFC is inconsistent" is semidecidible: you run a program that searches for a contradiction.

The question BB(748) =/= 1000 is similarly semidecidable. You can run a program that will rule out 1000 if it is not BB(748).

So they are in the same "category", at least regarding their undecidability.

Also, if you turn "ZFC is consistent" into a number: {1 if ZFC is consistent; 0 if ZFC is inconsistent}, you will see, that BB(748) is not very much different, both are defined (well, equivalently) using the halting of Turing machines, or, the result of an infinite search.

replies(1): >>44428496 #
1. Straw ◴[30 Jun 25 22:15 UTC] No.44428496[source]▶
Yes, I would say that neither is really a number in the traditional sense of the word, nor in constructive analysis.