Cellular automata and the sciences of complexity (part II)
Howard A. Gutowitz · Complexity · 1996
This is the final half of a review of selected problems in the theory of cellular automata. Contents 1 State Transition Graphs 3 2 Cryptography 9 3 Suggested Reading 17 1 State Transition Graphs In the first half of this article, we looked at the behavior of cellular automata on infinite lattices. In this final half we will examine some of the properties of CA acting on finite systems, and trace their relationships with properties of infinite-sized systems. Consider a one-dimensional cellular automaton operating on periodic lattices of cells each having two states. If the size of the periodic lattice is s, then there are 2 s possible configurations of cell states on the lattice. Each configuration maps to a new configuration under the action of the cellular automaton rule. Thus, we think of the configuration as a node in a graph, with an out-going arc leading to its successor configuration. As the number of possible configurations is finite, any initial configuration must map ...