←back to thread

BusyBeaver(6) Is Quite Large

(scottaaronson.blog)
271 points bdr | 7 comments | | HN request time: 0s | source | bottom
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. drdeca ◴[] No.44407506[source]
No individual number is uncomputable. There’s no pair of a number and proof in ZFC that [that number] is the value of BB(748). And, so, there’s no program which ZFC proves to output the value of BB(748). There is a program that outputs BB(748) though, just like for any other number.
replies(2): >>44408600 #>>44409666 #
2. boothby ◴[] No.44408600[source]
Individual numbers can be uncomputable! For example, take your favorite enumeration of Turing machines, (T1, T2...) and write down a real number in binary where the first bit is 0 if T1 halts and 1 otherwise, second bit is 0 if T2 halts... clearly this number is real and between 0 and 1, but it cannot be computed in finite time.
replies(3): >>44408772 #>>44408950 #>>44411344 #
3. Vecr ◴[] No.44408772[source]
If it had a finite size it would be computable.
4. drdeca ◴[] No.44408950[source]
Pardon, I meant natural number. I should have specified.
5. cvoss ◴[] No.44409666[source]
I think your mistake is your claim that BB(748) is a natural number. For you to know that, you would necessarily have to know an upper bound for the number of steps it takes for the BB-748 machine (whichever machine it is) to halt. But you definitely don't know that.

Related: It's incorrect to claim that each machine either halts or doesn't halt. To know that that dichotomy holds would require having a halting problem algorithm.

replies(1): >>44414135 #
6. Scarblac ◴[] No.44411344[source]
That's a number in R, obviously most of them are uncomputable (there is a countable number of Turing machines).

But for every natural number n there is a trivial Turing machine that just prints n and then halts.

7. drdeca ◴[] No.44414135[source]
I don’t know it in a constructive sense, sure.

It’s still true though. I’m not wrong.