How many of you like HP41C calculators?

From: Brian L. Stuart <blstuart_at_bellsouth.net>
Date: Wed Nov 19 23:34:09 2003

While there have been other follow-ups to this thread, I'm picking
this one as the point I jump in. This is a bit long and for those
of you who don't see a point in this sort of "angels on the head of
a pin" discussion feel free to delete. If you want to criticize
me for engaging in such a discussion because there's no ROI there,
then you can just kiss my big, white... :-) Sorry, too much bean
counter frustration at work lately. Another way of looking at this
message is that it was suggested that a professor be asked. Well,
be careful what you ask for, you might get it:-)

>> There are several architectures for computers, with all being the
>> equal of the Turing machine.
>
> That's interesting, because not one of the devices I have called
> computers, used as computers, or heard/seen called computers, is even
> theoretically equivalent to a Turing machine. In particular, they all
> have finite storage.

It is indeed correct that in an absolute sense physical computers
can be modeled by finite automata and don't need a Turing machine
to model them. And it's correct that the reason for this is that
the physical computer is finite and a Turing machine's tape is
unbounded. (Almost no authors highlight the distinction between
unbounded and infinite. But keep in mind that for any recursive
function, the Turing machine must finish in a finite amount of
time and therefore can only use a finite amount of tape. However,
there is no a priori bound on that finite size.)

>> Frankly, the Turing machine is the definition of a computer,
>
> I don't know where you got _that_, but it certainly doesn't match my
> understanding, usage, or experience of others' ditto. As I remarked
> above, there aren't any computers by that definition.

Now here I do agree with the desire to define a computer in terms
of machines that can compute functions that are computable in a
Church-Turing sense. Of course in doing so we have to keep in
mind that we are only looking at bounded approximations. In other
words, there are some recursive functions that we can never
completely implement with a finite physical computer.

So if physical realizations of the computing ideal will always
come up short of the models of the Turning machine or the lambda
calculus, then why do we ever study these models and why do we
make distinctions between recursive and recursivly enumerable?
As I see it, the answer lies in the enormous size of the finite
automaton that a physical computer realizes. Take even a small
(by today's standards) machine with 1MB of memory. Ignoring
secondary storage, the machine has 2^8388608 states. Since there
are only about 2^34 nano-seconds per year, it would take 2^8388574
years to go through all the states at a rate of one new state
per nano-second. Now, of course, one doesn't have to visit all
of the states of a finite automaton to recognize an input string.
But this observation suggests that regular languages make a poor
model to describe the physical computers we build. Add to that
the fact that the way that deterministic models (like RAM or
deterministic TMs) handle those regular languages most naturally
reognized by non-deterministic FAs is by exploding the number
of states in a similar way. So the bottom line is that the
regular expression model does a poor job of describing the
types of interesting problems we use computers for.

Now if we flip the perspective and ask about what interesting
things can be done on a Turing machine, we find a similar issue.
In order for the answer to do us any good, we must get it in
our lifetime which implies that there is an upper bound on
the size of the tape we will use in an interesting computation.
Of course, this gets us right back to the same issues we have
with the physical computers. Once I set an a priori bound,
the set of languages recognizable is a subset of the regular
languages.

But once I say that, then all of the structure in the language
hierarchy collapses. However, we view the question of Church-
Turing computability and the questions of NP-Completeness as
something more than just mental self-gratification. Therefore
(you knew I had to get there eventually), the Turing machine
is a powerful model to describe physical computers just as
it's a powerful model to assess the limits of computation in
the abstract. Furthermore, it's a more useful model than
those that are actually theoretically equivalent.

Those who would argue that I've shifted the discussion away
from the semi-original issue of defining a computer have a
good point. Just because the Turing machine is one of the
best ways to abstractly model the physical computer doesn't
necessarily mean that it should define said computer. So
how would I attempt to couch the definition of a physical
computer in terms of a Turing machine? I'd say that if you
can implement a simulation of a universal Turing machine
so that the range of it's computations is limited only by
the amount of addressable memory, then you have a real
computer. I am aware that Cohen defines the term computer
in a more abstract sense and I understand why he does so.
(By the way, his is one of my favorite books on the subject.)
And if I'm wearing my theoretician's hat, then I'm likely
to use the terminology the same way. But when I'm wearing
my engineer's hat and am appreciating the design of classic
hardware and when I'm wearing my historian's hat and am
trying to classify early machines, then I'm more likely
to use a definition like I've suggested above.

If you've stayed with me this long, you have my condolances.
However, there's one more interesting point that comes out
here. This sub-thread was sparked by the question of whether
the potential of self-modifying code was necessary in order
to be a computer. Notice that with the definition above,
any computer can implement a universal Turing machine and
unless you engage in some unnatural limitations, such a
machine can modify it's own programming. (Remember that
a universal Turing machine interprets instructions read
from the tape.) A more prosaic way of looking at this same
point is that I don't need a von Neumann architecture to
implement an interpreter which interprets self-modifying
code. And if computing theory teaches us anything, adding
or removing levels of abstraction doesn't affect the basic
power of the model.

My apologies for being so long-winded.

Brian L. Stuart
Received on Wed Nov 19 2003 - 23:34:09 GMT