RECOGNITION OF TOPOLOGICAL INVARIANTS BY ITERATIVE ARRAYS.
MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC
Pagination or Media Count:
A study is made of the recognition and transformation of figures by iterative arrays of finite state automata. A figure is a finite rectangular two-dimensional array of symbols. The iterative arrays considered are also finite, rectangular, and two-dimensional. The automata comprising any given array are called cells and are assumed to be isomorphic and to operate synchronously with the state of a cell at time t 1 being a function of the states of it and its four nearest neighbors at time t. At time t 0 each cell is placed in one of a fixed number of initial states. The pattern of initial states thus introduced represents the figure to be processed. The resulting sequence of array states represents a computation based on the input figure. If one waits for a specially designated cell to indicate acceptance or rejection of the figure, the array is said to be working on a recognition problem. If one waits for the arrays to come to a stable configuration representing an output figure, the array is said to be working on a transformation problem. In addition to the formal results, several open questions are presented and some iterative programming techniques are considered. Author
- Computer Systems