“Remarks on a 25 year old theorem on two-dimensional cellular automata
J. M. Greenberg, Curtis Greene, S. P. Hastings · 2005
The purpose of this brief note is to call attention to a theorem published almost twenty-…ve years ago [GGH] on two dimensional cellular automata which we believe is still of interest, but which seems to be very little known. One reason for this obscurity may be that when we wrote this paper, we did not know the term “cellular automata”, and so it does not appear in the title or elsewhere in the paper. A second reason may be that the journal itself was discontinued more than 15 years ago. Despite the long intervening period, we are not aware of another theorem like it in this …eld. The model in question is quite well known, as a discrete model of “excitable media”. See for example [W], where the model is described (with acknowledgement) and some of the patterns are shown. What seems to be largely unknown is that we proved a theorem which allows one to predict from the initial condition an important aspect of the long time behavior of this model. The theorem is based on de…ning a “topological invariant ” for the model. We now state a special case of the main result in the paper, in order for the reader to decide quickly if the result indeed merits reading further, and perhaps even looking up the original reference. We consider a speci…c three-state cellular automata on a two-dimensional square lattice. This means that to each index pair (i; j), and for each integer valued “time” n 0: we associate a number from the set f0; 1; 2g, denoted by sn (i; j) ; and this mapping obeys a set of rules which enable us to determine sn+1 (i; j) if we know sn (i; j) and also the values of fsn (i 0; j 0)g for (i 0; j 0) lying in some “neighborhood set” of (i; j). The nature of this neighborhood does not matter much in the statement of the theorem. Indeed, the result is not restricted to two dimensions. For the purpose of this basic example, consider that the neighborhood of the “cell ” (i; j)