Model computer

Defintion

The model computer consists of a storage and a processing unit.

The storage is a large array of elementary storage units, each of which stores one bit of information.

The processing unit is a Boolean circuit, that is, a number of logical gates connected by wires. Both the input and the output pins are attached to the bits in the storage, in both cases in a one-to-one correspondence.

In each clock cycle of the computer, the current values of the storage bits are imported into the combinatorial circuit via the input bins, and the values exported at the output bins are the new values of the storage bins.

In each clock cycle, only a single machine instruction is executed, that is, a single bit is copied or two bits are processed logically/arithmetically (giving the values of one or two other bits). In particular, in each clock cycle, a constant, instruction-specific number of gates is involved in the update of the bit values in the storage.

For simplicity, interfaces to background devices, terminals, networks, etc., are ignored here. These details are not necessary for the analysis of algorithms and data structures.

It may be useful to regard the storage units as being organized in larger units (machine words) of fixed size like in a real-world computer. But this is not necessary for most considerations. In fact, an elementary instruction on fixed-size machine words (like on RISC) machines amounts to a constant number of elementary operations on bits. A constant factor on the number of execution steps makes no difference with respect to asymptotic complexity. In other words, a machine model with elementary instructions on bits and an analogously organized machine model elementary instructions on machines words are equivalent and undistinguishable with respect to asymptotic complexity.

Known Related Topics

All descriptions of algorithms and data structures and algorithmic problems in this wiki shall be based on this model of computation (unless clearly stated otherwise).

Remark

This model computer is equivalent to the Turing machine model with respect to computability and asymptotic complexity of algorithmic problems. Therefore, all computability and complexity results in this wiki are identical to those in Theoretical Computer Science (but derived differently).

Reference

General introduction to abstract machines.