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