🚀 go-pugleaf

In article <3007@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:
 
|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.

No. I mean that practical computers are ACTUALLY finite: for both
practical AND theoretical purposes. I don't know any simpler way of
phrasing this. Practical computers are finite. They ARE. Really. In
actuality, real, actual, practical computers are actually really
finite in every way. They are limited, bounded and finite. Really.

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

Of course not. But any important theoretical result that DEPENDS on a
computer being infinite will have NO DIRECT APPLICATION to computers,
since actual computers are not, EVER, infinite.

|         And it is certainly the case that there are many applications
|where computers are not finite -- for practical purposes.

This is absurd. Of course there are applications in which a finite
practical machine of certain capacity and an infinite theoretical
machine would exhibit the same behaviour. But does this make the
finite machine less finite? No way, no how. Practical computers are,
for all purposes, always finite. That's just the way it is. Any
infinite computer is a mere approximation of a real computer and you
use techniques and results derived for infinite computers at your own
peril.

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

I don't understand what you're saying here. Are you telling me that
you actually KNOW that computers are FSMs but that you consider this
fact sufficiently non-obvious that you feel justified in persisting in
the pretence that they are infinite, despite the facts? Or are you
merely defending OTHER people's rights to err without fear of
correction?

In any event, the finitude of computers is obvious to about the same
extent as it is obvious that the population of ducks in Tahiti is
finite, I'd say. I mean, computers are finite, have discrete states,
and are machines. Therefore they're REALLY QUITE LIKELY (ahem) to be
FSMs.

|                                  Both models of computers have their
|uses.  

You bet. No question.

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

EXACTLY!!!! THANKYOU!!!! THIS IS THE POINT!!!! And any theorem that
depends on the fact that the machine will *NOT* hit a boundary does
not in fact apply to a real computer - and this is true any theorem
that requires that encodings exist for arbitrary objects, for example.
Remember: computers FINITE and (like humans) CANNOT DO ARITHMETIC.

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

Oh, yes. Correct me if I'm wrong, but it seems to me that they are not
adequate to THEORETICAL purposes like the standard
incompleteness/inconsistency proofs. You're confusing building up with
building down: these theorems, at least as I've seen them, apply to
"computers" that are AT LEAST infinite, not to ones that are AT MOST
infinite.  They may be useful approximations, but they aren't precise
results.

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

No; I'm suggesting that it's important to attribute cause accurately.
There's nothing INCORRECT about my sort, just because it can be handed
unbounded input. And there's nothing INFINITE about my computer just
because it can be approximated in some respects by an infinite
machine.
----------------------------------------------------------------------
stephen p spackman         Center for Information and Language Studies
systems analyst                                  University of Chicago
----------------------------------------------------------------------