Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!cs.utexas.edu!asuvax!noao!arizona!kwalker
From: kwalker@cs.arizona.edu (Kenneth Walker)
Newsgroups: comp.lang.misc
Subject: Re: Will this *thread* ever halt?
Message-ID: <3522@optima.cs.arizona.edu>
Date: 23 May 91 16:10:46 GMT
References: <3430@optima.cs.arizona.edu> <30863@dime.cs.umass.edu>
Sender: news@cs.arizona.edu
Lines: 17

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