It is said that "The Turing machine is not intended as practical computing technology, but rather as a hypothetical device representing a computing machine. Turing machines help computer scientists understand the limits of mechanical computation." [Wikipedia]

So on which model current machines are built?


The one closest to typical CPUs is probably the register machine or random access machine (RAM). A RAM has

  • an infinite number of registers, each of which stores an arbitrarily large number,
  • a set of operations on these registers (typically $\{+ 1, = 0\}$),
  • a programming language including these operations as well as control structures for looping/branching (until/if some register holds $0$) and
  • a program counter pointing to the next operation (in some program).

Real CPUs are quite similar, with some changes:

  • There are only finitely many registers (which may exist only virtually), and each stores only numbers of bounded size.
  • There are more operations.

Apart from that, it's very close indeed. It is common to extend the RAM model to account for memory hierarchy, which makes results a lot more applicable.

  • $\begingroup$ I think that the Random-access stored-program (RASP) machine model is even closer to an everyday computer $\endgroup$ – Vor Nov 7 '12 at 13:19
  • $\begingroup$ What Raphael said is not quite true: you are not allowed to store arbitrarily large numbers. In fact, in the RAM-model every register/memory cell can store $O(\log n)$ bits of information. Still this means that, the larger your input, the larger your machine word-size. This is of course not true for computers. $\endgroup$ – A.Schulz Nov 7 '12 at 13:33
  • $\begingroup$ @A.Schulz: if you are going to criticize the RAM model in that way, you should also criticize Turing machines for having infinite tapes. These models are fine as they are because they idealize reality (very large but limited resources) in a mathematically useful way (approximate "very large" with "infinite" in order to study certain aspects of computation which are not about limited resources). $\endgroup$ – Andrej Bauer Nov 7 '12 at 15:09
  • 1
    $\begingroup$ @AndrejBauer: I never criticized the RAM model. Scaling is an important concept for all reasonable powerful models of computation. Otherwise we would be stuck with regular languages. However, technically speaking, a computer has limited resources and is therefore a finite state machine/finite automaton. $\endgroup$ – A.Schulz Nov 7 '12 at 16:22
  • $\begingroup$ @A.Schulz That may depend on who is talking, and about what they are talking. In computability theory, such a restriction is more of a hindrance than of relevance. In complexity theory, it sure is relevant; the specific restriction then depends on the cost model one wishes to work with. $\endgroup$ – Raphael Nov 8 '12 at 17:02

Von Neumann machine, and if you prefer something more mathematical, look instead at RAM machine.

  • 3
    $\begingroup$ That is a computer architecture, not a mathematical model. $\endgroup$ – Massimo Cafaro Nov 7 '12 at 6:50
  • $\begingroup$ "I need to add another sentence." -- that's a dead give-away that this should have been a comment, not an answer. Do you want to extend your post, or should I convert it? $\endgroup$ – Raphael Nov 7 '12 at 10:35
  • 3
    $\begingroup$ Raphael is not right. Comments can be long, the answer can be as simple as 'Yes'. If it is a comment or answer is not a matter of length but a matter of content. $\endgroup$ – Val Nov 7 '12 at 13:29
  • 2
    $\begingroup$ The answer is fine as it stands because it completely answers the question. Von Neumann's machines (let us not quibble over "machine" vs. "architecture") were designed specifically for the purpose of building actual computers. And since Wikipedia does a good job of describing them, I do not see what else I could say. It's not my fault the question has an easy answer. $\endgroup$ – Andrej Bauer Nov 7 '12 at 15:02
  • $\begingroup$ @MassimoCafaro: what precisely is the difference? Von Neumann's designs are every bit as mathematical as Turing machines. Do not confuse a particular presentation with the mathematical idea. For example, Turing machines can be described in terms of "tapes", "heads" and "control states", or in terms of "a set of quadruples" and a "transition function". Even though one of them sounds more "mathematical", they are both mathematics. $\endgroup$ – Andrej Bauer Nov 7 '12 at 15:04

Your Answer

