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