🚀 go-pugleaf

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