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* <= *r ^{k}*
for arbitrary

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