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

141–150 of 232 posts

Re: BusyBeaver(6) Is Quite Large

#141

Post by wat10000 »

Kranar wrote: post #139
wat10000 wrote: post #138

Earlier quoted context omitted.

I don’t get it. Let’s say that BB(748) is 10,000. (I realize the true number is somewhat larger, this is just an example that doesn’t change the argument.) That means there’s one or more Turing machines of that size which run for that many steps. All of the others either run for fewer, or never stop. Running for fewer steps is extremely well defined and I don’t imagine that enters into this. That means there’s issue…

Yes the issue has to do with "never stops". One of the machines that never stops in one model will stop in another model. So in one model a Turing Machine called R never stops. In another model R stops after Q steps. But here's the issue... Q isn't an actual natural number, what it is is some mathematical object that satisfies all of the properties of a natural number in ZFC, but is not an actual natural number. What…

What do you mean, Q isn’t a natural number? If you had unlimited time and paper, you could sit down and run the machine by hand, counting each step, until it reaches the halting state. You will have counted Q steps. Or the machine never stops. There’s no such thing as a machine that stops after a number of steps defined by an infinitely large construct. There are machines that stop after some whole number of steps, and there are machines that don’t stop. There are no others.

If there’s another model where this machine doesn’t stop, then that means that at some point during this process, you reach a particular machine state and tape contents and transition to a different state than you did in the first model. That has to happen, because otherwise the execution follows the same process as before, and halts at Q steps. But the mechanics of the machine don’t depend on your theory. They’re just state transitions and tape operations.

Re: BusyBeaver(6) Is Quite Large

#142

Post by Kranar »

wat10000 wrote: post #141
Kranar wrote: post #139

Earlier quoted context omitted.

Yes the issue has to do with "never stops". One of the machines that never stops in one model will stop in another model. So in one model a Turing Machine called R never stops. In another model R stops after Q steps. But here's the issue... Q isn't an actual natural number, what it is is some mathematical object that satisfies all of the properties of a natural number in ZFC, but is not an actual natural number. What…

What do you mean, Q isn’t a natural number? If you had unlimited time and paper, you could sit down and run the machine by hand, counting each step, until it reaches the halting state. You will have counted Q steps. Or the machine never stops. There’s no such thing as a machine that stops after a number of steps defined by an infinitely large construct. There are machines that stop after some whole number of steps, a…

>What do you mean, Q isn’t a natural number?

Q isn't a natural number because natural numbers must be finite, but Q is infinitely large.

>If you had unlimited time and paper, you could sit down and run the machine by hand, counting each step, until it reaches the halting state. You will have counted Q steps.

What if the machine never stops? How many steps will you run before you decide that the machine never halts?

>There’s no such thing as a machine that stops after a number of steps defined by an infinitely large construct.

There's no such thing as an actual machine that stops after an infinite number of steps, but that's not the issue. The issue is that ZFC has different models with conflicting definitions of what infinite is. 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. But there is another model, called the standard model, and in this model there is no Q, all elements of this model are actually finite, and in this model the Turing machine never halts.

ZFC doesn't know which of these two models is the "real" model of natural numbers. From within ZFC both of these models satisfy all properties of natural numbers. It's only from outside of ZFC that one of these models is wrong, namely the model that contains Q as an element.

You can add more axioms to ZFC to get rid of the model that has Q as an element, but if the resulting theory containing your new axiom is consistent, then it necessarily follows that there is some other model that will contain some element Q* which is also infinitely large but from within the theory satisfies all of the new/stronger properties of being a natural number.

Re: BusyBeaver(6) Is Quite Large

#143

Post by ajkjk »

SAI_Peregrinus wrote: post #114
dtech wrote: post #24

Earlier quoted context omitted.

I am also not an expert, but this does not sound right to me. Godel's incompleteness theorem shows that there are certain things that cannot be proven. Being independent of ZFC means that something is such a case. So BB(643) being independent of ZFC means that we cannot prove or disprove that a certain number is BB(643). Aka we don't have the math to know for certain.

Independence from ZFC means we can't prove that any given number is BB(643) using ZFC . It doesn't mean we can't prove it at all, e.g. one could use a stronger set theory like NBG which can prove the consistency of ZFC to verify the value of BB(643). But there would be some n for which BB(n) is independent of that set theory, requiring a yet-stronger theory, and so on ad infinitum. ZF & ZFC are as important as they a…

sure, but it is still very hard to wrap one's head around how the value of a function can be independent of ZFC, and how it could not be for (e.g.) 642 but then be true for 643. That was the point of my post. It seems like you could just... run the function on every 643-state input and see what the value is, which would in some sense constitute a "proof" in ZFC? but maybe not, because you wouldn't even know if you had the answer? That's the part that is so intriguing about it.

Re: BusyBeaver(6) Is Quite Large

#144

Post by pinkmuffinere »

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

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 though? It's familiar/convenient to refer to tetration, pentation, etc as f() for convenience, but this is just notational -- not related to computability. When comparing BB(n) and tetration(n), pentation(n), etc(n), I don't think there is really anything that can be said 'easily' about which values are larger. BB(n) will be larger than anything that can be computed in n steps. But pentation(n) is not necessarily computable in n steps, it may take much more. We may find pentation(n) > BB(n) for all n greater than some threshold. I might be misunderstanding a logical step here though that connects them?

Re: BusyBeaver(6) Is Quite Large

#145

Post by wat10000 »

Kranar wrote: post #142
wat10000 wrote: post #141

Earlier quoted context omitted.

What do you mean, Q isn’t a natural number? If you had unlimited time and paper, you could sit down and run the machine by hand, counting each step, until it reaches the halting state. You will have counted Q steps. Or the machine never stops. There’s no such thing as a machine that stops after a number of steps defined by an infinitely large construct. There are machines that stop after some whole number of steps, a…

>What do you mean, Q isn’t a natural number? Q isn't a natural number because natural numbers must be finite, but Q is infinitely large. >If you had unlimited time and paper, you could sit down and run the machine by hand, counting each step, until it reaches the halting state. You will have counted Q steps. What if the machine never stops? How many steps will you run before you decide that the machine never halts? >…

> 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’s the largest number of steps they can run?” functions that would admit infinities, but those would not be Turing machines and the function would not be the Busy Beaver.

Re: BusyBeaver(6) Is Quite Large

#146

Post by Kranar »

wat10000 wrote: post #145
Kranar wrote: post #142

Earlier quoted context omitted.

>What do you mean, Q isn’t a natural number? Q isn't a natural number because natural numbers must be finite, but Q is infinitely large. >If you had unlimited time and paper, you could sit down and run the machine by hand, counting each step, until it reaches the halting state. You will have counted Q steps. What if the machine never stops? How many steps will you run before you decide that the machine never halts? >…

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

There is a lot of nuance you are skipping over that needs to be fully appreciated if you wish to understand this topic.

Re: BusyBeaver(6) Is Quite Large

#147

Post by btilly »

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

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.

Re: BusyBeaver(6) Is Quite Large

#148

Post by raincole »

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 a finite number, but I'd argue its magic also comes from infinites: the fact some Turing Machines run forever and never halt.

Re: BusyBeaver(6) Is Quite Large

#149

Post by vhcr »

Straw wrote: post #14
ChadNauseam wrote: post #11

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

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.

Nobody can give you that number, because it's way bigger than what can be represented in the universe.

Re: BusyBeaver(6) Is Quite Large

#150

Post by raincole »

wat10000 wrote: post #145
Kranar wrote: post #142

Earlier quoted context omitted.

>What do you mean, Q isn’t a natural number? Q isn't a natural number because natural numbers must be finite, but Q is infinitely large. >If you had unlimited time and paper, you could sit down and run the machine by hand, counting each step, until it reaches the halting state. You will have counted Q steps. What if the machine never stops? How many steps will you run before you decide that the machine never halts? >…

> 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 non-standard models, as arguably they shouldn't.

Q is not a number you can actually count, so it doesn't fit into our intuition of natural number. The point is not that Q exists in some physical sense in real life, like "3" in "3 apples" (it doesn't). The point is that ZF itself isn't strong enough to prevent you from defining random shit like Q as a natural number.

Post reply on HN