Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!asuvax!noao!arizona!gudeman
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions)
Message-ID: <2861@optima.cs.arizona.edu>
Date: 7 May 91 19:16:05 GMT
Sender: news@cs.arizona.edu
Lines: 38

In article  <30164@dime.cs.umass.edu> victor yodaiken writes:
]In article <1991May5.135342.13792@daffy.cs.wisc.edu> quale@khan.cs.wisc.edu (Douglas E. Quale) writes:
]>I should also point out that real computers are *not* finite state machines.
]
]Pointing it out is nice, but most computer engineers would be surprised by
]this claim...

Probably so, but not those who have put some thought into the matter.
Keep in mind that "state" in this sense refers to the entire body of
information accessible by the computer.  If a computer runs out of
storage, you can always go buy another tape.  Now there are two
possible ways to interpret the question of whether this gives the
computer unbounded storage: the practical and the theoretical.

Whether this gives the computer _practical_ unbounded store depends on
your opinion of what is practical.  If either you don't expect your
problems to run out of tape, or your problems are important enough
that you are willing to keep the computer supplied with all the tape
it needs, then the computer has a practically unbounded state space.
If you don't agree that the above is practical, then the computer has
a _practically_ bounded state space.

If you want to get theoretical, then you can _theoretically_ keep
buying tapes until the world's supply of tape runs out.  Then you can
manufacture more.  When you use up all the earth's supply of materials
for making tapes, you can build mining space ships.  The question of
whether a computer is a finite-state device or not boils down to the
question of whether the universe holds a finite amount of material for
making tape.  In this case whether you believe that a computer is a
finite-state device depends on whether you believe there is a finite
amount of matter in the universe.

The question of whether an electronic computer is an FSA or an
infinite-state device is not as trivial as most people seem to think.
--
					David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudeman