The one-dimensional Exactly 1 cellular automaton:

Description: Description: Description: Description: Description: exactly1banner.gif

replication, periodicity, and chaos from finite seeds

by Janko Gravner and David Griffeath


In the Exactly 1 cellular automaton (also known as Rule 22 ), every site of the one-dimensional lattice is either in state 0 or in state 1, and a synchronous update rule dictates that a site is in state 1 next time if and only if it sees a single 1 in its three-site neighborhood at the current time. We analyze this rule started from finite seeds, i.e., those initial configurations that have only finitely many 1’s. Three qualitatively different types of evolution are observed: replication, periodicity, and chaos. We focus on rigorous results, assisted by algorithmic searches, for the first two behaviors. In particular, we explain why replication is observed so frequently and present a method for collecting the smallest periodic seeds. Some empirical observations about chaotic seeds are also presented.

The full article (< 1 MB pdf)

Links to Cellular Automaton Simulation Software:

MCell                           Golly

Supporting Experiment and Data Files:

Experiments corresponding to the examples of the article, an archive of Mcell (.mcl) and Golly (.rle) initializations

Five periodic seeds not detailed in the article, an archive of Mcell (.mcl) and Golly (.rle) initializations

Raw data generated for the article, an archive of .txt and .doc files

Partially supported by the National Science Foundation and the Republic of Slovenia’s Ministry of Science