Skip to main content
Mathematics LibreTexts

11.2: Examples of Simple Binary Cellular Automata Rules

  • Page ID
    7830
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Majority rule The two exercises in the previous section were actually examples of CA with a state-transition function called the majority rule (a.k.a. voting rule). In this rule, each cell switches its state to a local majority choice within its neighborhood. This rule is so simple that it can be easily generalized to various settings, such as multi-dimensional space, multiple states, larger neighborhood size, etc. Note that all states are quiescent states in this CA. It is known that this CA model self-organizes into geographically separated patches made of distinct states, depending on initial conditions. Figure 11.4 shows an example of a majority rule-based 2-D CA with binary states (black and white), each of which is present at equal probability in the initial condition.

    Fig. 11.4.PNG
    Figure \(\PageIndex{1}\): Typical behavior of binary CA with a Moore neighborhood governed by the majority rule.

    Parity rule The parity rule, also called the XOR (exclusive OR) rule, is another well known state-transition function for CA. Its state-transition function is defined mathematically as
    \[s_{t+1}(x) = \sum_{i=0}^{n-1} s_{t}(x+x_i) \qquad{(mod \ k),} \label{(11.2)} \]

    where \(k\) is the number of states (\(k = 2\) for binary CA). It is known that, in this CA, any arbitrary pattern embedded in the initial configuration replicates itself and propagates over the space indefinitely. Figure 11.2.2 shows examples of such behaviors. In fact, this self-replicative feature is universal for all CA with parity rules, regardless of the numbers of states (\(k\)) or the neighborhood radius (\(r\)). This is because, under this rule, the growth pattern created from a single active cell (Fig. 11.2.2, top row) doesn’t interact with other growth patterns that are created from other active cells (i.e., they are “independent” from each other). Any future pattern from any initial configuration can be predicted by a simple superposition of such growth patterns.

    Game of Life The final example is the most popular 2-D binary CA, named the “Game of Life,” created by mathematician John Conway. Since its popularization by Martin Gardner in Scientific American in the early 1970s [35, 36], the Game of Life has attracted a lot of interest from researchers and mathematics/computer hobbyists all over the world, because of its fascinating, highly nontrivial behaviors. Its state-transition function uses the Moore neighborhood and is inspired by the birth and death of living organisms and their dependency on population density, as follows:

    • A dead (quiescent) cell will turn into a living (active) cell if and only if it is surrounded by exactly three living cells.

    Fig. 11.5 Top Row.PNG

    Fig. 11.5 Bottom Row.PNG
    Figure \(\PageIndex{2}\): Typical behaviors of binary CA with a von Neumann neighborhood governed by the parity (XOR) rule.
    • A living cell will remain alive if and only if it is surrounded by two or three other living cells. Otherwise it will die.

    The Game of Life shows quite dynamic, almost life-like behaviors (Fig. 11.3.1). Many intriguing characteristics have been discovered about this game, including its statistical properties, computational universality, the possibility of the emergence of self-replicative creatures within it, and so on. It is often considered one of the historical roots of Artificial Life1, an interdisciplinary research area that aims to synthesize living systems using non-living materials. The artificial life community emerged in the 1980s and grew together with the complex systems community, and thus these two communities are closely related to each other. Cellular automata have been a popular modeling framework used by artificial life researchers to model self-replicative and evolutionary dynamics of artificial organisms [37, 38, 39, 40].

    1http://alife.org/


    This page titled 11.2: Examples of Simple Binary Cellular Automata Rules is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Hiroki Sayama (OpenSUNY) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.