# Computer, abstract

abstract machine

A mathematical concept describing a model of a computer, while ignoring the bounded capacities of storage registers and other technological parameters of electronic computers. Unlike real computers, abstract computers can compute functions defined on an infinite domain of constructive objects (e.g. integers, words over a finite alphabet, finite graphs, infinite trees, etc., cf. Constructive object). Abstract machines are used as a concept which defines more rigorously the intuitive idea of an algorithm. This concept is used in the study of problems on the existence of an algorithm (i.e. solvability of algorithmic problems, cf. Algorithmic problem), or in investigations on the quality of an algorithm (i.e. estimates on the complexity of the algorithm). It is used also for the formalization of the semantics of algorithmic languages (cf. Algorithmic language), the modelling of certain classes of abstract computers by other classes (e.g. in order to simulate parallel algorithms by sequential ones).

Abstract computers may be classified by the complexity of their structure and also by the type of information processed by the algorithms. The main classes of abstract computers are listed below.

1) Abstract computers which process words over a finite alphabet. The complexity of their structure most simple in order to meet the special needs of the theory. Typical representatives are the Turing machine, the Minsky machine, the normal algorithms of Markov (cf. Normal algorithm), and the Post canonical system. Abstract computers are often utilized to demonstrate the unsolvability of algorithmic problems, and in estimates of the complexity of algorithms (cf. Algorithm, computational complexity of an).

2) Abstract computers with the same complexity of structure as those in class 1), but which process matrices, finite graphs and arbitrary complexes. Typical representatives include the algorithms of Kolmogorov, von Neumann's cellular automata and growing automata. While in the algorithms of Kolmogorov information is processed locally, in von Neumann's cellular and in growing automata this takes place in parallel. Universal abstract computers have been built; they have satisfactory characteristics and are able to model arbitrary abstract computers of the same type. Maximum-speed (real-time) computations have been studied on certain classes of abstract computers.

3) Abstract computers which usually process words or integers and have an elaborate structure determined by practical requirements, having much in common with that of real computers. Typical representatives are the so-called operator algorithms  and machines with random access to the memory. Such abstract computers are used to estimate the complexity of algorithms employed in practice, and to model abstract computers.

4) Abstract computers with the same complexity of structure as those in class 3), but which process arbitrary graphs (most often infinite trees). They are the product of development of the abstract computers of class 3), designed for adaptation to the special features of algorithmic languages. Such abstract computers are used in the formalization of the semantics of algorithmic languages, and to demonstrate the correctness of programs. Typical representatives include abstract computers employed in the specification of the semantics of Algol-68 and PL/I.

How to Cite This Entry:
Computer, abstract. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Computer,_abstract&oldid=46436
This article was adapted from an original article by V.A. Nepomnyashchii (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article