R70-18 Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines

The paper begins with a good formal introduction to iterative arrays, discussing briefly their relation to other automata, particularly the "tessellation structures" of Moore [1] and von Neumann [2]. Attention is then restricted to iterative arrays viewed as real-time tape acceptors. The author proves a speedup theorem, which shows how to speed up an array by a constant factor k. The speedup is done by using a length k encoding of the input tapes, and realizing blocks of the array as finite-state machines in a new array which operates k times as fast. The complexity classes of arrays defined by the author ignore the complexity of the modules of which the array is composed. Thus, the speeded-up array is a member of the same class of arrays as the array whose behavior it imitates. The author then proves that the pattern of interconnection ("stencil") of any array may be reduced to allow direct communication only between nearest neighbors without reducing the real-time computing power of the array. This again involves increasing the complexity of the finite-state machines in the array.