Analysis of Iterative NOR Autonomous Sequential Machines

The autonomous behavior of an array of identical elements is investigated and found to be related closely to the structure of the array. Each element consists of a symmetric Boolean function of the inputs and one unit of delay. The interconnection of the elements is described by a matrix. A function in the element is universal and minimal if there exists an n×n interconnection matrix that will generate each of the autonomous state diagrams of 2ⁿ states. It is shown that no such function can exist. Assuming the NOR function in the element, theorems are presented that test the interconnection matrix in order to determine the autonomous behavior, i. e., state diagram, of the array. In particular, necessary and sufficient conditions for an array to generate a state diagram consisting entirely of cycles or rooted trees are described. If the array generates a cyclic state diagram, the cycle set can be determined from theorems derived in the paper. If the behavior is a rooted tree, theorems are presented that determine the state vector of the root, the maximum path length through the tree, and the number of states at a given distance from the root of the tree.