My PC at home is a 486/25. I bought it four years ago and it's trembling on the brink of obsolescence. I want a better machine. If I had the money, I'd get one. I want a 486/66 like my roommate has! Actually, what I really want is a Pentium. No, I want a Pentium Pro... with 128 megs of RAM, a sextal-speed CD-ROM, and a ten gigabyte hard disk. Better yet, I want a machine which hasn't even been built yet, one that will be the top-of-the-line five years from now. I want more speed, more power, more space. We all do -- we're computer science students. But why stop there? Though we build more and more powerful machines, they still do basically the same thing and execute similar instructions. Some do so faster, better, more efficiently; yes, certainly. But even so, a good computer today is not different in any fundamental way from the 8086 my parents bought fifteen years ago. Given enough time (maybe 1,000 years) and enough computers working side by side (millions), even those old clunkers could have generated the computations necessary to animate Pixar's Toy Story. It would be difficult in terms of size and speed, but not impossible. Computers back then had limitations, and they still do.
What would the perfect computer be like? Our best model of a computer so far has been the Turing machine, but that has basic limitations. It can't read a program and decide whether it will terminate or not. It can't write certain programs for itself without running into the possibility of contradiction. So why don't we just make a better, more powerful model of a computer, one that can do everything? Simple: because there is no more powerful model. Such a model would be a logical impossibility, a living contradiction. Kurt Gödel was the first person to realize this basic truth, when he stated in his famous theorem that no mathematical system can be both complete and consistent.
In chapter 3 of the text for this class, we learned of the Church-Turing thesis, which states says that a formalized algorithm is symbolically equivalent to an operating Turing machine, and that the two are equal in power. This thesis shows why a Turing machine is so widely used. Algorithms are how we conceptualize all the problems we wish computers to solve, and we would like our model of a computer to be as versatile as possible in handling the programs we give it; thanks to the Church-Turing thesis, we know that any problem for which we can describe a solution can have computer program associated with it. But even a generalized algorithm is itself an imperfect medium for writing programs, because algorithms which refer to themselves sometimes lead to contradictions and then they don't work.
Perhaps the most compelling argument that no better design for a computer than the Turing machine will ever exist is that human beings themselves are subject to the same limitations as that of a Turing machine. In the book Gödel, Escher, Bach, Douglas Hofstadter offers a vivid example of the limitations of the "computational system" of a human. On page 476 he describes a sentence which is true, and yet I myself cannot assert without becoming inconsistent. That sentence is: "Russell Glasser cannot consistently assert this sentence." Clearly this sentence is true as long as I never assert it, but if I ever state that it's true, I will be admitting that I am inconsistent! If this is the case, then I myself am not a perfectly robust system, since I cannot consistently assert all things that are true. Actually, I just did assert that it's true, so I guess I'm not consistent, as my family and friends could have told you in the first place. Luckily, the "circuitry" of my mind won't suffer if I say something inconsistent or false. But computers are designed by humans to serve certain purposes, and those purposes rely on the fact that the computer always produces correct output. A computer would be worthless if it sometimes accidentally made false or inconsistent statements. The problem is not one of insufficient computing power, but of our specifications for what a computer should do. Hofstadter offers up another good example of why computers can't be perfect on page 478: "A computer program can modify itself but it cannot violate its own instructions -- it can at best change some parts of itself by obeying its own instructions."
How powerful are modern computers, anyway? Turing machines have infinite read/write space, but computers clearly are not infinite in scope, so in what sense is a modern computer really a Turing machine? Surely it's not literally a Turing machine. We can think of it as a very very large finite automaton. The "infinite read-only-memory" which computers are supposed to have is similar in spirit to the potentially infinite input to a finite automaton; it is simply a series of immutable symbols that the computer reads as data. Since the Random Access Memory is finite, there is no infinite writable tape, hence no Turing machine. Does this mean that computers are nothing more than really big Finite Automata? In some sense, yes. But the amount of RAM available is extremely large. Even my crummy old computer has 8 megabytes of RAM, as well as 500 megabytes of disk space which the machine can write to, and is sometimes "swapped" as pseudo-RAM. That I means have roughly 500 megabytes of memory, or "tape," to do what I please with. 500 megabytes. That's 500,000,000 bytes. That's 4 BILLION bits of memory. If that's a finite automaton, well, it's an awfully big one. Since each bit can be either 1 or 0, there can be 24,000,000,000 actual states in there. That may not be infinite, but it's close enough for me! Here's a little exercise for your mind. A finite automaton is considered to be limited because it can't do certain elementary problems, such as print the string "(an)(bn)" for all values of n. [Note for non-theory people: the preceding notation means "print the character 'a' n times, then print 'b' n times (the same number as a)".] But my computer can certainly print out (an)(bn) if I want it to, because I have room to write the character 'a' 250,000,000 times and 'b' 250,000,000 times without even using a counter for the states! Now, let us (rather generously) imagine that a computer writes at the rate of 200 characters per second. By the time it prints out 500,000,000 letters, a month will have passed. Who wants to wait that long for a computer program to finish? You see, even if a computer were a real Turing machine, it would still have to work within the bounds of human patience. The real boundary on our machine must be in human terms, not in computer terms, and the power of the "tape" on a modern computer is so very vast that it might as well be infinite, so we may as well call it a Turing machine.
How could a real Turing machine exist? The universe is finite, after all. The number of atoms and the possible configuration of those atoms is uncountably large, of course, but still finite. So in some sense, a Turing machine cannot possibly exist; but we can have really huge input/output tape, and even though it must be finite, there comes a point when we can say "That's big enough for me! It doesn't have to be infinite because I'd never sort through so much output even if I could sit here until the universe dies, which of course I can't." Modern computers really are as robust as they can be, so what else can we expect in the future, if not a better model? The answer is summed up weekly by Tim Allen: "More power, more power, more power! Grunt grunt grunt."