| The other controversy that you'll see in a computer science context is that the Turing Machine specified by Turing has an infinite tape (or at least an unbounded tape; there are no conditions under which it can produce an out-of-memory error). That means that there is no largest number (or other mathematical object) that it can represent, which is different from a physically-realized general-purpose programmable computer. On a physically-realized computer, once you fix some representation for numbers, there will always be a largest one that the computer can actually represent in its memory. People have even maintained that, from the pure theory of computation point of view, the desktop computer (without threads and interrupts) is most like a finite-state machine rather than a Turing machine. It's just that each different possible memory (plus CPU register) state is a "state", so a computer with 8 GB of RAM will have something above 2^68719476736 states. However, it can easily simulate a Turing machine given the assumption that the tape doesn't run out for a particular computation, including for computations that in human terms are very large and complex ones. :-) Edit: One could also include the computer's hard drive as addressable memory, in which case it has even more states when viewed as a finite state machine. A basic problem from an automata theory point of view is that eventually there are some inputs which need to fit entirely in memory in order to be processed correctly, and yet simply can't fit in memory. At that point, the computer will necessarily have to stop being as powerful as the idealized Turing machine in terms of distinguishing those inputs! |