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
Distribution Statement : APPROVED FOR PUBLIC RELEASE