Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!samsung!crackers!m2c!risky.ecs.umass.edu!dime!chelm.cs.umass.edu!yodaiken
From: yodaiken@chelm.cs.umass.edu (victor yodaiken)
Newsgroups: comp.lang.misc
Subject: Re: Will this *thread* ever halt?
Message-ID: <30863@dime.cs.umass.edu>
Date: 22 May 91 12:08:38 GMT
References: <3430@optima.cs.arizona.edu>
Sender: news@dime.cs.umass.edu
Organization: University of Massachusetts, Amherst
Lines: 26

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.