Accession Number : AD0651027

Title :   THEORY OF A PARALLEL-ACTING AUTOMATION.

Descriptive Note : Technical rept.,

Corporate Author : ARMY ELECTRONICS COMMAND FORT MONMOUTH NJ

Personal Author(s) : Amoroso, S. M.

Report Date : JAN 1967

Pagination or Media Count : 210

Abstract : 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)

Descriptors :   (*AUTOMATION, THEORY), COMPUTER LOGIC, SWITCHING CIRCUITS, DIGITAL SYSTEMS.

Subject Categories : Cybernetics
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE