🚀 go-pugleaf

In article <3430@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:
>No, it's just that you seem to be trying to be trying to have it both
>ways: "Since a computer has a finite number of states, it is possible
>in principle to solve the halting problem for it, since you can always
>just traverse all possible states."  The first part of the sentence
>implies that you are modeling a computer as an FSM.  The second part
>of the sentence implies that you are modeling a computer as a
>non-finite state machine, since you are assuming that you can traverse
>all possible states.
>

You are defining the problem incorrectly. I do not argue that for any
FSM M, we can use M to decide its own halting problem. Instead, 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).

You are arguing that there are programs which can be executed on
any computer which use enough of the state space of the computer as to
leave no room for a program that would emulate them. But, of course. 
However these programs *can* be emulated on a bigger, but still finite,
physical or virtual machine.  Note that there is no analog for this
procedure with TMs. A TM does not get any more powerful
when we add additional tapes or heads, but FSMs limited to n states
are strictly less powerful than FSMs limited to n+1 states.  

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

In article <30863@dime.cs.umass.edu>, yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:
> 
> You are defining the problem incorrectly. I do not argue that for any
> FSM M, we can use M to decide its own halting problem. Instead, 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).

The original problem, as I recall, was whether a compiler can solve
the halting problem for real programs. I insist on being able to
run your compiler on the same machine I run my program on. (After
all, this is a real-world question and not some "silly" theoretical
exercise, right? :-)

  Ken Walker / Computer Science Dept / Univ of Arizona / Tucson, AZ 85721
  +1 602 621-4252  kwalker@cs.arizona.edu {uunet|allegra|noao}!arizona!kwalker