Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!ncar!noao!arizona!gudeman
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: Re: Halting Problem Solved! Film at 11! (Was Re:
Message-ID: <3354@optima.cs.arizona.edu>
Date: 19 May 91 20:54:45 GMT
Sender: news@cs.arizona.edu
Lines: 33

In article  <1991May19.024820.25262@sbcs.sunysb.edu> Joseph Allen writes:
[about the halting problem for real computers]
]Ack!  I apologize for wasting net bandwidth.  The following article answers
]this question:

I missed the original article, but no, it does not answer the
question, it only confuses it further.

]From: yodaiken@chelm.cs.umass.edu (victor yodaiken)
]>[A finite TM is translatable into a FSM.  A FSM has a state space S and a
]>mapping S -> S.  To see if it halts, pick a starting state, run through the
]>sequences.  If if goes on the halt state then it halts.  If it ever touches a
]>state which already occured, it doesn't.  Since there is only a finite number
]>of states, it takes a finite amount of time to decide (since at most it has
]>to go through all the states)]

What machine is going to do this?  If computers are FSM's then you
only have an FSM to do this, and I can always find a program too big
to analysis in this way.

By the way, how do you know that the TM is finite in the first place?

By the way, the term "Turing machine" refers to a specific
architecture, and does not describe all machines with infinite state
spaces.  (PDAs are infinite-state devices that can't even recognize
the recursive sets.)  A Turing machine has an infinite read-write tape
with a movable head and only four possible actions (as I recall).
There are very few applications where it is useful to model a computer
as a TM -- infinite or not.
--
					David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudeman