Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!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: The Halting Problem is _not_ solvable on real com
Message-ID: <30581@dime.cs.umass.edu>
Date: 15 May 91 18:16:09 GMT
References: <3069@optima.cs.arizona.edu> <30505@dime.cs.umass.edu> <1991May15.145359.20719@daffy.cs.wisc.edu>
Sender: news@dime.cs.umass.edu
Organization: University of Massachusetts, Amherst
Lines: 46

In article <1991May15.145359.20719@daffy.cs.wisc.edu> quale@saavik.cs.wisc.edu (Douglas E. Quale) writes:
>2) The FSM view ties us to a particular machine.  I don't think this is a
>   very useful view of computation. :-)  Generally we want our  programs
>   to behave similarly on different machines.  I want to say "This program
>   will terminate with result foo or with an error condition if not enough
>   memory is available."  I don't want to say "This program will terminate
>   with result foo if run on a small enough machine but I don't know what
>   it will do otherwise."

I don't understand your reasoning here. Knowing that the state machine
has a bounded number of states does not commit us to exactly what that
number is.

>* What useful programs terminate as FSMs and fail to terminate as TMs?

Here are some programs that differ in interesting ways on FSMs and TMs

while(true){ print(i), i = i+1 }
      
          loops or dies on a FSM, runs without repeating state on a TM

input i
while(i is not prime) i = i+1; print (i)
>
         finds the next prime greater than i on a TM, but has more
         complex behavior on a FSM


n = m*m
         does the multiplication on a TM, may compute  m*m MOD k
         on a FSM


i = 1
while(i != 0) i = i+ 1

          terminates with most definitions of FSM arithmetic,
          does not terminate on a TM.



Correct programs on real machines must respect that inherent limitations of
digital computing devices.  While it is sometimes convenient to act as 
if we were writing programs within an unbounded domain, e.g. as if
"i" could indeed range over the integers, this is only a convenience
when it does not lead to errors.