Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!bu.edu!m2c!risky.ecs.umass.edu!dime!yodaiken
From: yodaiken@chelm.cs.umass.edu (victor yodaiken)
Newsgroups: comp.lang.misc
Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions)
Message-ID: <30231@dime.cs.umass.edu>
Date: 8 May 91 15:14:48 GMT
References: <333124@socrates.umd.edu> <R73812w164w@mantis.co.uk> <30040@dime.cs.umass.edu> <1991May4.192440.5527@sctc.com> <30095@dime.cs.umass.edu> <truesdel.673495042@sun418>
Sender: news@dime.cs.umass.edu
Reply-To: yodaiken@chelm.cs.umass.edu (victor yodaiken)
Organization: University of Massachusetts, Amherst
Lines: 41

In article <truesdel.673495042@sun418> truesdel@nas.nasa.gov (David A. Truesdell) writes:
>It's getting fairly obvious that you don't really understand what the problem
>in the halting problem is.  The halting problem does not exist because a
>turing machine has an potentially infinite state space and infinite storage.
>It arises from the fact that, for certain cases, the question "will this
>program reach the halting state" is inherently undecidable, even given
>infinite time.  The physical limits of "actual computers" have no bearing on
>the problem.  Your "obvious, although impractical algorithm" does not exist.
>--

I'm a little bothered by the tone of this post. These are sometimes tricky
questions, and the news group includes people of diverse backgrounds, so
a little patience with errors would be appreciated.  As far as I understand
it, the Turing proof relies quite a good deal on the infinite state
space of turing machines. Note that if we limit a turing machine to
a fixed number of squares on the tape, we can transform it into an
equivalent finite state machine. Say that we fix tape length at k, and
we have an alphabet of n symbols, including the blank. Then, there
are n^k possible configurations on the tape. The tape head can be
in positions 1,2,... k and there is a finite state control for the
turing machine with, say, r states. We can then build a FSA that
emulates the original turing machine by letting its state set be
the set of triples (s,p,t) where "s" is one of the states of the turing
machine, "p" is the current position of the turing machine read/write
head, and "t" is the tape in current configuarion --- t is a sequence
of length k over the alphabet. The alphabet of the FSA would consist
of  a single symbol -- "go-to-next-step". If the FSA was in state
(s,p,(x_1,....,x_k)) then we ask what the Turing machine would have done
in state s with the head over square p -- where the stored value will
be x_p. If the turing machine moves left we get a new state
(s',p-1,(x_1,...,x_k) etc. If there is a path from the state
(start,1,blank) to some state (halt,p,t) then the Turing machine halts
on the blank tape input. Otherwise it does not.

Now, this is an exponential algorithm (exponential in the size of the
tape), but that does not necessarily make it impractical as
your local trucking  or phone company will tell you (the simplex
algorithm for linear programming is exponential, but is in very
wide use).

Any corrections in this exposition will be accepted gratefully.