automata theory
automata theory, body of physical and logical principles underlying the operation of any electromechanical device (an automaton) that converts information from one form into another according to a definite procedure. Real or hypothetical automata of varying complexity have become indispensable tools for the investigation and implementation of systems that have structures amenable to mathematical analysis.
An example of a typical automaton is a pendulum clock. In such a mechanism the gears can assume only one of a finite number of positions, or states, with each swing of the pendulum. Each state, through the operation of the escapement, determines the next succeeding state, as well as a discrete output, which is displayed as the discrete positions of the hands of the clock. As long as such a clock is wound and its operation is not interfered with, it will continue to operate unaffected by outside influences except the effect of gravity on the pendulum.
More general automata are designed to respond to changes in external conditions or to other inputs. For example, thermostats, automatic pilots of aircraft, missile guidance systems, telephone networks, and controls of certain kinds of automatic elevators are all forms of automata.
The internal states of such devices are not determined solely by their initial state, as is the case of the pendulum clock, but may be determined by an input from a human operator, from another automaton, or by an event or series of events in the environment. A thermostat, for instance, has an “on” or “off” state that depends on the temperature. The best known general automaton is the modern electronic computer, the internal states of which are determined by the data input and which operates to produce a certain output.
Nature and origin of modern automata
The components of automata consist of specific materials and devices, such as wires, transistors, levers, relays, gears, and so forth, and their operation is based on the mechanics and electronics of these parts. The principles of their operation as a sequence of discrete states can, however, be understood independently of the nature or arrangement of their components. In this way, an automaton may be considered, abstractly, as a set of physically unspecified states, inputs, outputs, and rules of operation, and the study of automata as the investigation of what can be accomplished with these. This mode of abstraction yields mathematical systems that in certain respects resemble logical systems. Thus, an automaton can be described as a logically defined entity that can be embodied in the form of a machine, with the term automaton designating both the physical and the logical constructions.
In 1936 an English mathematician, Alan Mathison Turing, in a paper published in the Proceedings of the London Mathematical Society (“On Computable Numbers with an Application to the Entscheidungsproblem”), conceived a logical machine the output of which could be used to define a computable number. For the machine, time was considered to be discrete and its internal structure, at a given moment, was described simply as one of a finite set of states. It performed its functions by scanning an unbounded tape divided into squares, each of which either contained specific information in the form of one of a finite number of symbols or was blank. It could scan only one square at a time, and, if in any internal state except one called “passive,” it was capable of moving the tape forward or backward one square at a time, erasing a symbol, printing a new symbol if the square was blank, and altering its own internal state. The number it computed was determined by symbols (the “program”) provided on a finite portion of the tape and the rules of operation, which included stopping when the passive state was reached. The output number was then interpreted from the symbols remaining on the tape after the machine stopped.
Automata theory since the middle of the 20th century has been extensively refined and has often found practical application in civilian and military machines. The memory banks of modern computers can store large (though finite) amounts of information. (For further information on computers and their applications, see information processing.) The original Turing machine had no limit to the memory bank because each square on the unbounded tape could hold information. The Turing machine continues to be a standard reference point in basic discussions of automata theory, and many mathematical theorems concerning computability have been proved within the framework of Turing’s original proposal.
Neural nets and automata
The finite automata of McCulloch and Pitts
Part of automata theory lying within the area of pure mathematical study is often based on a model of a portion of the nervous system in a living creature and on how that system with its complex of neurons, nerve endings, and synapses (separating gap between neurons) can generate, codify, store, and use information. The “all or none” nature of the threshold of neurons is often referred to in formulating purely logical schemata or in constructing the practical electronic gates of computers. Any physical neuron can be sufficiently excited by an oncoming impulse to fire another impulse into the network of which it forms a part, or else the threshold will not be reached because the stimulus is absent or inadequate. In the latter case, the neuron fails to fire and remains quiescent. When several neurons are connected together, an impulse travelling in a particular part of the network may have several effects. It can inhibit another neuron’s ability to release an impulse; it can combine with several other incoming impulses each of which is incapable of exciting a neuron to fire but that, in combination, may provide the threshold stimulus; or the impulse might be confined within a section of the nerve net and travel in a closed loop, in what is called “feedback.” Mathematical reasoning about how nerve nets work has been applied to the problem of how feedback in a computing machine can result in an essential ingredient in the calculational process.
Original work on this aspect of automata theory was done by Warren S. McCulloch and Walter Pitts at the Research Laboratory of Electronics at the Massachusetts Institute of Technology starting in the 1940s.
The definitions of various automata as used here are based on the work of two mathematicians, John von Neumann and Stephen Cole Kleene, and the earlier neurophysiological researches of McCulloch and Pitts, which offer a mathematical description of some essential features of a living organism. The neurological model is suggested from studies of the sensory receptor organs, internal neural structure, and effector organs of animals. Certain responses of an animal to stimuli are known by controlled observation, and, since the pioneering work of a Spanish histologist, Santiago Ramón y Cajal, in the latter part of the 19th and early part of the 20th century, many neural structures have been well known. For the purposes of this article, the mathematical description of neural structure, following the neurophysiological description, will be called a “neural net.” The net alone and its response to input data are describable in purely mathematical terms.
A neural net may be conveniently described in terms of the kind of geometric configuration that suggests the physical structure of a portion of the brain. The component parts in the geometric form of a neural net are named (after the physically observed structures) neurons. Diagrammatically they could be represented by a circle and a line (together representing the body, or soma, of a physiological neuron) leading to an arrowhead or a solid dot (suggesting an endbulb of a neuron). A neuron may be assumed to have either an excitatory or an inhibitory effect on a succeeding one; and it may possess a threshold, or minimum number of unit messages, so to speak, that must be received from other neurons before it can be activated to fire an impulse. The process of transmission of excitation mimics that which is observed to occur in the nervous system of an animal. Messages of unit excitation are transmitted from one neuron to the next, and excitation is passed along the neural net in quantized form, a neuron either becoming excited or remaining non-excited, depending on the states (excitatory or quiescent) of neurons whose endbulbs impinge upon it. Specifically, neuron N, with threshold h, will be excited at time t, if and only if h or more neurons whose excitatory endbulbs impinge upon it are excited at time t - 1 and no neuron whose inhibitory endbulb impinges upon it is excited at time t - 1. A consistent picture can be made of these conditions only if time and excitation are quantized (or pulsed). It is assumed conventionally that a unit of time is required for the transmission of a message by any neuron.
Certain neurons in the configuration mathematically represent the physiological receptors that are excited or left quiescent by the exterior environment. These are called input neurons. Other neurons called output neurons record the logical value, excited or quiescent, of the whole configuration after time delay t and transmit an effect to an exterior environment. All the rest stimulate inner neurons.
Any geometric or logical description of the neural structure of an organism formulated as the basis of physical construction must be sufficiently simple to permit mechanical, electric, or electronic simulation of the neurons and their interconnections.
The basic logical organs
The types of events that can excite the automaton and the kinds of responses that it can make must next be considered. By stripping the description down to the most simple cases, the basic organs from which more complicated robots can be constructed may be discovered. Three basic organs (or elementary automata) are necessary, each corresponding to one of the three logical operations of language: the binary operations of disjunction and conjunction, leading to such propositions as A ∪ B (read “A or B”), A ∩ B (read “A and B”), and the unary operation of negation or complementation, leading to such propositions as Ac (read “not A” or “complement of A”). First to be considered are the stimulus-response pattern of these elementary automata.
Assuming that a neuron can be in only one of two possible states—i.e., excited or quiescent—an input neuron at a given instant of time t - 1 must be either excited or nonexcited by its environment. An environmental message transmitted to two input neurons N1 and N2 at time t - 1 can then be represented numerically in any one of the four following ways, in which binary digit 1 represents excitation and binary digit 0 represents quiescence: (0, 0), (0, 1), (1, 0), (1, 1). The disjunction automaton must be such that a single output neuron M correspondingly registers at time t the response: 0, 1, 1, 1. The conjunction automaton must be such that a single output neuron M correspondingly registers at time t the response: 0, 0, 0, 1. The negation automaton considered as having two input neurons N1 and N2, of which N1 is always excited, must respond to the environmental messages (1, 0) and (1, 1) with 1, 0, respectively, at the output neuron M.
