Models of Computation
Turing machines are usually regarded as the de facto model of a computer. John D. Cook even said "For example, a Turing machine is a computer reduced to theory." There is a serious objection to this view, for it leaves no place for innovations like the transistor. If a Turing machine producing symbols on an infinite tape is a totally adequate model of a computer, why bother transistors? Yet transistors are the reason why modern CPUs are so fast and small, suitable for personal computing devices. A more balanced point of view would be that Turing machines capture the logic of computation, but are not a comprehensive model of a modern computer. Turing machines constructed as they are operate very slowly. The place of transistors is to preserve the essential logic of Turing machines while greatly speed up computation. Consequently, computational steps, or logical depth, should not be regarded as a measure of real computational time, but only as a measure of logical complexity. O...