How many of you like HP41C calculators?

From: William R. Buckley <wrb_at_wrbuckley.com>
Date: Thu Nov 20 02:32:27 2003

I asked for the professor, and I got it. Well,
>
> 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.

******thank you******

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

Mine, too!

> 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

William R. Buckley
Received on Thu Nov 20 2003 - 02:32:27 GMT