# Mathematical model on which current computers are built

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?

-

## migrated from cstheory.stackexchange.comNov 7 '12 at 10:22

This question came from our site for theoretical computer scientists and researchers in related fields.

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.

-
I think that the Random-access stored-program (RASP) machine model is even closer to an everyday computer –  Vor Nov 7 '12 at 13:19
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. –  A.Schulz Nov 7 '12 at 13:33
@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). –  Andrej Bauer Nov 7 '12 at 15:09
@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. –  A.Schulz Nov 7 '12 at 16:22
@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. –  Raphael Nov 8 '12 at 17:02