🚀 go-pugleaf

victor yodaiken:
   I argue that there is a deterministic *algorithm* with time/space
   bounded by the number of states of M, and that this algorithm can
   decide the halting problem for M. If we want, we can compute this
   algorithm on a FSM with sufficient state space (probably quite a
   bit larger than M).

Well, yes.  If you're dealing with an arbitrary machine, with 16k ram
(8 bit bytes) you have to have a state space of over 10^(10^6) bits to
store halting information (halts/doesn't) for every possible state.
And this doubles every time you add a bit to the machine -- for a unix
system with a gigabyte of disk space, your state space over
10^(8.26x10^10) bits (a number greater than 1 followed by over 82
billion zeros (decimal)).

An the other hand, many algorithms can be easily shown to halt.  (Any
algorithm which is "primitive recursive" in the number-theoretic
sense, which includes just about every computer programming technique
except arbitrary loops and arbitrary recursion).

So I can see why a person might want to say that the halting problem
is solvable for a practical machine, but I wouldn't say that using
state space is a useful solution.  The solution I see is to limit
yourself to a class of problems which are primitive recursive.

From personal experience, I can say that you're still going to have to
resort to state machine style techniques when you deal with i/o or
secondary storage (secondary storage being defined as any storage not
managed transparently by your target language).

And I'm sure that any systems implementor can tell you horror stories
about lurking race conditions and other potential bogosities in the os...

Raul Rockwell