Model of computation

A model of computation (Модель вычисления) is a formal, abstract definition of a computer. Using a model, one can easily analyze the intrinsic execution time or memory space of an algorithm while ignoring many implementation issues. There are many models of computations which differ in computing power (that is, some models can perform computations impossible for other models) and the cost of various operations.

The best-known example of a model of computation is the Turing machine. As all our models, a Turing machine also operates in discrete times. It consists of a finite state machine controller, a read-write head, and an unbounded sequential tape. Depending on the current state and symbol read on the current sell of the tape, the machine can change its state, write a symbol in the current sell and move the head to the left or right. Unless otherwise specified, a Turing machine is deterministic, i.e. permits at most one next action at any step in a computation.

The input-output format of a Turing machine is specified as follows. The machine begins its computation by scanning the leftmost symbol of a given input word in a specific initial state. The input is accepted iff the computation reaches a specific final state. If the machine is viewed as a translator rather than an acceptor, then the word on the tape, after machine has reached a final state, constitutes the output to the given input. Some of the symbols on the tape might thus be disregarded.

Let [math]\displaystyle{ T }[/math] be a nondeterministic Turing machine. When scanning a specific symbol in a specific state, [math]\displaystyle{ T }[/math] may have several possibilities for its behavior. Otherwise, a nondeterministic Turing machine is defined as a deterministic one. A word [math]\displaystyle{ \alpha }[/math] is accepted iff it gives rise to an accepting computation, independently of the fact that it might also give rise to computations leading to failure. Thus, as in connection with nondeterministic machines in general, all roads to failure are disregarded if there is one possible road to success.

The tape of a Turing machine can be viewed both as an input and output channel and as a potentially infinite external memory. The basic difference between Turing machines and other types of automata can be briefly described as follows. A finite automaton has only an internal memory deter\-min\-ed by its finite state set; the input tape is not used as an additional memory. A finite automaton just reads the input in one sweep from the left to right. In a linear-bounded automaton, the external memory is bounded from above by the size of the input word (or by a linear function of it, which amounts to the same thing). In a pushdown automaton, the access to the information in the infinite external memory is very limited and is based on the principle first in-last out; a pushdown automaton is a finite automaton combined with a potentially infinite pushdown tape.

Hence, clearly, a Turing machine is more general than the other model of computation we have considered. It is also a general model: every algorithm (in the intuitive sense) can be realized as a Turing machine (Church's thesis).

Another well-known example of a general model of computation is a random access machine (or RAM) whose memory consists of an unbounded sequence of registers, each of which may hold an integer. In this model, arithmetic operations are allowed to compute the address of a memory register.

Other names are Abstract machine and Abstract computer.