Cellular Automata (CA) Papers
Simple Nontrivial Self-Reproducing Machines
Pattern Recognition by Finite Cellular Automata
The Queen Bee Theorem: A Desynchronization Theorem for Cellular Automata
Introduction and Survey of Cellular Automata and Polyautomata Theory
Real-Time Language Recognition by One-Dimensional Cellular Automata
Two-Dimensional Formal Languages and Pattern Recognition by Cellular Automata
Simple Computation-Universal Cellular Spaces
Cellular Automata Complexity Trade-Offs
General Shift-Register Sequences of Arbitrary Cycle Length
Cellular Automata and Formal Languages
Simple Computation-Universal Cellular Spaces and Self-Reproduction
IEEE FOCS = the Symposium on the Foundations of Computer Science of the Institute of Electrical and Electronics Engineers, formerly known as the Switching and Automata Theory Symposium (SWAT). My proudest contribution to this proceedings is a cover design used for decades.
Encyclopedia of Computer Science, 4th edition, edited by Anthony Ralston and Edwin D Reilly, International Thomson Publishing, Jan 1993. I wrote the original entry for the 1st edition and have updated it for each subsequent edition, 1976, 1983, 1993.
Pattern Recognition by Finite Cellular Automata
Accepted for publication by Journal of Computer and System Sciences, c1974, but never completed (I changed careers to computer graphics instead, and this paper depended on the Queen Bee paper which was rejected for publication). The principal results of these two papers eventually appeared in the book Picture Languages: Formal Models for Picture Recognition, edited by Azriel Rosenfeld, Chapters 3 and 5, Academic Press, NY, 1979.
Abstract. The class of pattern sets accepted by cellular automata (CA, finite, connected subsets of cells in a 2-dimensional cellular space) is shown to be precisely the class of languages generated by the monotonic array grammars, a generalization of context-sensitive grammars to the 2-dimensional integer grid. The relationships of rectangular CA and simply-connected CA to this larger class of CA are established. The sets of rectangular patterns and simply-connected patterns are shown to be recognized within perimeter time by deterministic CA. The set of simple closed curves, the set of well-nested simple closed curves, the majority predicate, and the set of patterns with positive Euler number are shown to be recognized within diameter time by deterministic rectangular CA. The Queen Bee Theorem is used to show the equivalence of the isotonic and the monotonic array grammars and to prove the equivalence of two modes of pattern recognition. A standard derivation form, the northeast derivation form, is established for monotonic array grammars.
The Queen Bee Theorem: A Desynchronization Theorem for Cellular Automata
Abstract. Any cellular automaton (CA) can desynchronize. That is, any finite connected collection of identical finite-state machines (cells), each lying at a point in 2-dimensional integer space and interconnected with at most four of its nearest neighbors, can desynchronize in the sense that there is a cell design such that a CA of these cells, all of which are initially in the same state (synchronized), can find and distinguish, by local operations only, one and only one of its members. Furthermore, the desynchronization occurs within perimeter time, and the cell design is independent of the size or shape of the CA.
Rejected for publishing (but see above)
Simple Nontrivial Self-Reproducing Machines
Artificial Life II, Santa Fe Institute Studies in the Sciences of Complexity, Vol X, edited by C G Langton, C Taylor, J D Farmer, and S Rasmussen, Addison-Wesley, 1991, 709-725 (Proceedings of the ALIFE2 (Artificial Life 2) Conference, Santa Fe, New Mexico, Feb 1990)
Abstract. A simple and brief proof of the existence of nontrivial self-reproducing machines, as cellular automata (CA) configurations, is presented, which relies only on computation universality. Earlier proofs are book length and rely on "construction universality." Furthermore, simple CA are shown to support nontrivial self-reproduction—hence, simultaneously simple and nontrivial. Nontriviality is guaranteed by the requirement that the machine which reproduces itself is also a universal computer. Biological relevance—or non-relevance—is also briefly discussed, as is trivial self-reproduction, called self-replication.
Introduction and Survey of Cellular Automata and Polyautomata Theory
in Automata, Languages, Development, edited by A Lindenmayer and G Rozenberg, North-Holland Publishing Company, 1976, 405-422.
This is an extensive survey and bibliography of the field of CA (I was calling them "polyautomata" at the time) up to 1975. I added the words "Cellular Automata and" to the original title when I transcribed the original article into online form.
It was originally written as the introduction to the German edition of Theory of Self-Reproducing Automata, by John von Neumann, edited (posthumously) by Arthur W Burks, University of Illinois Press, Urbana, 1968. Von Neumann performed the work, completed by Burks, in 1952-53. The German publishers never published the German edition, but gave me permission to publish my survey in the book listed above, the proceedings of a conference held in Noordwijkerhout, The Netherlands, Apr 1975. I like to call this conference ALife0 - for Artificial Life 0 conference - since it was the first attempt I know to cross-fertilization between biologists and computer scientists. Many of the players at this conference were present for ALife1, ALife2, etc - cf Simple Nontrivial Self-Reproducing Machines . Other participants at ALife0 were Karel Culik, Pauline Hogeweg, John Holland, Aristid Lindenmayer, and Stanislaw Ulam .
Real-Time Language Recognition by One-Dimensional Cellular Automata
Journal of Computer and System Sciences, Vol 6, No 3, 233-253, Jun 1972
Abstract. Pattern recognition by parallel devices is investigated by studying the formal language recognition capabilities of 1-dimensional cellular automata (CA). The precise relationships of CA to iterative automata and to Turing machines are established: In both cases, CA are inherently faster. The relationship of context-free languages to the languages recognized in real time by bounded CA is detailed. In particular, nondeterministic bounded CA can recognize the context-free languages in real time. The deterministic case remains open, but many partial results are derived. Finally, closure properties and CA transformation lemmas are presented.
Existence of Finite Automata Capable of Being Synchronized although Arbitrarily Connected and Numerous
By Pierre Rosenstiehl, translated from the French by Alvy Ray Smith at New York University, Nov 1971 (unauthorized). A freeform translation of the title might be The Firing Squad Synchronization Problem for Cellular Automata on a Graph.
Paper originally published in French as Existence d'automates finis capables de s'accorder bien qu'arbitrairement connectes et nombreaux, ICC Bulletin, 1966, Vol 5, 245-261.
Abstract. A collection of n finite, identical automata are considered, where each one, at each unit time step, takes a new state as a function of the state taken at the preceding step by itself and by certain other automata in the collection, called its neighbors, arbitrarily chosen, but limited in number. The neighborhood relation is assumed symmetric. One is asked to determine for a given d, and independently of n, the number of states and the state-transition function of an automaton of the type which has the following property: All automata in the collection are put in the resting state except for one of them, A', arbitrarily chosen, put into an initial state distinct from the resting state; then at the end of a finite length of time all automata in the collection depending, by the neighborhood relation, directly or indirectly on A', are put simultaneously and for the first time into a final state agreed upon in advance. It is said then that our arbitrarily numerous automata are connected into an arbitrary network of automata of degree d, and that those in the component connected to A' have been synchronized.
Two-Dimensional Formal Languages and Pattern Recognition by Cellular Automata
12th IEEE FOCS Conference Record, 144-152, Oct 1971
Abstract. A formal study of pattern recognition capabilities of cellular automata (CA) is undertaken based on a class of recently introduced grammars for two dimensions, the array grammars, which can be thought of as the 2-dimensional generalization of context-sensitive grammars. The class of languages (patterns) generated by array grammars is shown to be precisely the class of languages accepted by CA forming rook-connected finite subsets of the plane. Thus the usual generalization to rectangular array-bounded CA is a special case of this class of machines. The concept of perimeter time is introduced as a natural measure of computing speeds for 2-dimensional CA, and connectedness and convexity are related to this measure. The class of patterns with positive Euler number is shown to be linear-time recognizable by rectangular array-bounded CA, thus solving an open problem of Beyer.
See also Pattern Recognition by Finite Cellular Automata
Simple Computation-Universal Cellular Spaces
Journal of the Association for Computing Machinery, Vol 18, No 3, 339-353, Jul 1971
Abstract. The specialization of the theory of cellular spaces (cellular automata (CA)) to those spaces which compute partial recursive functions is presented. Neighborhood reduction and state-set reduction are shown to be particularly simple in this special theory, and one dimension is proved to be sufficient for computation universality. Several computation-universal CA (CUCA) are exhibited which are simple in the sense that each cell has only a small number q of states and a small number p of neighbors. For example, a 1-dimensional CUCA with pq = 36 is presented. Two quite different proofs of the existence of a 1-dimensional CUCA with only two neighbors are given. Finally, one of the theorems derived is used to settle three open decidability questions.
Cellular Automata Complexity Trade-Offs
Information and Control, Vol 18, No 5, pp 466-482, Jun 1971
Abstract. The general theory of cellular automata (CA) is investigated with special attention to structural complexity. In particular, simulation of CA by CA is used to make explicit trade-off relationships between neighborhood size and state-set cardinality. A minimum neighborhood template with d+1 elements is established for the class of d-dimensional CA. The minimum state set for this class is shown to be the binary state set. The temporal costs, if any, of structural complexity trade-offs are also studied. It is demonstrated that any linear time cost can be eliminated and, in fact, a speed-up by arbitrary positive integer factor k can be attained at an increased structural cost.
General Shift-Register Sequences of Arbitrary Cycle Length
IEEE Transactions on Computers, Vol C-20, No 4, 456-459, Apr 1971
Abstract. An r-ary shift-register sequence is desired that has arbitrary cycle length L <= rk for arbitrary r and k, where k is the number of stages (degree) of the shift register. The existence of such sequences is established for "almost all" cycle lengths L. Furthermore, existence of such sequences which are "zero free" for almost all cycle lengths L is proved.
Cellular Automata and Formal Languages
11th IEEE FOCS Conference Record, 216-224, Oct 1970
Abstract. A set of equivalences is established among cellular automata (CA), iterative acceptors, and linear-bounded automata. However, CA are shown to be inherently faster than interactive acceptors. Many positive results are presented to indicate that the context-free languages can, perhaps, be accepted in time n and space n by CA, where n is the length of the CA.
See also Real-Time Language Recognition by One-Dimensional Cellular Automata
Technical Report No 2, Digital Systems Laboratory, Stanford Electronics Laboratories, Stanford University, Stanford, CA, Dec 1969
My PhD dissertation, supervised by Prof Michael Arbib at Stanford. There are several bugs in this report, fixed in the derivative publications Cellular Automata Complexity Trade-Offs, Simple Computation-Universal Cellular Spaces, Simple Nontrivial Self-Reproducing Machines, General Shift-Register Sequences of Arbitrary Cycle Length, and Real-Time Language Recognition by One-Dimensional Cellular Automata
Simple Computation-Universal Cellular Spaces and Self-Reproduction
9th IEEE FOCS Conference Record, 269-277, Oct 1968
Abstract. Cellular spaces (aka cellular automata (CA)) computationally equivalent to any given Turing machine are exhibited which are simple in the sense that each cell has only a small number of states and a small neighborhood. Neighborhood reduction theorems are derived in this interest, and several simple computation-universal CA are presented. Conditions for computation-universality of a CA are investigated, and, in particular, the conjecture that unbounded but boundable propagation in a space is a sufficient condition is refuted. Finally, the computation-universal CA derived in the study are used to introduce, via recursive function theory, examples of simple self-reproducing universal Turing machine configurations in one and two dimensions.
See also Cellular Automata Complexity Trade-Offs, Simple Computation-Universal Cellular Spaces, Simple Nontrivial Self-Reproducing Machines, and Real-Time Language Recognition by One-Dimensional Cellular Automata