Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!sdd.hp.com!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: <3007@optima.cs.arizona.edu>
Date: 9 May 91 19:15:58 GMT
Sender: news@cs.arizona.edu
Lines: 39

In article  <STEPHEN.91May9022258@estragon.uchicago.edu> Stephen P Spackman writes:
]
]... PRACTICAL computers are FSMs and not fully
]general turing machines because PRACTICAL computers are finite. The
]fact that PRACTICAL computers are finite is an important THEORETICAL
]property of PRACTICAL computers and may need to be addressed before
]certain ideas are dismissed...

I'm assuming that by "practical computers are finite" you mean that
computers are finite for practical purposes -- if you meant something
else, please correct me.  OK, suppose that there are important
theoretical results based on the assumption that computers are finite.
That does not preclude the possibility that there are important
theoretical results based on the assumption that computers are not
finite.  And it is certainly the case that there are many applications
where computers are not finite -- for practical purposes.

I have not claimed that computers are unbounded-state machines, I've
only said that it isn't the case that computers are obviously FSMs as
some on this group seem to think.  Both models of computers have their
uses.  It is not the case that all results based on the assumption
that computers are USMs are impractical, because as long as your
problems do not hit the boundaries, the boundaries may as well not
exits.  Most algorithm analyses and programming language semantics
assume that the machines are USM's and the results from such
assumptions are valid for most practical purposes.

]....I feel a bit like you're telling me that it's impossible to code a
]correct sort, because you never know when your input is going to be
]an infinite stream and the function just might not terminate....

I don't understand what you mean by that.  If your input is another
process of unknown origin, then there _are_ certain correctness
criteria that you cannot satisfy with your own sort.  Are you
suggesting that you wouldn't want to be told that?
--
					David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudeman