Theory of Adaptive Mechanisms. Volume I. Class of Parallel Processing Automata

摘要

A class of abstract machines called Parallel Processing Automata (denoted PPA) which provides an alternative viewpoint to the concept of iterative arrays is proposed in an attempt to describe some of the properties of parallel computation by means of the simultaneous application of local functions on large arrays of data. The machines of the PPA class are n-dimensional tape Turing machines with (n-1)-dimensional arrays of read-write heads, called read-write units. The formulation of the PPA class is shown to be strongly equivalent to a class of iterative array processors (denoted IAP) which are n-dimensional iterative arrays of identical finite state machines that operate under the direction of a finite state control unit. The control unit processes external inputs and outputs and receives information from an origin cell in the array. At each time unit t of a computation, the control unit determines and broadcasts the state update function that is to be applied to all cells. A programming approach is presented for specifying the operations of the automata studied and its equivalence to the usual state transition function method is shown. (Author)