THEORY OF A PARALLEL-ACTING AUTOMATION.

The report considers first a subclass of deterministic automata which are characterized by master control programs consisting of finite sequences of instructions. Machines of this subclass are called A sub p-machines. After investigating some of the basic properties of these A sub p-machines, it is shown that with respect to the task of string recognition, these automata are weaker than finite automata and equivalent to a variant of k-limited automata. The next subclass of automata considered is characterized by master control programs that are infinite sequences of instructions each composed of a finite initial sequence of instructions followed by a repeating cycle of instructions. Machines of this subclass are called B sub p-machines. It is shown that with respect to the task of producing defining sets of strings these machines are equivalent to a number of variant B sub p-machines, and it is shown that an arbitrary recursively enumerable set of strings can be produced on some B sub p-machines. The last subclass of these machines considered is characterized by the introduction of a conditional transfer in the master control programs. It is shown that these automata, that are called C sub p-machines, can compute with a very simple instruction set, any effectively computable function. Then it is shown that either limiting our parallel automata to one-way infinite chains, or to communication with neighboring machines of the chain in one direction only, does not limit their theoretical processing capabilities. Author