Live data from Hacker News

BusyBeaver(6) Is Quite Large

scottaaronson.blog

121–130 of 232 posts

Re: BusyBeaver(6) Is Quite Large

#121
post #63

Earlier quoted context omitted.

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).

I think the more correct statement is that there are different models of ZFC in which BB(748) are different numbers. People find that weird because they don't think about non-standard models, as arguably they shouldn't.

How is that possible? That implies there’s at least one specific program whose execution changes based on the ZFC model. The rules of program execution are so simple, it doesn’t make sense that they’d change based on anything like that.

Re: BusyBeaver(6) Is Quite Large

#122
post #20
post #14

Earlier quoted context omitted.

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.

Not an expert, but I've read about this a bit because it bothered me also and I think this is the answer: Most of these 'uncomputable' problems are uncomputable in the sense of the halting problem: you can write down an algorithm that should compute them, but it might never halt. That's the sense in which BB(x) is uncomputable: you won't know if you're done ever, because you can't distinguish a machine that never hal…

> Most of these 'uncomputable' problems are uncomputable in the sense of the halting problem: you can write down an algorithm that should compute them, but it might never halt. That's the sense in which BB(x) is uncomputable: you won't know if you're done ever, because you can't distinguish a machine that never halts from one that just hasn't halted yet (since it has an infinite number of states, you can't just wait for a loop).

> So presumably the independence of a number from ZFC is like that also: you can't prove it's the value of BB(745) because you won't know if you've proved it; the only way to prove it is essentially to run those Turing machines until they stop and you'll never know if you're done.

These aren't similar ideas. You can't know if a machine that hasn't halted yet will ever halt. But you can easily know if a machine that has already halted was going to halt.

Independence is the second case. For the value of BB(x) to be independent of ZFC, one of two things must hold:

(1) ZFC is inconsistent, and therefore all statements are independent of it.

(2) ZFC is consistent with two different statements, "BB(x) = a" and "BB(x) = b" for two different a, b. This means that a disproof of either statement cannot exist.

This, in turn, means that there is no observation you could ever make that would distinguish between the values a and b (for the identity of BB(x)). No matter what you believe the value of BB(x) might secretly be, there are no consequences; nothing anywhere could ever change if the value turned out to be different. Because, if there were an observable consequence of the value being different, the hypothetical observation of that consequence would be a disproof of the value that didn't cause it, and no such disproof can exist.

Neither value, a or b, can be more true than the other as the answer to the question "what is BB(x)?". It doesn't make sense to consider that question to have an answer at all.

Re: BusyBeaver(6) Is Quite Large

#123
> For those tuning in from home, here BB(6) is the 6th Busy Beaver number, i.e. the maximum number of steps that a 6-state Turing machine with a {0,1} alphanet can take before halting, when run on an initially all-0 input tape.

Oh! Of course! That sure clears things up for this non-expert. This is clearly a hardcore blog for people who have been doing this kind of research for decades. Kind of awesome to stumble upon something so unapologetically dense and jargony and written for a very specific audience!

Re: BusyBeaver(6) Is Quite Large

#124
post #96
post #79

People on the bbchallenge Discord server are keen to speculate on how many Turing Machine states are needed to surpass Graham's Number, which is vastly larger than the 2^^2^^2^^9 achieved by the latest BB(6) champion. We know from the functional busy beaver [1] that Graham behaviour can come surprisingly early; a 49-bit lambda term suffices. There are only 77519927606 closed lambda terms of at most that size [2], com…

I can't pretend to be an expert, but I'll argue BB(7) is probably larger than Graham's number. BB has to grow faster than any computable sequence. What exactly that means concretely for BB(7) is... nothing other than handwaving... but it sort of means it needs to walk up the "operator strength" ladder very quickly... it eventually needs to grow faster than any computable operator we define (including, for example, up…

Apologies if this feels adversarial, but I think your informal proof has an error, and I think I can explain it!

Your proof rests primarily on this assertion:

> BB has to grow faster than any computable sequence.

This is almost true! BB(n) has to grow faster than any computable sequence _defined by an n-state Turing machine_. That last part is really important. (Note that my restatement is probably incorrect too, it is just correct enough to point out the important flaw I saw in your statement). This means that up-arrow^f(n) _can_ be larger than BB(n) — up-arrow^f(n) is not restricted by a Turing machine at all. As an easy example, consider f(n) = BB(n)^2.

You may still be right about BB(7) being bigger than Graham’s number, even if your proof is not bulletproof

Re: BusyBeaver(6) Is Quite Large

#125
post #96

Earlier quoted context omitted.

I can't pretend to be an expert, but I'll argue BB(7) is probably larger than Graham's number. BB has to grow faster than any computable sequence. What exactly that means concretely for BB(7) is... nothing other than handwaving... but it sort of means it needs to walk up the "operator strength" ladder very quickly... it eventually needs to grow faster than any computable operator we define (including, for example, up…

Apologies if this feels adversarial, but I think your informal proof has an error, and I think I can explain it! Your proof rests primarily on this assertion: > BB has to grow faster than any computable sequence. This is almost true! BB(n) has to grow faster than any computable sequence _defined by an n-state Turing machine_. That last part is really important. (Note that my restatement is probably incorrect too, it…

one of the things that does come out of BB is that BB(n)^2>>BB(n+c) for some very small constant c (I would be surprised if c>2)

Re: BusyBeaver(6) Is Quite Large

#126
post #63

Earlier quoted context omitted.

I think the more correct statement is that there are different models of ZFC in which BB(748) are different numbers. People find that weird because they don't think about non-standard models, as arguably they shouldn't.

How is that possible? That implies there’s at least one specific program whose execution changes based on the ZFC model. The rules of program execution are so simple, it doesn’t make sense that they’d change based on anything like that.

Because what it means to "halt in finite time" has different meanings in different models, because time is measured with different numbers.

Re: BusyBeaver(6) Is Quite Large

#127

> For those tuning in from home, here BB(6) is the 6th Busy Beaver number, i.e. the maximum number of steps that a 6-state Turing machine with a {0,1} alphanet can take before halting, when run on an initially all-0 input tape. Oh! Of course! That sure clears things up for this non-expert. This is clearly a hardcore blog for people who have been doing this kind of research for decades. Kind of awesome to stumble upon…

The definition there is standard undergraduate computer science theory. Maybe not standard for software engineering though.

Re: BusyBeaver(6) Is Quite Large

#128

> For those tuning in from home, here BB(6) is the 6th Busy Beaver number, i.e. the maximum number of steps that a 6-state Turing machine with a {0,1} alphanet can take before halting, when run on an initially all-0 input tape. Oh! Of course! That sure clears things up for this non-expert. This is clearly a hardcore blog for people who have been doing this kind of research for decades. Kind of awesome to stumble upon…

That should be enough for someone with an undergrad CS education to at least get a sense of what's going on if they haven't encountered the busy beaver problem before.

Is it niche jargon, absolutely, but to say it's only accessible to people who have put in decades is selling yourself short.

Re: BusyBeaver(6) Is Quite Large

#129
post #63

Earlier quoted context omitted.

I think the more correct statement is that there are different models of ZFC in which BB(748) are different numbers. People find that weird because they don't think about non-standard models, as arguably they shouldn't.

Isn't that incompatible with the models being consistent? Suppose model A proves BB(748) = X and model B proves BB(748) = Y > X. But presumably the models can interpret running all size 748 Turing machines for Y steps. Either one of the machines halts at step Y (forming a proof within A that BB(748) >= Y contradicting the assumed proof within A that BB(748) = X I'm guessing the only way this could ever work would be…

The issue is that X and Y are not actual natural numbers. They are mathematical objects that satisfy all the ZFC axioms and Peano arithmetic but are infinitely large. The issue is that ZFC underspecifies natural numbers.

Re: BusyBeaver(6) Is Quite Large

#130

Earlier quoted context omitted.

Apologies if this feels adversarial, but I think your informal proof has an error, and I think I can explain it! Your proof rests primarily on this assertion: > BB has to grow faster than any computable sequence. This is almost true! BB(n) has to grow faster than any computable sequence _defined by an n-state Turing machine_. That last part is really important. (Note that my restatement is probably incorrect too, it…

one of the things that does come out of BB is that BB(n)^2>>BB(n+c) for some very small constant c (I would be surprised if c>2)

Sure, but the example I'm providing is just meant to illustrate that BB(n) is not greater than arbitrary f(n). I'm not trying to provide the biggest number, I'm trying to illustrate that the sketched-out proof is incorrect. If you want me to provide a bigger number, I suppose another easy example is to define f(n) = BB(BB(n)).

Edit: Oh sorry, I see I misread the direction of your greater than signs. Leaving comments as-is though, hopefully that results in the least confusion

Post reply on HN