Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

BusyBeaver(6) Is Quite Large

scottaaronson.blog

Post reply on HN
Print view View original

191–200 of 232 posts

Re: BusyBeaver(6) Is Quite Large

#191

Post by Kranar »

Scarblac wrote: post #160
thaumasiotes wrote: post #122

Earlier quoted context omitted.

> 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…

What happens if you take the larger of a and b and run all the Turing machines for that many steps?

Among all possible values of BB(n) for some fixed n, it's the smallest such value that is the true value.

The issue is that there is no way within ZFC to determine which value is the smallest.

Re: BusyBeaver(6) Is Quite Large

#192

Post by wat10000 »

bo1024 wrote: post #186
wat10000 wrote: post #175

Earlier quoted context omitted.

I can accept that there is a lot of nuance on the math side that I’m completely missing, but the Turing machine side is really straightforward. A Turing machine either never stops, or it stops after a finite number of steps. If it stops, the number of steps that it runs is a finite whole number, no different from “three” in its relationship to infinity or its theoretical ability to be written down. This doesn’t depen…

The point is that when it "never stops", there are models of ZFC in which the "infinity" number of steps it runs for isn't considered infinity by the model, it's a made-up "nonstandard" number that is smaller than infinity but larger than any integer. And that model considers that to be "halting", so that model says the TM halts.

That’s just a change of definition. That isn’t really saying that BB(748) is different under a different model, just that there’s a BB’ equivalent for that model and BB’(748) is equal to something else.

Re: BusyBeaver(6) Is Quite Large

#193

Post by wat10000 »

raincole wrote: post #183
wat10000 wrote: post #177

Earlier quoted context omitted.

> ZFC doesn't prevent us from defining a non-standard model where Bar halts after a non-standard number of steps. But it does prevent you from defining a non-standard model where Bar halts after a finite number of steps. Since BB is finite by definition, the non-standard number of steps after which Bar halts cannot be BB(748). I’m pretty sure you and the other commenter have this mixed up. The fact that BB(748) is in…

> I’m pretty sure you and the other commenter have this mixed up. We really don't. > that BB(748) is independent of ZFC > there are different models that have different values of BB(748) > ZFC is insufficient to determine the value of BB(748) These three statements are equivalent. f(n)=X is independent of ZFC means there are different models of ZFC that have different values of f(n). It's a very trivial theorem[0]. I…

My argument has nothing to do with the universe. My argument is that there is a single definition of the BB function and its definition does not allow for different values in different circumstances.

What is “a model” here? Can I say that there’s a model ZFC’ which is the same as ZFC except that 107 is considered to be equivalent to 200, and therefore BB(4) in ZFC’ is actually 200? Or can I say that ZFC’’ says integers only go up to 100 and therefore BB(4) is 100 in that model? Or is it something more restricted than that?

Re: BusyBeaver(6) Is Quite Large

#194

Post by raincole »

raincole wrote: post #166
joelthelion wrote: post #159

Earlier quoted context omitted.

Is it? If it's not possible to prove that it's the best solution to bb(748), does it even exist in any meaningful way?

I'm not sure what you mean. First of all BB(n) is a function so it has value(s). And in theory we can prove BB(748)=X, where X is a plain big natural number, as long as we just assume ZFC is consistent. It's practically impossible, but not fundamentally impossible like proving Con(ZFC) in ZFC itself.

(Late Edit: the above comment was rather sloppy. I meant that we don't know if it's impossible to prove BB(748)=X in ZFC+Con(ZFC). It's not necessarily possible either. We just haven't ruled out the possibility.)

Re: BusyBeaver(6) Is Quite Large

#195

Post by pinkmuffinere »

btilly wrote: post #147
pinkmuffinere wrote: post #124

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…

No, the original was correct. Any computable sequence S(n) must be computed by a specific finite program of fixed length. Once n gets big enough, BB(n) will include the function S(2^n), and therefore will exceed that computable sequence. Given computable sequences may exceed BB(n) for a finite number of terms. But eventually BB(n) will outgrow them, and will never look back.

Just replying to say you’re right! Thanks!

Re: BusyBeaver(6) Is Quite Large

#196

Post by raincole »

wat10000 wrote: post #193
raincole wrote: post #183

Earlier quoted context omitted.

> I’m pretty sure you and the other commenter have this mixed up. We really don't. > that BB(748) is independent of ZFC > there are different models that have different values of BB(748) > ZFC is insufficient to determine the value of BB(748) These three statements are equivalent. f(n)=X is independent of ZFC means there are different models of ZFC that have different values of f(n). It's a very trivial theorem[0]. I…

My argument has nothing to do with the universe. My argument is that there is a single definition of the BB function and its definition does not allow for different values in different circumstances. What is “a model” here? Can I say that there’s a model ZFC’ which is the same as ZFC except that 107 is considered to be equivalent to 200, and therefore BB(4) in ZFC’ is actually 200? Or can I say that ZFC’’ says intege…

> Or can I say that ZFC’’ says integers only go up to 100 and therefore BB(4) is 100 in that model?

You'd be defining a new axiomatic system here, not just a model of ZFC. I don't know how we're going to formalize Turning machine in this system, but if we managed to do it, the value of BB(4) is likely to be indeed 100, at least for some models of this new system.

Roughly speaking, a model of ZFC is a set and a binary relationship over the set, whose members all satisfy every axiom of ZFC. Obviously this super simplified definition does a crazy amount of handwaving.

But we don't need to accept or understand the idea of model. What we need to accept is this simple idea:

An axiomatic system can be consistent, but wrong.

For example, if ZFC is consistent, then T = ZFC+~Con(ZFC) would be consistent as well. But this T is wrong, as it believes ZFC is inconsistent.

Similarly, if ZFC is indeed consistent, then T is wrong about which Turing machines halt. Therefore it would have a wrong value of BB(748) (and many other BB(n)).

However, since ZFC can't prove its own consistency, it can't prove that value is wrong. That's why there are different values of BB(748). Those values are not necessarily equally correct, it's just that ZFC isn't strong enough to prove which one is wrong.

Models, nonstandard natural numbers, etc... are more or less technical details (so mathematicians can avoid scary terms like 'wrong'.)

Re: BusyBeaver(6) Is Quite Large

#197

Post by throwaway81523 »

Xcelerate wrote: post #165
throwaway81523 wrote: post #155

Earlier quoted context omitted.

> It boggles my mind that we ever thought a small amount of text that fits comfortably on a napkin (the axioms of ZFC) would ever be “good enough” to capture the arithmetic truths or approximate those aspects of physical reality that are primarily relevant to the endeavors of humanity. ZFC is way overpowered for that. https://mathoverflow.net/questions/39452/status-of-harvey-fr...

I don’t understand your post. You’re linking to a discussion about the same conjecture I mentioned in another comment 11 hours prior to your comment. Did you mean to link something else?

I didn't notice your other post mentioning the conjecture. Anyway, one thing it might mean is that we humans have a very limited understanding of mathematics.

Re: BusyBeaver(6) Is Quite Large

#198

Post by raincole »

gpm wrote: post #178
raincole wrote: post #171

Earlier quoted context omitted.

Yes, but I'm not "proving BB(748)=X in ZFC" in my previous comment. I clearly stated: > as long as we assume ZFC is consistent In other words, I'm talking about proving BB(748)=X in ZFC+Con(ZFC), which is not fundamentally impossible. It's practically impossible simply because you need to reason out the sheer amount of TMs with 748 states.

Is there reason to believe that there's not a similarly sized turing machine that halts iff Con(ZFC + Con(ZFC)) (which is independent of ZFC+Con(ZFC) by godel's)? Certainly there's some sized machine that does that... it seems to me that all you're doing is playing games with adding axioms to maybe change the exact value of "748"... and I don't even see that you've established that you've successfully changed it.

Well, yes, my previous comment was sloppy. Of course it's also possible that 748 is such a high upper limit that we can add a lot of axioms to ZFC and BB(748) is still independent to it. We just don't know it.

Re: BusyBeaver(6) Is Quite Large

#199

Post by wat10000 »

raincole wrote: post #196
wat10000 wrote: post #193

Earlier quoted context omitted.

My argument has nothing to do with the universe. My argument is that there is a single definition of the BB function and its definition does not allow for different values in different circumstances. What is “a model” here? Can I say that there’s a model ZFC’ which is the same as ZFC except that 107 is considered to be equivalent to 200, and therefore BB(4) in ZFC’ is actually 200? Or can I say that ZFC’’ says intege…

> Or can I say that ZFC’’ says integers only go up to 100 and therefore BB(4) is 100 in that model? You'd be defining a new axiomatic system here, not just a model of ZFC. I don't know how we're going to formalize Turning machine in this system, but if we managed to do it, the value of BB(4) is likely to be indeed 100, at least for some models of this new system. Roughly speaking, a model of ZFC is a set and a binary…

Am I understanding you correctly that there’s is one specific finite integer which equals BB(748), but that some models of ZFC will say it’s a different one, and it’s just not correct?

And since we can find a four-state Turing machine that runs for more than 100 steps before halting, ZFC’’ is just not correct when it says that BB(4) = 100, but we still say that 100 is the value in that model?

Re: BusyBeaver(6) Is Quite Large

#200

Post by Kranar »

wat10000 wrote: post #199
raincole wrote: post #196

Earlier quoted context omitted.

> Or can I say that ZFC’’ says integers only go up to 100 and therefore BB(4) is 100 in that model? You'd be defining a new axiomatic system here, not just a model of ZFC. I don't know how we're going to formalize Turning machine in this system, but if we managed to do it, the value of BB(4) is likely to be indeed 100, at least for some models of this new system. Roughly speaking, a model of ZFC is a set and a binary…

Am I understanding you correctly that there’s is one specific finite integer which equals BB(748), but that some models of ZFC will say it’s a different one, and it’s just not correct? And since we can find a four-state Turing machine that runs for more than 100 steps before halting, ZFC’’ is just not correct when it says that BB(4) = 100, but we still say that 100 is the value in that model?

In all models where BB(748) = F and F is actually finite, then F will be the same in all such models. There can't be two models that disagree about the value of F for some actual natural number. It's only in models where BB(748) = Q where Q != F then Q is necessarily not actually finite and hence not an actual natural number.

From within those models Q satisfies all the properties of being a natural number but it's not actually a natural number. Q is some successor of 0, you can add 1 to Q to get another distinct mathematical object, there is some predecessor to Q called P so that P + 1 = Q, etc etc... Q satisfies all the properties within ZFC of being a natural number but it isn't an actual natural number.

Furthermore if ZFC is consistent then it's impossible for any model of ZFC to have BB(4) = 100. ZFC is sufficiently powerful to prove that BB(4) != 100, it is not sufficiently powerful enough to prove that BB(748) = F for some actual natural number F.

Post reply on HN