Theory of Automatons

Theory of Automatons 

an area of theoretical cybernetics in which various discrete data processors are studied. It originated in the early 1950’s in connection with practical computer design requirements and with the development of mathematical models for data-processing operations in biological, economic, and other systems. It is an independent branch of mathematics, having a variety of problems and applications.

The basic concepts of the theory are the concept of an abstract automaton and the concept of combining automatons. These are reasonable abstractions of real existing discrete devices—automatons. The concept of an abstract automaton permits a device to be characterized in terms of its functional algorithm—that is, the algorithm of the data process it performs. The concept of combination of automatons permits a device to be characterized from the structural point of view; in other words, it depicts how a given device is constructed from other, more elementary devices.

The theory has several parts. One is the abstract algebraic theory of automatons. This part studies the properties of abstract automatons and the various methods of representing them. The term abstract automaton is given to the object A = A (ℌ, X, Y, δ, γ) consisting of three nonempty sets—the set of states ℋ, the set of input signals X, and the set of output signals Y—and two functions that uniquely map the set ℋхX’ into ℋ, δ (a, x) of the transitions and the set ℋ X X into Y, ʎ (a, x) of the outputs. An abstract automaton is called finite if the sets ℋ, X, and Y are finite. The abstract algebraic theory of automatons can be divided into the theory of finite automatons and the theory of infinite automatons. The basic problems of the finite automaton theory can be regarded as solved. The most interesting results of the theory are the theorem for the analysis and synthesis of finite automatons which gives the characteristics of events occurring in finite automatons, theorems of definite relationships in the algebra of regular events, evaluations of the duration of experiments with finite automatons, and a series of results from investigations into the algebraic properties of abstract automatons. In the theory of infinite automatons, various conceptions of infinite automatons are considered, and the classes of special kinds of infinite automatons are distinguished more accurately. This theory is important for its close association with the general theories of formal languages and grammars and also with the theory of algorithms. Within the scope of the abstract algebraic theory of automatons, an approach was outlined in the late 1960’s for the solution to the problem of creating an algebra of algorithms and of designing apparatus for formal transformations of expressions in this algebra, thus permitting a completely new approach to solving these types of problems as the equivalent of algorithm schemes and making it possible to efficiently solve optimization problems in the design of discrete devices.

Another part of the theory of automatons is the structural theory. Here an automaton is represented in the form of a network whose elements are chosen from a certain ensemble of elementary automatons, are connected among themselves in some special manner, and store and transform elementary signals. The principal results of the structural theory of automatons are the practical techniques of constructing complex logic networks, of investigating their complexity by means of asymptotic evaluations, of solving the problem of completeness for a system of elementary automatons, of coding the states of automatons, of optimal realization for logic networks in various elementary structures, and so forth. The structural theory of automatons is closely associated with the coding theory, the general theory of switching functions, the theory of combining circuits, information theory, the reliability theory of discrete devices, and so forth.

The third part of the theory of automatons is the theory of random automatons and adaptive systems.

The principal application of the theory of automatons is in the practical design of and automation of the design of discrete devices, especially computers. It is gaining in importance in such classical mathematical disciplines as the theory of algorithms, on the one hand, and in such modern mathematical theories in mathematics and cybernetics as the theory of formal systems, programming theory, and the theory of formal languages and grammars, on the other.

REFERENCES

Avtomaty. Edited by C. E. Shannon and J. McCarthy. Moscow, 1956. (Collection of articles; translated from English.)
Glushkov, V. M. Sintez tsifrovykh avtomatov. Moscow, 1962.
Glushkov, V. M. Vvedenie v kibernetiku. Kiev, 1964.
Kobrinskii, N. E., and B. A. Trakhtenbrot. Vvedenie v teoriiu konechnykh avtomatov. Moscow, 1962.
Logika. Avtomaty. Algoritmy. Moscow, 1963.
Gill, A. Vvedenie v teoriiu konechnykh avtomatov. Moscow, 1966. (Translated from English.)

IU. V. KAPITONOVA