See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/287249825

Extension of cellular automata by introducing an algorithm of recursive

estimation of neighbors

Article in Artificial Life and Robotics · December 2015

DOI: 10.1007/s10015-016-0287-4

CITATIONS READS

6 109

1 author:

Yoshihiko Kayama
Baika Women's University
20 PUBLICATIONS 115 CITATIONS

SEE PROFILE

All content following this page was uploaded by Yoshihiko Kayama on 27 December 2015.

The user has requested enhancement of the downloaded file.

 Extension of cellular automata by introducing an algorithm
of recursive estimation of neighbors
Yoshihiko Kayama
BAIKA Women’s University, Japan
(Tel: 81-72-643-6221, Fax: 81-72-643-8473)

kayama@baika.ac.jp

Abstract: This study focuses on an extended model of a standard cellular automaton (CA) that includes an extra index
consisting of a radius that defines a perception area for each cell in addition to the radius defined by the CA rule. Extended
standard CA rules form a sequence ordered by this index, which includes the CA rule as its first term. This extension aims at
constructing a model that can be used within the CA framework to study the relationship between information processing and
pattern formation in collective systems. Although the extension presented here is merely an extrapolation to a CA with a larger
rule neighborhood, the extra radius can be interpreted as an individual difference of each cell, which provides a new
perspective to CA. Some pattern formations in extended one-dimensional elementary CAs and two-dimensional Life-like CAs
are presented. It is expected that the extended CA can be applied to various simulations of complex systems and other fields.

Keywords: cellular automata, collective dynamics, complex systems, Conway’s game of life

the relationship between information processing and

1 INTRODUCTION
fluctuation control in CA pattern formation.
Cellular automaton (CA), which consists of cells In this article, we discuss an extended model of standard
arranged in a grid, was proposed by Uram and Neuman [1] CA that includes an extra index consisting of a radius that
in the 1940s. In the 1970s, Conway found a two- defines a perception area for each cell in addition to the
dimensional CA, which he called “the Game of Life,” that radius of the rule neighborhood. Extended rules originating
exhibited complex behaviors evoking biological activities from a standard CA form a sequence ordered by the index,
(Gardner [2] and Berlekamp, Conway, and Guy [3]). In the which includes the CA rule as its first term. The extended
1980s, Wolfram studied one-dimensional CAs (Wolfram [4- model is implemented by an algorithm named “Recursive
7]). He proposed that CA could be grouped into four classes Estimation of Neighbors” (REN), in which the original CA
of complexity: homogeneous (class I), periodic (class II), rule is recursively used to estimate the states of neighboring
chaotic (class III), and complex (class IV). cells. Typical examples of extended CA originating from
Under the CA framework, the neighborhood of each cell one- and two-dimensional binary CAs are presented.
is defined by the CA rule and there is no possibility of The next section shows how the radius of perception
expanding the sensory area of a cell. For example, each cell area of a cell can be introduced in addition to the radius of
of a one-dimensional elementary CA (ECA) acquires states the CA neighborhood by using the REN algorithm. In
of the three cells within its radius-one neighborhood to Section 3, the definition of the extended CA is applied to
determine its state in the next step. In contrast, in a flocking ECA and to two-dimensional eight-neighbor outer-totalistic
“boids” simulation, which is an artificial life program CA including Conway’s Game of Life. With the additional
developed by Reynolds (Reynolds [8], and Banks, Vincent, radius, some sequences of the extended ECA change
and Anyakoha [9]), each boid obtains the motion complexity between periodic and chaotic patterns. In the
information of other boids within its perception area and sequence of the extended Game of Life, there is a positive
using a simple algorithm, alters its own motion according to correlation between the presence of the additional radius
an analysis of this information. Boids easily organize and the average convergence speed to a rest state; for
themselves into a large, orderly group and move as a single another sample, there is a negative correlation. Some
organism without a central commander, i.e., their interesting pattern formations are also found in
information processing leads to a collective control of heterogeneous models; that is, their grids are composed of
group motion. If a framework similar to that of “boids” cells that follow different extended rules over a given
were to be introduced into CA, we would be able to discuss sequence.
2 EXTENSION OF CA (ii) In each step, a cell determines its own state in the next
step by estimating the states of the cells within its
In order to expand the perception area of a cell, it
perception area in the next step, using the base rule
should be separated from the neighborhood determined by
recursively.
the CA rule. In case of boids, each boid acquires
(iii) In the process of estimation, the same algorithm of
information regarding the positions and velocities of boids
recursive estimation is assumed to be used by all cells
within its perception area and determines its own
within the perception area. Within the perception area,
movement so as to follow the representative values of the
each cell is assumed to have a perception area that is as
neighbors. A similar scenario can be written in CA: in
large as possible.
applying the CA rule, each cell acquires the states of cells
(iv) In cases where the assumed perception area of a cell is
within its perception area and considers virtual cells with
smaller than the neighborhood of the base rule, the base
representative values, e.g., average values of this
rule is not applicable and the state of the cell in the next
information, to be its neighbors. In the boids case, the
step is assumed to remain equal to the current state.
approach of applying the update process to the
representative values controls fluctuation and leads to a
In the following, we assume that the rule neighborhood
group formation; in extended CA, by contrast, the result of
and perception area are both isotropic and can be
this scenario is expected to simply resemble a coarse parametrized by their respective radii r and R. Their
graining of the grid. Because no notable results have been containment relationship is expressed by � ≥ �. Here, we
obtained so far using this approach, further arguments will restrict our discussion to the simplest one-dimensional
not be provided for this scenario. binary CA with � = 1, called ECA. The state of the i-th
We then try to explore a model with an expanded cell at time t and an ECA rule function are denoted by ��
(�)

perception area that includes the rule neighborhood. The and f, respectively. The time evolution of the state is
original CA rule is referred to as the “base rule.” The target expressed by
model must function without introducing any other rules (�+1) (�) (�) (�)
�� = �(��−1 , �� , ��+1 ). (1)
and must be able to treat the size of the perception area as a
In the REN framework, the above equation changes to
parameter expressing differences between individual cells. (�+1) (�+1) (�) (�+1)
��,� = �( ��−1,�−1 , �� , ��−1,�+1 ), (2)
In other words, we take the standpoints that pattern
(�+1)
formations can be discussed on the basis of a possible where ��,� is an estimated state of the i-th cell with
(�+1)
single architecture and that some complexity of pattern radius R at t+1 and ��−1,�±1 indicate the estimated states
formation can emerge from differences between individual of the neighbors at t+1 with an estimated radius R-1; the
elements. value of the neighbors’ radius stems from assumption (iii)
To illustrate the basic concept of separation of the because R-1 is the maximum value of the perception area
perception area from the rule neighborhood, we consider for neighbors within the perception area of the i-th cell.
(�+1) (�+1)
our decision-making as to what each cell is to do in the next Note that ��,� is equal to the actual state �� , but
step. This action will be accompanied by a reasoning (�+1)
��−1,�±1 are not necessarily equal to their respective actual
process, i.e., the action will be decided through prediction (�+1)
states ��±1 because the neighbors’ true radii are not
of neighbors’ actions from current information. One of the
� − 1 but R. Subsequently, assumption (iii) leads to the
rules of boids— “Alignment,” which dictates that each boid
following recursive expressions of estimated states of the
follows the average speed of the boids within its perception
neighbors:
area— contains a reasoning process. Here, we propose an (�+1) (�+1) (�) (�+1)
��−�,�−� = ����−�−1,�−�−1 , ��−� , ��−�−1,�−�+1 �,
algorithm of REN, in which the base CA rule is used (3)
(�+1) (�+1) (�) (�+1)
recursively to estimate the neighbors’ states in the next step ��−�,�+� = ����−�−1,�+�−1 , ��+� , ��−�−1,�+�+1 �,
until the state of the target cell is subsequently determined. where � = 1,2, … , � − 1. Because � = � implies that none
The following assumptions will make the definition of of the neighbors’ perception areas are estimated,
the extended CA clear: assumption (iv) gives the following conditions:
(�+1) (�) (�+1) (�)
(i) Each cell has a perception area in addition to the �0,�±� = ��±� , �0,�±�∓2 = ��±�∓2 . (4)
neighborhood defined by the base CA rule. The states of As the first step of a concrete demonstration, let us
all cells within the area are perceived in each step. consider the case � = � = 1. Eqs. (2) and (4) give
(�+1) (�+1) (�) (�+1)
�� = �( �0,�−1 , �� , �0,�+1 )
 (�+1) (�)
and �0,�±1 = ��±1 . Accordingly, the extended ECA with Among the sequences generated from independent ECA
� = 1 is identical to the base ECA (eq. (1)). This rules, eight are based on class I rules and all of the rules
discussion is not restricted to ECA; all extended CAs with contained in these sequences also belong to class I. In
� = � are identical to their base CA. contrast, various pattern formations can be found in
We next discuss the case � = 2, which corresponds to a sequences based on class II rules. The sequence [#134]
5-neighbor rule. Eq. (2) gives shows changes between periodic and chaotic patterns
(�+1) (�+1) (�) (�+1)
�� = �(�1,�−1 , �� , �1,�+1 ), depending on the index R (Fig. 1), where the green dots are
live cells and black ones are dead. The patterns originate
and the recursive expressions (3) give
(�+1) (�+1) (�) (�+1) from initial configurations with one live cell. Some
�1,�−1 = ���0,�−2 , ��−1 , �0,� �,
(�+1) (�+1) (�) (�+1) sequences other than [#134] show similar changes.
�1,�+1 = ���0,� , ��+1 , �0,�+2 �,
(�+1) (�) (�+1) (�)
Because from eqs. (4), �0,� = �� and �0,�±2 = ��±2 ,
the extended � = 2 CA is expressed by
(�+1) (�) (�) (�) (�) (�) (�) (�)
�� = � �����−2 , ��−1 , �� �, �� , ���� , ��+1 , ��+2 ��. (5)
R=1 (base) R=2 R=3 R=4
The cases for larger values of R can be derived similarly.
Figure 1 Pattern formations in [#134]
The above discussion indicates that the extended rules
with increasing values of � form a sequence parametrized
by R and originating from the base CA rule. As each
extended rule for R is a (2 × � + 1)-neighbor CA rule, this
extension represents an extrapolation via the REM
R=1 (base) R=2 R=3 R=4
algorithm to CA with increasing neighborhood sizes.
Figure 2 Pattern formations in [#30]

Patterns of sequences based on class III and IV rules

3 PATTERN FORMATIONS
are also attractive. Class III rules are sometimes
A treatment similar to the extension discussed in the exemplified by rule #30, and its sequence [#30] has typical
previous chapter can be applied to the two-dimensional chaotic patterns (Fig. 2). Some sequences show periodic
outer-totalistic CA, including Conway’s Game of Life changes between periodic and chaotic patterns depending
(called Life-like CA). Here, some examples of pattern
on the odd-even parity of R, e.g., [#22] (Fig. 3) and [#110]
formations in extended ECA and Life-like CA are presented.
(Fig. 4). In these cases, no simple correlations have been
3.1 Extended ECA found between fluctuation control and the radius R, even
ECA is the simplest nontrivial CA with � = 1; its when the amount of information each cell acquires
23 = 8 different neighborhood configurations result in increases monotonically with R.
28 = 256 possible rules. We follow a standard naming
convention invented by Wolfram [4, 7], which gives each
rule in ECA a number from #0 to #255. The equivalency of
the CA rules under mirror and complement transformations
reduces the number of independent rules to 88 (Li and R=1 (base) R=2 R=3 R=4
Figure 3 Pattern formations in [#22]
Packard [10] and Kayama [11]).
A sequence of extended rules with index R is
represented by a code in which the base rule is enclosed by
square brackets, e.g., [#110]. When each rule included in
the sequence is identified, the rule code is shown as the
base rule code followed by a letter “R” and its value. The R=1 (base) R=2 R=3 R=4
Figure 4 Pattern formations in [#110]
sequence is represented by
[#110] = {#110R1, #110R2, #110R3, … }, 3.2 Extended Life-like CA
where #110R1 is identical with the base rule #110. In the In the descriptions below, all two-dimensional Life-like
simulations used in this subsection, we set the maximum CA rules are specified in the Golly/RLE format
value of R to 20. (Adamatzky (Ed.) [12], and Eppstein [13]). Conway’s
Game of Life is denoted by B3S23 in this notation, where In contrast, [B23S234] has a rest state only in
“B” stands for “birth” and “S” stands for “survival.” B23S234R1 and random states in all others (Fig. 8).
Following the previous subsection, a sequence of extended Randomness gradually increases with R.
rules is denoted by the base rule code in square brackets,
e.g., [B3S23].
In Conway’s Game of Life, one of the most famous CA,
many complex patterns and activities can emerge (Callahan
[14], Flammenkamp [15]). After a long transient process, a
randomly generated initial configuration transfers to a rest
state that can include a variety of patterns: still lifes (e.g.,
blocks, beehives, or ships) and oscillators (e.g., blinkers, R=1 (base) R=2
toads, or beacons). Isolated still lifes are also still lifes in
any extended rule in the sequence [B3S23] based on the
(�+1)
Game of Life because the estimated states ��,� defined

R=3 R=4
Figure 8 Pattern formations in [B23S234]
Thus far, we have discussed homogeneous CA, that is,
R=1 (GoL) R=2 all cells following the same CA rule. If we recognize the
extra radius R as an index of the amount of information
each cell can acquire, heterogeneous CA composed of cells
having different values of R becomes meaningful. Figs. 9-a
and -b represent mixing between B3S23R1 and B3S23R2
cells and between B23S234R3 and B23S234R4 cells,
respectively. The mixing ratio changes linearly from 1:0
(left-hand side) to 0:1 (right-hand side). Although B3S23R1
R=3 R=4 and B3S23R2 have rest states as shown in Fig. 5, Fig. 9-a
Figure 5 Rest states of [B3S23] shows that their intermediate mixing area is unstable. In
in Chapter 2 are all equal contrast, Fig. 9-b shows the emergence of a rest state in the
(�+1)
to the actual states �� . intermediate area. Nevertheless, B23S234R3 and
Figure 5 shows rest states B23S234R4 have no rest states (Fig. 8).
of [B3S23], where colored
dots represent live cells.
The average transient time
from pseudo-randomly Figure 6 Transient time - R
graph of [B3S23]
generated initial
configurations to rest states decreases (Fig. 6 is on a
double-logarithmic scale), which means that there is a
positive correlation between the radius R and the average
a. B3S23R1↔R2 b. B23S234R3↔R4
convergence speed. The long transient time at � = 6 is the
Figure 9 Mixings of two types of cells
only exception owing to a
A mixing of B4S1234R1 and B4S1234R2 cells is also
glider (Fig. 7-b travels
interesting. Fig. 10 shows a complex pattern change; there
diagonally). Additionally,
an amusing glider can be is an area of islands between two walls and a random state
found in B3S23R2 (Fig. 7- a. R=2 b. R=6 at the right-hand edge. The left-hand edge wall is a rest
a travels vertically). Figure 7 Gliders in [B3S23] state of B4S1234R1 and the right-hand edge is a random
state of B4S1234R2. Their mixing ratio is the same as in
the case of Fig. 9, but the Academic, New York
initial probability of live [4] Wolfram S. (1983), Statistical mechanics of cellular
automata. Reviews of Modern Physics, vol. 55, pp. 601-644
cells has been set to 0.2. [5] Wolfram S. (1984), Universality and complexity in
Some analytical discussion cellular automata. Physica D, vol. 10, pp. 1-35
to better understand the [6] Wolfram S. (1986), Theory and Applications of
above results should be Cellular Automata. World Scientific, Singapore
[7] Wolfram S. (2002), A New Kind of Science.
presented in future work.
Wolfram Media, Inc.
Figure 10 B4S1234R1↔R2 [8] Reynolds C. W. (1987), Flocks, herds and schools: A
distributed behavioral model. ACM Siggraph Computer
Graphics, vol. 21 (4), pp. 25-34
4 CONCLUSIONS [9] Banks A., Vincent J., and Anyakoha C. (2007), A
In this article, we tried to extend the standard CA to a review of particle swarm optimization. Part i: background
model that can be applied to studying the relationship and development. Natural Computing, vol. 6 (4), pp. 467-
484
between information processing and pattern formation in
[10] Li W., Packard N. (1990), The Structure of the
collective systems with a minimal introduction of extra Elementary Cellular Automata Rule Space, Complex
rules or technical contrivances. The REN algorithm, which Systems, vol. 4, pp. 281–297
arose from the idea of self-similarity, made it possible to [11] Kayama Y. (2011), Network Representation of
separate the perception area from the rule neighborhood Cellular Automata. In 2011 IEEE Symposium on Artificial
and to formalize an extension of the rule. There may be Life (IEEE ALIFE 2011) at SSCI 2011, pp. 194-202
other algorithms besides REN to estimate the states of [12] Adamatzky A. (Ed.) (2010), Game of life cellular
automata. London, Springer
neighbors, and the assessment of possible candidates is a [13] Eppstein D. (2010), Growth and decay in Life-like
future subject of investigation. In the applications discussed cellular automata. In Adamatzky A. (Ed.), Game of Life
in this paper, the extended ECA sequences showed a variety Cellular Automata, Springer, pp. 71–98
of patterns that changed with the size of the perception area [14] Callahan P. (1995), Patterns, Programs, and Links
of each element. The sequences of extended Life-like CA, for Conway’s Game of Life. http://www.radicaleye.com/
[B3S23] and [B23S234], represent contrasting dependences lifepage/. Retrieved at February 1, 2011
[15] Flammenkamp A. (1998), Achim’s Game of Life.
on the size of the perception area. It will be crucial to
http://wwwhomes.uni-bielefeld.de/achim/gol.html
understand these differing correlations in order to construct Retrieved at December 12, 2011
an applicable model for various simulations of complex [16] Sayama H. (2007), Decentralized control and
systems and other fields. interactive design methods for large-scale heterogeneous
Heterogeneous models of the extended CA show further self-organizing swarms. Advances in Artificial Life, vol.
possibility. Even if the homogeneous models have rest 15(1), pp. 105-114
states, a heterogeneous model of cells belonging to the [17] Sayama H. (2009), Swarm chemistry. Artificial Life,
vol. 15(1), pp. 105-114
various homogeneous models within a given extended
[18] Sayama H. (2010), Robust morphogenesis of robotic
sequence may have unstable patterns, and vice versa. Such swarms. Computational Intelligence Magazine, IEEE, vol.
phenomena appear to act like a mixture of two different 5(3), pp. 43-49
materials changing its state through a chemical reaction.
Just as the boids theory has been adapted to “Swarm
Chemistry” by introducing interactions between its
elements and an evolutionary algorithm (Sayama [16-18]),
the extended CA would be expected to evolve into “CA
Chemistry.”

REFERENCES
[1] Neumann J. von (1966), The theory of self-
reproducing automata. In: Burks A. W. (Ed.), Essays on
Cellular Automata, University of Illinois Press
[2] Gardner M. (1970), Mathematical games. Scientific
American, vol. 223, pp. 102-123
[3] Berlekamp E. R., Conway J. H., and Guy R. K.
(1982), Winning Ways for Your Mathematical Plays.

View publication stats