Comment by Kranar
8 months ago
>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?
26 replies →
But Q is a number you can actually count, for a definition of “actually” that includes unimaginably large space and time. That finiteness comes from the basic mechanics of the Turing machine, which don’t depend on your mathematical axioms.
Sure, you can come up with a set of axioms where the natural numbers include infinities. You may be able to use it to prove interesting things. But all that does here it make it so that the set of numbers describing how many steps a Turing machine runs before it stops is no longer the “natural numbers.”
There is a lot of nuance you are skipping over that needs to be fully appreciated if you wish to understand this topic.
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 depend on your mathematics, only on your Turing machine.
2 replies →