Measuring Behavioral Similarity of - IA de Investigación especializada en el MIT

Measuring Behavioral Similarity of
Cellular Automata

Peter D. Turney*
Ronin Institute

peter.turney@ronininstitute.org

Abstract Conwayʼs Game of Life is the best-known cellular
automaton. It is a classic model of emergence and self-organization, él
is Turing-complete, and it can simulate a universal constructor. El
Game of Life belongs to the set of semi-totalistic cellular automata, a
family with 262,144 miembros. Many of these automata may deserve
as much attention as the Game of Life, if not more. The challenge we
address here is to provide a structure for organizing this large family,
to make it easier to find interesting automata, and to understand the
relations between automata. Packard and Wolfram (1985) divided the
family into four classes, based on the observed behaviors of the rules.
Eppstein (2010) proposed an alternative four-class system, based
on the forms of the rules. Instead of a class-based organization, nosotros
propose a continuous high-dimensional vector space, donde cada
automaton is represented by a point in the space. The distance
between two automata in this space corresponds to the differences in
their behavioral characteristics. Nearest neighbors in the space have
similar behaviors. This space should make it easier for researchers to
see the structure of the family of semi-totalistic rules and to find the
hidden gems in the family.

Palabras clave
Cellular automata, semi-totalistic automata,
outer-totalistic automata, Conwayʼs Game
of Life, similarity of cellular automata,
behavior of cellular automata

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
a
r
t
yo
/

a
r
t
i
C
mi
–
pag
d

F
/

2
7
1
6
2
2
0
2
0
4
1
2
a
r
t
yo

_
a
_
0
0
3
3
7
pag
d

b
y
gramo
tu
mi
s
t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

1 Introducción

The Game of Life (GoL) is a solitaire game invented by John Conway and introduced to the world by
Martin Gardner (1970) in Scientific American. It is played on a potentially infinite, two-dimensional grid
of square cells. Each cell is either dead (estado 0) or alive (estado 1). The state of a cell changes with time,
based on the states of its eight nearest neighbors (called the Moore neighborhood). Time passes in a
series of discrete intervals. At time t = 0, the player of the game chooses the initial states of the
grid. The initial states form a seed pattern that determines the course of the game. The states at time t
uniquely determine the states at time t + 1. With each increment of t, all of the cells are updated. Como
the game runs, patterns grow and decay, resembling living organisms.

The rule for changing states in GoL can be compactly represented as B3/S23, where B means
“born” and S means “survives.” A cell is born (it switches from state 0 to state 1) when exactly three
of its eight nearest neighbors are alive (in state 1). A cell survives (remains in state 1) when it has either
two or three living neighbors. De lo contrario, a cell dies (it switches to state 0 or remains in state 0).

GoL is a cellular automaton, a discrete, abstract computational system. It is the best-known member
of the family of cellular automata. It is popular as a model of emergence and self-organization

* Autor correspondiente.

Artificial Life 27: 62–71 (2021) https://doi.org/10.1162/artl_a_00337

Publicado bajo una atribución Creative Commons
4.0 Internacional (CC POR 4.0) licencia.

PAG. D. Turney

Measuring Behavioral Similarity of Cellular Automata

(Bak et al., 1989), it is Turing-complete (Rendell, 2016), and it is a universal constructor (Life-
Wiki, 2021b).

GoL is a member of the family of semi-totalistic cellular automata (also called “outer-totalistic”). El
rules for this family have the general form Bx/Sy, where x and y are generated by deleting digits from
the string 012345678, including deleting no digits or deleting all digits (Eppstein, 2010). Since there
are nine digits available for B and nine digits available for S, hay 2 to the power of 18 (262,144)
possible semi-totalistic rules.

Packard and Wolfram (1985) introduced a four-class system for characterizing two-dimensional
cellular automata. Sin embargo, as Eppstein (2010, pag. 72) reports, “The boundary between classes is less
clear-cut and more subjective than one would like, and may for some automata be impossible to
decide.” Eppstein (2010) proposed an alternative four-class system, based on an analysis of the Bx/
Sy rule forms. We will compare Eppsteinʼs four-class system with our approach in section 3.

In this article, we introduce a continuous high-dimensional vector space, where the statistical behavior
of an automaton corresponds to a point in the space. For a given semi-totalistic rule, such as B3/S23, nosotros
create an initial random soup of living cells and then run the game. We then randomly sample cells in the
game to estimate the probabilities of the state transitions, which depend on both the rules of the game
and the particular patterns of neighbors that tend to arise in the game. The behavior is then represented as
a vector of the estimated probabilities of each possible state transition.

With the probability vectors for all 262,144 semi-totalistic cellular automata, we can measure the
behavioral similarity of any two automata by any suitable distance measure. In this article, tenemos
chosen to use Euclidean distance, where low distance corresponds to high behavioral similarity. Este
continuous high-dimensional vector space enables many ways of searching for interesting automata
and finding relations among automata, as we show in Table 1.

The source code for calculating the high-dimensional vectors is available for downloading, a lo largo de
with the vectors for all 262,144 possible semi-totalistic rules (Turney, 2021). The source code uses
Python and Golly (Trevorrow et al., 2021). En la sección 2, we describe the problems of strobing and
infinity that arise with rules that contain B0. En la sección 3, we present a 36-dimensional space for
representing the behavior of automata, ignoring the issues of strobing and infinity, in order to sim-
plify the presentation. En la sección 4, we address the problems of strobing and infinity, using a 72-
espacio dimensional. We conclude in section 5.

2 The Problems of Strobing and Infinity

In a typical game, we begin at time t = 0 with a potentially infinite grid and a finite number of live cells.
If the given rule contains B0, all dead cells with no neighbors will come alive at time t = 1. This means
there will be an infinite number of live cells at t = 1. If the rule does not contain S8, at time t = 2, un
infinite number of cells will die. This creates an annoying strobing effect, with alternating light and dark
images at odd and even times.

The popular Golly software for cellular automata automatically corrects the problems with strobing
and infinity (Golly, 2021). If a rule contains B0 and S8, then the rule is replaced with an equivalent rule
that avoids the problem of an infinite number of live cells. If a rule contains B0 but not S8, then the rule is
replaced with two rules, one for even times and one for odd times, to avoid the problem of strobing. Nosotros
do not have the space here to explain how Golly adjusts the rules, but this information is available on the
Golly website (Golly, 2021) and our Python code includes the required adjustments (Turney, 2021).

3 The 36-Dimensional Space for Semi-Totalistic Automata

As an example of the 36-dimensional space for semi-totalistic automata, Mesa 2 shows two vectors
for the Game of Life, B3/S23. The first is a Boolean vector that expresses the rule B3/S23 with four
9-dimensional vectors, Born (B), Survive (S), Unborn (Ud.), and Die (D). The rule tells us which state
transitions are allowed (1) and which transitions are forbidden (0). We can see that the Boolean vector

Artificial Life Volume 27, Número 1

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
a
r
t
yo
/

a
r
t
i
C
mi
–
pag
d

F
/

2
7
1
6
2
2
0
2
0
4
1
2
a
r
t
yo

_
a
_
0
0
3
3
7
pag
d

b
y
gramo
tu
mi
s
t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

PAG. D. Turney

Measuring Behavioral Similarity of Cellular Automata

Mesa 1. This table lists potential applications for a continuous high-dimensional vector space representation of the
characteristics of cellular automata.

Applications for vectors

Find more like this

Examples

Given an automaton that is interesting, find similar automata that
might also be interesting, by sorting the automata in order of
increasing distance from the given automaton.

Finding hybrids

Given two different automata, find a third automaton that is half

way between them.

Finding models for phenomena

Given some natural phenomenon that looks like it might be

something a cellular automaton could model, try to make a
behavioral vector for it, then use the behavioral vector to find
the best automaton for modeling the phenomenon.

Unsupervised clustering

Use a similarity-based clustering algorithm to cluster automata by

vector similarity.

Supervised clustering

Use vector similarity for supervised clustering, given some manually

identified examples of each desired cluster.

Finding opposites

Given an automaton, find the automaton that is least similar to the

given rule; the maximally distant automaton.

Finding idiosyncrasy

Finding paradigmatic examples

For each automaton, find its nearest neighbor, then make note of
how different the two automata are; output the automaton that
is least like its nearest neighbor (most unique).

Given a group of automata that belong to the same cluster, find the
automaton that is the centroid or average of the cluster, to serve
as a paradigmatic example of the cluster.

Projection into subspaces

To understand the high-dimensional vector space better, project it

into lower dimensional subspaces, such as two-dimensional
subspaces, which are easier to visualize.

for U is the inverse of the vector for B and D is the inverse of S. A limitation of measuring distance
with Boolean vectors is that any two rules that differ by the insertion or deletion of N numbers are
exactly the same distance apart. The Boolean vector space is not capable of making fine distinctions
between rules.

The second vector is a real-valued vector of probabilities, such that the sum of the probabilities is
1. This vector tells us the estimated probability of each allowed state transition, based on many ob-
servations of the Game of Life. State transitions that are forbidden have a probability of zero. Mesa 2
shows that a cell with two neighbors is more likely to survive than a cell with three neighbors (prob-
capacidad 0.0414 for two and probability 0.0327 for three). This implies that a line of live cells is slightly
more likely to continue than to branch out. The probability vectors give us qualitative behavioral
information that is not available in the Boolean vectors.

The probabilities in Table 2 were generated by repeatedly making random soups and running
them to see how they evolve. Mesa 3 shows the parameter settings we used for these experiments.
Taking a sample consists of randomly selecting a cell (alive or dead) and inspecting its state and the
state of its neighbors at time t and then inspecting its new state at time t + 1, to see what transition
took place.

Artificial Life Volume 27, Número 1

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
a
r
t
yo
/

a
r
t
i
C
mi
–
pag
d

F
/

2
7
1
6
2
2
0
2
0
4
1
2
a
r
t
yo

_
a
_
0
0
3
3
7
pag
d

b
y
gramo
tu
mi
s
t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

PAG. D. Turney

Measuring Behavioral Similarity of Cellular Automata

Mesa 2. Here we see two 36-dimensional vectors for the Game of Life, B3/S23.

Vectors

Boolean

B3/S23

Real

B3/S23

Ud.

Transition
t to t + 1

0 a 1

1 a 1

0 a 0

1 a 0

0 a 1

1 a 1

Number of neighbors

0.0454

0.0414

0.0327

0 a 0

0.5883

0.0963

0.1082

1 a 0

0.0013

0.0149

0.0212

0.0199

0.0037

0.0003

0.0002

0.0160

0.0073

0.0025

0.0004

0.0001

Nota. The Boolean vector expresses exactly the same information as the rule, B3/S23, but more explicitly. The real-valued
probability vector gives a more detailed picture, showing how the rule behaves in practice.

The initial random soup is contained in a 16 × 16 square of cells (initial_size), following the example
of Catagolue (LifeWiki, 2021a), the most popular software for exploring random soups. Catagolue is
the latest in a series of tools for exploring soups, and it is widely used by the GoL community. Catagolue
has been running continuously since 2015, and “at least 18,928,504,510,982 soups have been investi-
gated by the censusʼs participants, yielding a total of at least 413,493,174,300,923 objects of 159,347
distinct types” (LifeWiki, 2021a, para. 2).

The soup is generated in two steps. Primero, we randomly select a number d using a continuous
uniform distribution between 0 y 1 (density_range). This d gives us the desired density of live cells
para el 16 × 16 square. Segundo, we iterate through the cells in the square, randomly assigning state 1
with probability d and state 0 with probability 1 − d. We then run the soup for 50 steps, to see how it
develops (num_steps). We then take 50 samples of the state transitions (num_samples). This process
is repeated 1,000 veces (num_trials), each time with a different density d. Desde 50,000 state tran-
sitions (1,000 soups with 50 samples per soup), we estimate the state transition probabilities for the
real-valued probability vectors.

Después 50 steps (num_steps), the random soup may not have settled into a stable configuration, pero
we believe that some degree of instability is natural, so it is not necessary to run the game until it is

Mesa 3. This table shows the parameter settings we used for the experiments that estimated the probabilities in the
real-valued vectors.

Parameter

density_range

initial_size

num_steps

num_samples

num_trials

Value

[0.0, 1.0]

Descripción

density range for initial random soup matrix

width and height for initial random soup matrix

number of steps for a run of the cellular automaton

number of samples to collect from each run

1,000

number of trials (carreras) to evaluate for each rule

Artificial Life Volume 27, Número 1

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
a
r
t
yo
/

a
r
t
i
C
mi
–
pag
d

F
/

2
7
1
6
2
2
0
2
0
4
1
2
a
r
t
yo

_
a
_
0
0
3
3
7
pag
d

b
y
gramo
tu
mi
s
t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

PAG. D. Turney

Measuring Behavioral Similarity of Cellular Automata

completely stable. It is also advantageous to keep the number of steps relatively small, due to the
time required for computation, since we are dealing with 262,144,000 soups (num_trials × 218).

Eppstein (2010) was primarily interested in engineered patterns, designed with a purpose. Allá-
delantero, he chose to avoid B0 rules in his analysis of semi-totalistic cellular automata, arguing that B0
rules are not conducive to engineering. Without B0 rules, strobing and infinity are not an issue, entonces
we can compare Eppsteinʼs four-class system with our 36-dimensional space.

A rule is defined as fertile if it has a finite pattern that eventually escapes any bounding box
Eppstein (2010). Eppstein defines the following four classes: (1) If a rule includes B1, it is fertile,
given a single live cell as a seed pattern. (2) De lo contrario, if a rule includes B2, it is fertile, given a 2 × 2
block of live cells as a seed pattern. (3) De lo contrario, if a rule does not include B1, B2, or B3, it is not
fertile, because the dead cells outside of the bounding box can have at most three live neighbors. (4)
De lo contrario, the rule must begin with B3. Some of the B3 rules are fertile and some are not. En algunos
casos, it can be difficult to determine whether B3 rules are fertile or infertile.

Mesa 4 shows that, if two rules are near neighbors in our 36-dimensional space, then they are
almost certainly in the same Eppstein class. This mutual agreement between Eppsteinʼs classes and
our 36-dimensional space lends support to both approaches.

To generate Table 4, we randomly chose 10,000 target rules and, for each target rule, we randomly
chose another 10,000 candidate rules, from which we picked out the candidate that was nearest (pero
not identical) to the given target rule. For each target-neighbor pair, we then checked their Eppstein
classes. The table shows the percentages for each possible target−neighbor pair of Eppsteinʼs classes.
The numbers on the diagonal in Table 4 tend to decrease as the class numbers increase (50.05,
25.02, 11.26, 12.11). This is because the four classes are defined like a set of four successive sieves,
so each subsequent sieve tends to catch fewer cases than its predecessor.

4 The 72-Dimensional Space for Semi-Totalistic Automata

As an example of the 72-dimensional space for semi-totalistic automata, Mesa 5 shows the vectors
for the rule B03/S23. This rule causes strobing, because it contains B0 and not S8 (mira la sección 2), entonces
we replace it with two 36-dimensional Boolean vectors, one for even values of t (B1245678/
S0145678) and one for odd values of t (B56/S58) (Golly, 2021). To express these anti-strobing rules
in a vector space, we need to join these two 36-dimensional Boolean vectors, creating a 72-dimensional
Boolean vector. The bottom eight rows of the table show the corresponding 72-dimensional real-
valued vector of probabilities. The probabilities in the first 36 dimensions sum to 1, and the prob-
abilities in the second 36 dimensions also sum to 1, so the whole vector sums to 2.

Rules without strobing do not require 72 dimensions, but we can easily expand them to 72-
dimensions by repeating the 36-dimensional vector. The 72-dimensional vector has an even part

Mesa 4. This table shows the relation between Eppsteinʼs (2010) four-class system and our 36-dimensional vector space.

Clase 1

Clase 2

Clase 3

Clase 4

Clase 1

50.05

0.00

0.78

0.09

Clase 2

0.00

25.02

0.01

0.07

Total of classes

50.92

25.10

Clase 3

Clase 4

Total of classes

0.04

0.00

11.26

0.21

11.51

0.00

0.01

0.35

12.11

12.47

50.09

25.03

12.40

12.48

100.00

Nota. All numbers in the table are percentages. The numbers on the diagonal are highlighted in bold. The table shows
that near neighbors in the 36-dimensional vector space tend to belong to the same class.

Artificial Life Volume 27, Número 1

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
a
r
t
yo
/

a
r
t
i
C
mi
–
pag
d

F
/

2
7
1
6
2
2
0
2
0
4
1
2
a
r
t
yo

_
a
_
0
0
3
3
7
pag
d

b
y
gramo
tu
mi
s
t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

PAG. D. Turney

Measuring Behavioral Similarity of Cellular Automata

Mesa 5. Here we have vectors for the strobing rule B03/S23.

Vectors

Boolean B03/S23

Boolean

B1245678/S0145678
even t

Boolean B56/S58 odd t

Real

B1245678/S0145678
even t

Real B56/S58 odd t

Ud.

Transition

t to t + 1

Number of neighbors

0 a 1

1 a 1

0 a 0

1 a 0

0 a 1

1 a 1

0 a 0

1 a 0

0 a 1

1 a 1

0 a 0

1 a 0

0 a 1

0.1030 0.1332 0

0.0892 0.0489 0.0182 0.0033 0.0004

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
a
r
t
yo
/

a
r
t
i
C
mi
–
pag
d

F
/

2
7
1
6
2
2
0
2
0
4
1
2
a
r
t
yo

1 a 1

0.0090 0.0371 0

0.0628 0.0311 0.0125 0.0040 0.0147

0 a 0

0.1562 0

0.1277 0

1 a 0

0 a 1

1 a 1

0.0703 0.0785 0

0.0756 0.0622 0

0.1309 0

0.0408

0 a 0

0.1049 0.0189 0.0416 0.0558 0.0652 0

0.0303 0.0062

1 a 0

0.0001 0.0033 0.0250 0.0690 0.0999 0

0.1045 0.0656 0

_
a
_
0
0
3
3
7
pag
d

b
y
gramo
tu
mi
s
t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Nota. Primero, we have the 36-dimensional Boolean vector for B03/S23. Segundo, we have two 36-dimensional Boolean vectors,
one for even t and one for odd t, which combine to create a 72-dimensional Boolean vector that does not strobe. Tercero, nosotros
have two 36-dimensional probability vectors, which combine to create a 72-dimensional probability vector.

and an odd part, so it is natural to duplicate the 36-dimensional vector when the same rule is used
for even and odd times. This allows us to compare non-strobing rules (such as B3/S23) with strob-
ing rules (such as B03/S23) in the same 72-dimensional space.

Mesa 6 shows the nearest neighbors of the rule B3/S23 in the 72-dimensional probability space.
There are two cases where Golly modifies rules, in order to prevent strobing and infinity (Golly,

Artificial Life Volume 27, Número 1

PAG. D. Turney

Measuring Behavioral Similarity of Cellular Automata

Mesa 6. This table shows the twenty nearest neighbors of the Game of Life, the target rule B3/S23.

Rango

Regla

Anti-infinity
rule change

Duplicate
normas

Distance from B3/S23

B3/S23—target rule

B0123478/S01234678

B3/S23

B0123478/S1234678

B38/S23

B3/S238

B38/S23

B38/S238

B0123478/S0234678

B37/S23

B378/S23

B37/S23

1 & 2

3 & 5

7 & 9

8 & 10

7 & 9

B0123478/S234678

B378/S23

8 & 10

B37/S238

B378/S238

B3/S237

B3/S2378

13 & 15

B023478/S01234678

B3/S237

13 & 15

B48/S23678

B468/S236

B03478/S01235678

B4/S2367

18 & 34

B478/S238

Real

0.0000

0.0146

0.0269

0.0298

0.0313

0.0413

0.0553

0.0625

0.0664

0.0678

0.0838

0.0890

0.0925

0.0937

0.0949

0.0963

0.0970

0.0972

0.0976

Boolean

0.0000

1.4142

2.0000

1.4142

2.0000

1.4142

2.0000

2.4495

1.4142

2.0000

1.4142

3.4641

3.1623

2.8284

3.1623

3.4641

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
a
r
t
yo
/

a
r
t
i
C
mi
–
pag
d

F
/

2
7
1
6
2
2
0
2
0
4
1
2
a
r
t
yo

_
a
_
0
0
3
3
7
pag
d

b
y
gramo
tu
mi
s
t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

B01468/S034678

B367/S1356

20 & 136

0.0979

Nota. Duplicate rules occur when a rule must be changed to avoid infinity.

2021): (1) A rule containing B0 and S8 is black/white reversed to avoid infinity. (2) A rule containing
B0 but not S8 is split into two new rules to avoid strobing. En mesa 6, caso (1) aplica: Algunos de los
rules are modified to prevent infinity. This modification gives rise to duplicate rules, which give us
an opportunity to see how much noise there is in our probability estimates. If the probability esti-
mates in the real-valued vectors were perfectly accurate, then the duplicate rules would be adjacent
to each other in the table. The duplicates are close together at the top of the list, but they diverge as
we go down the list. We will discuss this divergence after we consider another example.

Artificial Life Volume 27, Número 1

PAG. D. Turney

Measuring Behavioral Similarity of Cellular Automata

Mesa 7 shows the nearest neighbors of the rule B03/S23 in the 72-dimensional probability space.
En mesa 7, caso (2) aplica: All of the rules are modified to prevent strobing. Unlike in Table 6, allá
are no duplicate rules in Table 7.

En mesa 6 and Table 7, the two final columns show the distances from the target rule in real
space and Boolean space. The ranking in column 1 is based on real space alone; the Boolean space is
only included for comparison. There are many ties in the Boolean column, which shows that the real
space is able to make finer distinctions than the Boolean space. We also see that the Boolean dis-
tances yield different rankings from the real-valued distances.

Mesa 7. This table shows the twenty nearest neighbors of the target rule B03/S23 in the 72-dimensional probability
espacio.

Anti-strobing rule change

Distance from B03/S23

Rango

Regla

Even rule

Odd rule

B03/S23—target rule

B1245678/S0145678

B56/S58

B038/S23

B037/S23

B124567/S0145678

B56/S058

B124568/S0145678

B56/S158

B0378/S23

B12456/S0145678

B56/S0158

B037/S023

B124568/S145678

B568/S158

Real

0.0000

0.0215

0.0237

0.0317

0.0365

B0378/S023

B12456/S145678

B568/S0158

0.0452

B03/S023

B1245678/S145678

B568/S58

B038/S023

B124567/S145678

B568/S058

B036/S23

B124578/S0145678

B56/S258

B0368/S23

B12457/S0145678

B56/S0258

0.0468

0.0525

0.0795

0.0816

B03678/S23

B1245/S0145678

B56/S01258

0.0889

B0367/S23

B12458/S0145678

B56/S1258

B038/S236

B124567/S014578

B256/S058

B036/S023

B124578/S145678

B568/S258

B03/S236

B1245678/S014578

B256/S58

0.0890

0.1020

0.1025

0.1042

B0368/S023

B12457/S145678

B568/S0258

0.1045

B0378/S236

B12456/S014578

B256/S0158

0.1094

B03/S0236

B1245678/S14578

B2568/S58

0.1103

B03678/S023

B1245/S145678

B568/S01258

0.1120

B037/S236

B124568/S014578

B256/S158

0.1125

Boolean

0.0000

1.4142

2.0000

2.4495

1.4142

2.0000

1.4142

2.0000

2.4495

2.0000

1.4142

2.4495

2.0000

2.8284

2.0000

Artificial Life Volume 27, Número 1

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
a
r
t
yo
/

a
r
t
i
C
mi
–
pag
d

F
/

2
7
1
6
2
2
0
2
0
4
1
2
a
r
t
yo

_
a
_
0
0
3
3
7
pag
d

b
y
gramo
tu
mi
s
t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

PAG. D. Turney

Measuring Behavioral Similarity of Cellular Automata

Cifra 1. Distance from target rule as a function of rank. This graph shows how the distance of a given rule from a target
rule varies as a function of the rank of the given rule.

Cifra 1 shows the relation between rank and distance for the 200 most highly ranked rules, con
one curve for the target rule B3/S23 and a second curve for the target rule B03/S23. The curve for
B3/S23 flattens out at about rank 15, and we can see this flattening also in Table 6, in the column of
real distances. This flattening explains why the duplicate rules in Table 6 are near each other until we
pass rank 15, when the duplicate rules become distant from each other. When the curve is flat, a
small amount of noise in the estimated probability can cause a large amount of variation in the
estimated rank. Sin embargo, the curve for B03/S23 does not flatten out as quickly as the curve for
B3/S23. Cifra 1 suggests that the rankings for B03/S23 will be reliable at least up to rank 40.

A potential problem with strobing rules is that it seems it should not matter whether the simu-
lation begins at time t = 0 or t = 1, but changing the starting time will have the effect of swapping
the order of the two 36-dimensional parts of the 72-dimensional vector. Sin embargo, this problem is
not likely to arise, since there is no reason to vary the starting time.

5 Conclusión

This article offers a new method for examining the behaviors of the family of semi-totalistic cellular
automata and for investigating the relations among the members of the family. Given that there are
262,144 semi-totalistic rules, researchers in the field of cellular automata have a large space to ex-
plore. In the spirit of Packard and Wolfram (1985) and Eppstein (2010), we hope that our method
for measuring behavioral similarity of cellular automata will give researchers useful new ways of
visita, organizing, and understanding the semi-totalistic family.

The general idea of this paper is that the behavior of a deterministic cellular automaton can be
captured to some extent by a real-valued probability vector, which expresses the likelihood of var-
ious state transitions, given a random soup as a starting point. This idea should be applicable to many
other classes of cellular automata, including 1D, 2D, 3D, and higher-dimensional automata, y
automata with more than two states.

Expresiones de gratitud
Thanks to the reviewers of Artificial Life for their very helpful advice.

Artificial Life Volume 27, Número 1

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
a
r
t
yo
/

a
r
t
i
C
mi
–
pag
d

F
/

2
7
1
6
2
2
0
2
0
4
1
2
a
r
t
yo

_
a
_
0
0
3
3
7
pag
d

b
y
gramo
tu
mi
s
t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

PAG. D. Turney

Measuring Behavioral Similarity of Cellular Automata

Referencias
Bak, PAG., Chen, K., & Creutz, METRO. (1989). Self-organized criticality in the ‘Game of Life’. Naturaleza, 342(6251), 780−782.

https://doi.org/10.1038/342780a0

Eppstein, D. (2010). Growth and decay in life-like cellular automata. In A. Adamatzky (Ed.), Game of Life

Cellular Automata (páginas. 71−97). Saltador. https://doi.org/10.1007/978-1-84996-217-9_6

jardinero, METRO. (1970). Mathematical games: The fantastic combinations of John Conwayʼs new solitaire game

“Life.” Scientific American, 223(4), 120−123. https://doi.org/10.1038/scientificamerican1070-120

Golly. (2021, Marzo 22). QuickLife: B0 emulation. SourceForge: https://golly.sourceforge.net/Help

/Algorithms/QuickLife.html#b0emulation

LifeWiki. (2021a, Marzo 22). Catagolue. LifeWiki. https://www.conwaylife.com/wiki/Catagolue

LifeWiki. (2021b, Marzo 22). Universal constructor. https://www.conwaylife.com/wiki/Universal_constructor

Packard, norte. h., & Wolfram, S. (1985). Two-dimensional cellular automata. Journal of Statistical Physics, 38(5/6),

901−946. https://doi.org/10.1007/BF01010423

Rendell, PAG. (2016). Turing machine universality of the Game of Life. Saltador. https://doi.org/10.1007/978-3-319

-19842-2

Trevorrow, A., Rokicki, T., Hutton, T., Rowett, C., Hutton, T., verde, D., Summers, J., Verver, METRO., Munafo, r.,

Bostick, B., & Sotavento, D. (2021, Marzo 22). Golly. SourceForge: https://golly.sourceforge.net/

Turney, PAG. D. (2021, Marzo 22). Similarity of cellular automata: Source code, GitHub, https://github.com

/pdturney/similarity-of-cellular-automata

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu
a
r
t
yo
/

a
r
t
i
C
mi
–
pag
d

F
/

2
7
1
6
2
2
0
2
0
4
1
2
a
r
t
yo

_
a
_
0
0
3
3
7
pag
d

b
y
gramo
tu
mi
s
t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Artificial Life Volume 27, Número 1

71
Descargar PDF