Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!dali.cs.montana.edu!uakari.primate.wisc.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!samsung!transfer!lectroid!jjmhome!smds!sw
From: sw@smds.UUCP (Stephen E. Witham)
Newsgroups: comp.lang.misc
Subject: Re: The Halting Problem is _not_ solvable on real com
Summary: Arbitrarily large FSM
Message-ID: <471@smds.UUCP>
Date: 17 May 91 14:09:53 GMT
References: <3125@cirrusl.UUCP> <3069@optima.cs.arizona.edu> <1991May15.145359.20719@daffy.cs.wisc.edu>
Organization: SMDS Inc., Concord, MA
Lines: 25

In article <1991May15.145359.20719@daffy.cs.wisc.edu>, quale@saavik.cs.wisc.edu (Douglas E. Quale) writes:
> 2) The FSM [finite state machine] view ties us to a particular machine.  
>    I don't think this is a very useful view of computation. :-)  

When people say (and they really do!), "This algorithm needs space O(n)," 
it seems to me they're working with a model of "arbitrarily large FSMs."
You can map FSMs to each other, and arrange them by memory capacity.
That's a class to which all real computers belong.  You can prove
things like...
  o  This program will finish on an FSM of size X. (Maximum size needed).
  o  This program may crash on an FSM of size < X. (Minimum size needed).
  o  This program may run forever on any FSM.  (No limit to size needed).

(where you may relate X to some function of the input).  Oh, also, you can
do the same with time limits.

So, the version of the halting problem you can definitely solve (given enough 
time on a big enough computer) is, given some ridiculously large amounts of 
memory and time, will this program halt?  Sounds useful to me.

But solving the halting problem for programs already written is silly.
I forget--how did we all get on the subject?

--Steve Witham, sw@smds.UUCP
Not-the-fault-of: SMDS, Inc., Concord, MA