Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!zaphod.mps.ohio-state.edu!wuarchive!udel!sbcs!eeserv1.ic.sunysb.edu!jallen
From: jallen@eeserv1.ic.sunysb.edu (Joseph Allen)
Newsgroups: comp.lang.misc
Subject: Re: Halting Problem Solved! Film at 11! (Was Re:
Message-ID: <1991May25.135757.6912@sbcs.sunysb.edu>
Date: 25 May 91 13:57:57 GMT
References: <3354@optima.cs.arizona.edu>
Sender: usenet@sbcs.sunysb.edu (Usenet poster)
Organization: State University of New York at Stony Brook
Lines: 55

In article <3354@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:
>In article  <1991May19.024820.25262@sbcs.sunysb.edu> Joseph Allen writes:
>]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.

I agree, none (plus it would much much too slow- the number of states in real
computers is huge).  The 64K question is can it be done symbolically on the
language source code.  I believe the answer is sometimes.  If you don't have
malloc and you don't have other forms of bignums then it might even be
practicle.  Maybe.  It would be usefull because you could tell at compile time
if you're going to overflow or go past array bounds or run out of stack space.
At any rate, the halting problem proof should not be justification to not at
least research this.  I originally thought that it was because I misunderstood
the halting problem and its scope.

If you're programming in an idealized lisp-like environment, then I guess the
problem starts to approach the actuall halting problem.

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

Well it's not as defined, but real computers are.  And more importantly, many
times the "functions" or whater the modularity structure in the language in
question is is.

This is not to say that the halting problem is not usefull- it is, but for
fundamental questions of discrete algorithms in idealized environments.  

>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.

TMs are used because they can represent any machine with a finite or infinite
(but not continuum) state space (including PDAs).  It's not pretty to
represent real computers on TMs, but it can be done, and that's the point.  

Similarly, a FSM as a classification means much more than an EPROM and a
latch.
-- 
/*  jallen@ic.sunysb.edu  */     /* Amazing */     /* Joe Allen 129.49.12.74 */
int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0)
+r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2
]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}