How many of you like HP41C calculators?

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