BusyBeaver(6) Is Quite Large

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.

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.

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

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 is “never stop”? That also seems pretty well defined to me. For BB(748) to vary based on your model, if the machines that run for fewer steps don’t change, then that means one of the machines that never stops in one model will stop in another. Or the BB winner for our model will never stop in another model.

How can changing your model make it so a specific Turing machine goes from stopping after 10,000 steps to never stopping, or from never stopping to stopping after 11,000 steps?

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 it actually is is some infinitely large object that satisfies all of the Peano axioms of what a natural number is as well as satisfies the following set of rules:

   Q > 0
   Q > 1
   Q > 2
   Q > 3
   ...

Q is basically some infinitely large construct that from within the model appears to be finite, but from outside of the model is not finite.

So within this model, the Turing machine R halts after Q steps, and since from within the model Q is finite then from within this model BB(748) is at least equal to Q.

If BB(748) is actually 10,000, then we can add this as an axiom to ZFC to get a new formal theory ZFC + "BB(748) = 10000".

In this new theory the previous structure that contained Q as an element will not satisfy the definition of a natural number, so we don't have to worry about Q anymore... however, there will exist some number T > 748 where BB(T) is independent of our new theory. For BB(T), there will exist some other model that has its own Q* which satisfies all of our axioms including the axiom that BB(748) = 10000, but also that

    Q* > 0
    Q* > 1
    Q* > 2
    Q* > 3
    ...

And rinse and repeat...

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.

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

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

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.

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

> ultrafinitism

I'm not sure what flavor of ultrafinitism you're referring here. If it's the "very big numbers, like TREE(3), are not natural numbers as they are far bigger than the number of atoms in this universe..." kind, then it has nothing to do with what this is about.

> physical representation

> your own eyes

Non standard models of ZFC have nothing to do with our physical world. That's why no physicist or engineer cares about them (or cares about axiom systems at all). So we need to be very careful when connecting the idea of physical, running "stuff" to the discussion of ZFC.

Anyway, back to

> you can run them both alongside in this universe and see which one finishes first

There are two Turing Machines, Foo and Bar. We build and run them in our physical universe. Foo halts at the standard BB(748) steps. Bar just keeps running and running. That's what we will see with our own eyes.

The issue is that when we try to reason out whether Bar will ultimately halts, ZFC doesn't prevent us from defining a non-standard model where Bar halts after a non-standard number of steps. Note that the physical Bar will not halt in our universe. The "non-standard number of steps" is as nonsense as it sounds. It's just that ZFC doesn't prevent us from defining such a nonsense. The point of ZFC is it's compatible with almost all the useful, sane math. It's not necessarily incompatible with bullshit and insane math.

That is it. The fact that Bar is still keeping running in our universe is completely irrelevant.

> 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 independent of ZFC doesn’t mean there are different models that have different values of BB(748). It means that ZFC is insufficient to determine the value of BB(748). That value is still some finite integer, you just can’t prove which one it is. Equivalently, there is some 748-state Turing machine which never halts but ZFC cannot prove never halts.

And no, you can’t change your model such that this Turing machine halts in some non-standard number of steps. Or rather, you can, but that doesn’t actually change anything. The machine still doesn’t halt for the purposes of defining BB(748).

> 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]. If you don't like it, I can't convince you otherwise.

> that doesn’t actually change anything

Changing the model will not change how any machine works in our physical, mechanical universe. However, it does change the value of BB(748).

I understand your line of thinking: There is only one mechanical universe, which is the one where we exist. We can build Turing machines in this universe. BB(n) depends on Turning machines. Since there is only one single universe, there is only one single value of BB(n).

It's a perfectly fine mental model for most cases. This was exactly how I thought when the first time I heard about BB(n). But it's not the kind of math than Scott Aaronson et al. are doing.

Bar keeps running in our mechanical universe. But it can also halt in some non-standard number of steps. This weird, absurd-sounding proposition works because non-standard numbers simply don't map to anything in mechanical universe. They're purely abstract objects living in ZFC+~Con(ZFC).

[0]: Given f(n)=X is independent of ZFC. Which means f(n)=X and ~(f(n)=X) are both consistent relative to ZFC. Therefore, if there is any model of ZFC, there is a model M1 that entails ZFC+(f(n)=X), and a model M2 that entails ZFC+~(f(n)=X). The value of f(n) cannot be the same in M1 and M2.

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?

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