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

161–170 of 232 posts

Re: BusyBeaver(6) Is Quite Large

#161

Post by Scarblac »

boothby wrote: post #112
drdeca wrote: post #69

Earlier quoted context omitted.

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.

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.

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.

Re: BusyBeaver(6) Is Quite Large

#162

Post by meindnoch »

pinkmuffinere wrote: post #144
gpm wrote: post #135

Earlier quoted context omitted.

Math's a cooperative endeavor, I want to know if I'm wrong! I'm not sure I understand the distinction you're trying to make though, and I'm not sure it's right... The argument that BB has to grow faster than any computable sequence is that if we have a computable f(n) where for all n f(n) > BB(n) then we can solve the halting problem by simulating turing machines of size n for f(n) steps and checking if they halt. Ev…

Thanks for the good attitude! Ah, I didn't realize 'computable' had a specific meaning in this domain -- showing the limits of my experience a bit. After looking at the wikipedia page and rereading your sketch, I think it is true that > it eventually needs to grow faster than any computable operator we define I'm not sure if this has implications about how quickly BB() grows compared to the "operator strength" ladder…

>BB(n) will be larger than anything that can be computed in n steps

Who said anything about "n steps"?

BB(n) is about an n-state Turing machine, not "n steps".

Re: BusyBeaver(6) Is Quite Large

#163

Post by edanm »

Diggsey wrote: post #107
tromp wrote: post #57

Earlier quoted context omitted.

What makes BB(748) independent of ZFC is not its value, but the fact that one of the 748-state machines (call it TM_ZFC_INC) looks for an inconsistency (proof of FALSE) in ZFC and only halts upon finding one. Thus, any proof that BB(748) = N must either show that TM_ZF_INC halts within N steps or never halts. By Gödel's famous results, neither of those cases is possible if ZFC is assumed to be consistent.

I think what's most unintuitive is that most (all?) "paradoxes" or "unknowables" in mathematics involve infinities. When limiting ourselves to finite whole numbers, paradoxes necessarily disappear. BB(748) is by definition a finite number, and it has some value - we just don't know what it is. If an oracle told us the number, and we ran TM_ZFC_INC that many steps we would know for sure whether ZFC was consistent or n…

> BB(748) is by definition a finite number, and it has some value - we just don't know what it is. If an oracle told us the number, and we ran TM_ZFC_INC that many steps we would know for sure whether ZFC was consistent or not based on whether it terminated.

This doesn't sound right to me.

You can prove that ZFC is consistent. You could do it today, with or without the magic number, using a stronger axiom system. If an Oracle told you that BB(748) = 100 or whatever, that would constitute proof that ZFC is consistent.

But it wouldn't negate the fact that BB(748) is independent of ZFC, because you haven't proved within the axioms of ZFC that ZFC is consistent, which is what makes it independent.

> I think what's most unintuitive is that most (all?) "paradoxes" or "unknowables" in mathematics involve infinities. When limiting ourselves to finite whole numbers, paradoxes necessarily disappear.

I might be missing something, but all of these assertions deal with finite whole numbers, not infinity. Unless you count a Turing machine running forever an infinity, in which case, it seems counterintuitive to me that encoding a while loop that runs forever somehow makes paradoxes appear.

Re: BusyBeaver(6) Is Quite Large

#164

Post by edanm »

tromp wrote: post #57
Scarblac wrote: post #4

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.

What makes BB(748) independent of ZFC is not its value, but the fact that one of the 748-state machines (call it TM_ZFC_INC) looks for an inconsistency (proof of FALSE) in ZFC and only halts upon finding one. Thus, any proof that BB(748) = N must either show that TM_ZF_INC halts within N steps or never halts. By Gödel's famous results, neither of those cases is possible if ZFC is assumed to be consistent.

> Thus, any proof that BB(748) = N must either show that TM_ZF_INC halts within N steps or never halts. By Gödel's famous results, neither of those cases is possible if ZFC is assumed to be consistent.

Isn't it more accurate to say that any proof that BB(748) = N in ZFC must either show that TM_ZF_INC halts within N steps, or never halts?

Meaning, it's totally possible to prove that BB(748) = N, it just can't be done within the axioms of ZFC?

Re: BusyBeaver(6) Is Quite Large

#165

Post by Xcelerate »

throwaway81523 wrote: post #155
Xcelerate wrote: post #40

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. That the behavior of a six state Turing machine might be unpredictable via a few lines of text does not surprise me in the slightest. A…

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

Re: BusyBeaver(6) Is Quite Large

#166

Post by raincole »

joelthelion wrote: post #159
raincole wrote: post #148

Earlier quoted context omitted.

BB(748) is a finite number, but I'd argue its magic also comes from infinites: the fact some Turing Machines run forever and never halt.

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.

Re: BusyBeaver(6) Is Quite Large

#167

Post by gpm »

pinkmuffinere wrote: post #158
gpm wrote: 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…

I can’t edit my original comment anymore, but replying to say I went on a Wikipedia binge and I think you’re right. Thanks for humoring me and helping me learn!

:)

Re: BusyBeaver(6) Is Quite Large

#168

Post by red75prime »

raincole wrote: post #150
wat10000 wrote: post #145

Earlier quoted context omitted.

> In one model there is an object called Q that satisfies all of the properties in ZFC of being a natural number, but is infinitely large. In this model the Turing Machine halts after Q steps. That doesn’t make any sense. A Turing machine can’t halt after a infinite number of steps. It either halts after a finite number of steps, or it never halts. I’m sure there are models of hypercomputation and corresponding “what…

It's not about hypercomputation. What the commenter above you said doesn't make sense in our daily life, but it makes perfect sense when in comes to non-standard models. You got confused because you're thinking natural numbers as something we can count in real physical world, which is a perfectly sane mental model, and that is why there was a comment above said: > People find that weird because they don't think about…

> The point is not that Q exists in some physical sense in real life

Ultrafinitism? If you'd run the Turing machine that performs BB(748) steps in a physical universe that admits it, you'd get a physical representation of BB(748). If you have a competing theory about which Turing machine computes BB(748), you can run them both alongside in this universe and see with your own eyes which one finishes first.

I guess from ultrafinitist's point of view such universe has different mathematics, but isn't it a fringe viewpoint in mathematical circles?

Re: BusyBeaver(6) Is Quite Large

#170

Post by gpm »

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.

Proving BB(748)=X for some concrete X in ZFC is equivalent to proving Con(ZFC) in ZFC.
Post reply on HN