[wizeman]

Perhaps we should start admitting to ourselves that infinity is not really something that actually exists but instead it's just an imaginary concept that we created but that has no correspondence to anything that makes sense in our universe?

Or at least, some versions of infinity (I will leave which ones, exactly, to the experts).

Hence all the paradoxes that derive from it.

I mean, perhaps we can work with some version(s) of infinity, without creating a plethora of paradoxes.

The natural numbers, for example, might be something that is infinite and makes sense. However, perhaps talking about a single set that contains an infinite amount of natural numbers might not make sense (or perhaps it still might?). Or perhaps we just need a new language for talking about infinite things without re-using the language we use for describing (finite) sets, so that we don't try to reuse concepts from finite objects with infinite objects.

Or perhaps the only objects that exist (and can be meaningfully talked about) are the computable ones. And/or perhaps "computable function" is one that can use infinite amounts of time but only finite amounts of storage (rather than infinite amounts of storage).

Would it make sense to go back to classical finitism and re-evaluate some of the choices that were made along the way to where we are now?

I can't help but think about the many paradoxes that arise from the very (supposed) existence of infinity.

For example, everybody thinks the halting problem is undecidable. The halting problem is clearly not undecidable on finite-state machines (i.e. real computers), it's only undecidable if you use imaginary Turing machines (which supposedly can have literally infinite state) as a model. But of course, Turing machines cannot exist in our universe.

So it's rather ironic that people say the Halting problem is undecidable, when this is only true for (impossible to construct) imaginary machines but it's not true for the real machines that we actually have and that are possible to construct.

Or think about Hilbert's paradox of the Grand Hotel.

Or the Banach-Tarski paradox.

Or Galileo's paradox.

Or other such paradoxes that only exist if you believe that imaginary infinite objects could possibly exist.

Most people will tell you "well, it's just that our intuition doesn't work for infinite things", but in this specific instance, it's really hard for me to believe that it's our intuitions that are mistaken rather than that we actually made some conceptual mistakes along the way. To me, this argument sounds more like gaslighting rather than a real convincing argument.

I'm not saying our intuition is always correct, though. For example, the quantum properties of our universe are clearly not intuitive but it's hard to argue that our universe is not quantum, after all the scientific experiments that have clearly verified this to be true.

I don't think that invalidates my argument, though, because the convincing argument in that case is not "sorry, you must believe my theory that the universe is quantum" despite not existing any evidence that this was true, but rather, "sorry, but here's all this real evidence that our universe truly is quantum".

Am I crazy here?

[tsimionescu]

The thing is, infinity is extremely useful for taking things to the extreme. The halting problem is a very good example: as you rightly point out, the halting problem is trivially decidable for any finite Turing machine. However, the core of the argument remains true, we just need to complicate it significantly if we want to remain within the realm of finite machines: instead of saying "there is no TM that can decide if any arbitrary TM halts", we need to say something like "there is no finite TM that can decide if any TM smaller than itself halts in an amount of time less than that TM". They are equivalent concepts on some level, but the second one is significantly more complex, and harder to prove (assuming you don't appeal to the infinite version, from which it easily follows).

That is, even if you seek to do maths on finite but unbounded sets, you will find mostly the same properties that infinite sets have, but you'll have a much harder time working with the concepts. It's true that there are some problems that infinite sets have that unbounded finite sets don't, but those may well be a worthy price to pay.

And either way, regardless of intuition, the logic is valid. The Banach-Tarski "paradox" is perfectly logically valid, though unintuitive. So, even if you could say that it's useless and a result that we should avoid having in our theories, you can't say that it's wrong, since it doesn't violate any rule of logic.

[wizeman]

I can't really give a substantial response to your first argument, as I'm not certain about all the implications that you mention.

Your second argument, though, doesn't sound very convincing to me.

There are many possible consistent logical frameworks (perhaps an infinite amount of them? hah!) that are clearly not adequate for describing our universe. Or at least, they wouldn't make sense for us.

For a trivial (and perhaps stupid) example, consider an alternate universe where we decided to use a logical framework which can represent natural numbers, but where the digit "2" is represented as "9" and the digit "9" is represented as "7", etc. Let's say you have a 1-to-1 mapping from one digit to another, compared to our usual representation.

Or perhaps the mapping is a lot more complicated than that, and not just about digits, but about entire numbers.

Let's say we decided to do that, for no good reason. Or maybe there was a good reason at the time, but since then we have figured out that it doesn't make sense anymore.

Yes, you could do exactly the same math in this logical framework as we do in our usual ones, and no contradictions would arise.

However, would that really be a wise idea? Wouldn't that just lead to making unnecessary mistakes, sometimes even conceptual ones, when considering that we would be prone to confusing numbers in this system with the numbers that we use normally?

I think language is also important here, not just logical soundness. Especially if we want our intuitions to be helpful.

Just to bring this back to something less abstract again, I will just mention the following:

> However, the core of the argument remains true, we just need to complicate it significantly if we want to remain within the realm of finite machines: instead of saying "there is no TM that can decide if any arbitrary TM halts", we need to say something like "there is no finite TM that can decide if any TM smaller than itself halts in an amount of time less than that TM".

Well, I don't believe the core of the Halting problem to be true, and that's exactly the language problem that I'm talking about: confusing language leads us to making conceptual mistakes.

For example, time is not necessarily relevant here.

I could argue that what the Halting problem really demonstrates is that to analyze whether a finite-state machine (FSM) halts, you need to use an FSM that can have more state than the machine being analyzed (which is why it stops working if you believe you can have infinite state).

This FSM with more state would always be able to decide whether the other FSM halts in finite time, regardless of whether the other machine halts or whether it never does.

In fact, that's exactly what cycle-detection algorithms do, such as the tortoise and hare algorithm.

[tsimionescu]

The biggest problem with finite sets is that most operations don't work nicely in finite sets.

For example, if we take the naturals to be a finite set, and arbitrarily define some number G that is the largest number, then common operations stop being commutative/associative/distributive (e.g. x-y+z is no longer equal to x+z-y, if x>G-z; or x×(y-z) ≠ x×y - y×z). Lots of simple equations stop having solutions at all. The finite rationals also get similar problems. Your models also have all these arbitrary parameters - the largest positive integer, the largest negative integer, the smallest fraction, the largest allowed amount of non-repeating digits in a decimal representation of a fraction - things like these become independent parameters, and can be arbitrarily chosen to be different.

> Well, I don't believe the core of the Halting problem to be true, and that's exactly the language problem that I'm talking about: confusing language leads us to making conceptual mistakes.

But it is - you still can't, in practice, construct a useful program that depends on solving the "finite halting problem", since you will need too much memory/time for anything but the most trivial of examples. If you don't beleive this, than it should be doable for you to create a program that checks whether P=NP if we limit it to programs that can run on, say, an 8086 processor and only use 16 KB of RAM, right?

[wizeman]

> The biggest problem with finite sets is that most operations don't work nicely in finite sets.

I didn't necessarily mean to suggest that we should not work with infinite sets, only that perhaps we should not call them "sets" (so as to not confuse them with the finite ones), but rather something else, like "domains" or whatever.

So perhaps you could say that those commutative/associative operations are valid over the domain of natural numbers. But you couldn't say, "X" represents the cardinality of the set of natural numbers, because there's no such thing as the set of natural numbers.

Or, maybe the set of infinite natural numbers and infinite rationals makes sense but the set of real numbers doesn't (as they have different infinite properties?).

I don't know exactly what would be a better solution here, as I'm not a mathematician. I'm only trying to suggest that there might be a better solution than what we have right now, even if it would simply amount to just using different language and not necessarily changing the logical properties of the theory, so as to not arrive at confusing conclusions.

> But it is - you still can't, in practice, construct a useful program that depends on solving the "finite halting problem", since you will need too much memory/time for anything but the most trivial of examples.

But the decidability of the Halting problem is not actually a question of how long it takes for an algorithm to solve it, is it?

The decidability of a problem is a matter of whether it's actually possible at all to construct an algorithm that solves it, no matter how long the algorithm takes to solve it.

That is, whether this algorithm is computable and finishes in a finite amount of steps.

So I will say again that yes, the Halting problem is decidable, as long as you don't use an absurd model to answer the question (i.e. a model that does not represent anything that can possibly be built in our universe even in theory?).

The tortoise and hare algorithm solves the Halting problem for FSMs in a finite amount of time and it only needs twice the amount of storage as the underlying FSM that is being analyzed.

> If you don't beleive this, than it should be doable for you to create a program that checks whether P=NP if we limit it to programs that can run on, say, an 8086 processor and only use 16 KB of RAM, right?

The P=NP is a problem regarding the resources required during computation to solve a given problem, as far as I understand.

I am not entirely sure how exactly this relates to the decidability of the Halting problem when applied to finite-state machines, though.

I mean, it's clear that the currently-known algorithms that solve the Halting problem on FSMs, such as the tortoise and hare algorithm, in the worst case take a time to solve that is proportional to the cycle length of non-halting FSMs.

But also note that these currently-known cycle detection algorithms don't even try to analyze the FSM to decide whether it halts, except by testing their states for equality. This is due to the inherent definition of the cycle detection problem.

So they can definitely be made more efficient, perhaps for a large set of useful FSMs, even, as long as they would be allowed to inspect the FSM's state transition table. I'm not sure how efficient they could be, in theory.

I would be cautious in taking any computational complexity theory results at face value when we know that they use Turing machines as models, which can give you results that are the opposite of the results that apply to FSMs. But I'm not an expert and admittedly, I'm not entirely sure of what I'm talking about here.

Regardless, even if you can trust the computational complexity results, to me this is an entirely different question than the decidability of the Halting problem, which is a "yes/no" problem.

[housecarpenter]

I agree that infinity doesn't exist in the universe, but this isn't a problem for mathematics. Mathematics isn't about what exists in the universe, it's about what exists in the realm of concepts. Some concepts are more interesting than others, sure. Cantor's work made it clear that infinite sets are pretty interesting.

[wizeman]

The Flying Spaghetti Monster is also an interesting concept.

It can even be useful as a concept, in certain discussions/contexts.

Should we take the Flying Spaghetti Monster as a core axiom of our theories of physics?

Wouldn't this lead to us logically concluding for example, that there has to exist something else beyond the universe that we know about, even if this is not really true?

I mean, I know that I'm exaggerating and that the analogy is not necessarily very good.

But I'm also not entirely sure how different is the Flying Spaghetti Monster from the infinite objects that mathematicians talk about and that lead us to logically arrive at certain conclusions (that I would argue might not really be true, in terms of things we can understand).

I'm not saying that I'm right and that most mathematicians are wrong, necessarily. Perhaps it's just a linguistic issue, I don't know.