# 11.1: Deﬁnition of Cellular Automata

- Page ID
- 7829

\( \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}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)“*Automaton*” (plural: “automata”) is a technical term used in computer science and mathematics for a theoretical machine that changes its internal state based on inputs and its previous state. The state set is usually defined as finite and discrete, which often causes nonlinearity in the system’s dynamics.

*Cellular automata *(CA) [18] are a set of such automata arranged along a regular spatial grid, whose states are simultaneously updated by a uniformly applied *state-transition function* that refers to the states of their neighbors. Such simultaneous updating is also called *synchronous updating* (which could be loosened to be asynchronous; to be discussed later). The original idea of CA was invented in the 1940s and 1950s by John von Neumann and his collaborator Stanisław Ulam. They invented this modeling framework, which was among the very first to model complex systems, in order to describe self-reproductive and evolvable behavior of living systems [11].

Because CA are very powerful in describing highly nonlinear spatio-temporal dynamics in a simple, concise manner, they have been extensively utilized for modeling various phenomena, such as molecular dynamics, hydrodynamics, physical properties of materials, reaction-diffusion chemical processes, growth and morphogenesis of a living organism, ecological interaction and evolution of populations, propagation of traffic jams, social and economical dynamics, and so forth. They have also been utilized for computational applications such as image processing, random number generation, and cryptography.

There are some technical definitions and terminologies you need to know to discuss CA models, so here comes a barrage of definitions.

Mathematically speaking, CA are defined as a spatially distributed dynamical system where both time and space are discrete. A CA model consists of identical automata (cells or sites) uniformly arranged on lattice points in a D-dimensional discrete space (usually \(D = 1, 2,\) or \(3)\). Each automaton is a dynamical variable, and its temporal change is given by

\[s_{t+1}(x)=F(s_{t}(x+x_{0}), s_{t}(x+x_{1}), ..., s_{t}(x+x_{n-1})), \label{(11.1)} \]

where \(s_{t}(x)\) is the state of an automaton located at \(x\) at time \(t\), \(F\) is the* state-transition function*, and \(N = {x_0,x_1,...,x_{n−1}}\) is the neighborhood. The idea that the same statetransition function and the same neighborhood apply uniformly to all spatial locations is the most characteristic assumption of CA. When von Neumann and Ulam developed this modeling framework, researchers generally didn’t have explicit empirical data about how things were connected in real-world complex systems. Therefore, it was a reasonable first step to assume spatial regularity and homogeneity (which will be extended later in network models).

\(s_t\) is a function that maps spatial locations to states, which is called a* configuration* of the CA at time \(t\). A configuration intuitively means the spatial pattern that the CA display at that time. These definitions are illustrated in Fig. 11.1.1.

Neighborhood \(N\) is usually set up so that it is centered around the focal cell being updated \((x_0 = 0)\) and spatially localized \((|x_i −x_0| ≤ r\) for \(i = 1,2,...,n−1)\), where r is called a radius of \(N\). In other words, a cell’s next state is determined locally according to its own current state and its local neighbors’ current states. A specific arrangement of states within the neighborhood is called a* situation* here. Figure 11.1.2 shows typical examples of neighborhoods often used for two-dimensional CA. In CA with von Neumann neighborhoods (Fig. 11.1.2, left), each cell changes its state according to the states of its upper, lower, right, and left neighbor cells as well as itself. With Moore neighborhoods (Fig. 11.1.2, right), four diagonal cells are added to the neighborhood.

The state-transition function is applied uniformly and simultaneously to all cells in the space. The function can be described in the form of a look-up table (as shown in Fig. 11.1.1), some mathematical formula, or a more high-level algorithmic language.

If a state-transition function always gives an identical state to all the situations that are identical to each other when rotated, then the CA model has* rotational symmetry*. Such symmetry is often employed in CA with an aim to model physical phenomena. Rotational symmetry is called *strong* if all the states of the CA are orientation-free and if the rotation of a situation doesn’t involve any rotation of the states themselves (Fig. 11.1.3, left). Otherwise, it is called* weak* (Fig. 11.1.3, right). In CA with weak rotational symmetry, some states are oriented, and the rotation of a situation requires rotational adjustments of those states as well. Von Neumann’s original CA model adopted weak rotational symmetry.

If a state-transition function depends only on the sum of the states of cells within the neighborhood, the CA is called totalistic. By definition, such state-transition functions are rotationally symmetric. The totalistic assumption makes the design of CA models much simpler, yet they can still produce a wide variety of complex dynamics [34].

The states of CA are usually categorized as either *quiescent *or *non-quiescent*. A cell in a quiescent state remains in the same state if all of its neighbors are also in the same quiescent state. Many CA models have at least one such quiescent state, often represented by either “0” or “ ” (blank). This state symbolizes a “vacuum” in the CA universe. Non-quiescent states are also called active states, because they can change dynamically and interact with nearby states. Such active states usually play a primary role in producing complex behaviors within CA.

Because CA models have a spatial extension as well as a temporal extension, you need to specify spatial boundary conditions in addition to initial conditions in order to study their behaviors. There are several commonly adopted boundary conditions:

This assumes that the space is infinite and completely filled with the quiescent state

This assumes that the space is “wrapped around” each spatial axis, i.e., the cells at one edge of a finite space are connected to the cells at the opposite edge. Examples include a ring for 1-D CA and a torus for 2-D CA

This assumes that cells at the edge of a finite space don’t have neighbors beyond the boundaries. This necessarily results in fewer numbers of neighbors, and therefore, the state-transition function must be designed so that it can handle such cases.

This assumes that cells at the edge of a finite space have fixed states that will never change. This is often the easiest choice when you implement a simulation code of a CA model

Shown below is an example of a one-dimensional totalistic CA model with radius 1 and a periodic boundary condition. White means 0, while gray means 1. Each cell switches to *round(S/3) *in every time step, where S is the local sum of states within its neighborhood. Complete the time evolution of this CA.

Shown below is an example of a two-dimensional totalistic CA model with von Neumann neighborhoods and with no boundary (infinite space) conditions. White means 0 (= quiescent state), while gray means 1. Each cell switches to *round(S/5)* in every time step, where S is the local sum of the states within its neighborhood. Complete the time evolution of this CA.