Identifying Patterns from
One-Rule-Firing Cellular Automata
Jae Kyun Shin*
Yeungnam University
关键词
Cellular automata, one-rule firing, 花
图案, 复杂
Abstract A new firing scheme for cellular automata in which only one
rule is fired at a time produces myriad patterns. In addition to geometric
图案, natural patterns such as flowers and snow crystals were also
生成的. This study proposes an efficient method identifying the
patterns using a minimal number of digits. Complexity of the generated
patterns is discussed in terms of the shapes and colors of the patterns.
1 介绍
Since its introduction by von Neumann [11], the cellular automaton (CA) has been applied to various
fields, including physics and computer science. Wolframʼs work on complexity classification [17] 和
Conwayʼs game of Life [1] are examples of famous works involving the CA. In the present study,
the CA is considered a generic mechanism for a class of symmetric patterns in the 2D plane. 尤其,
a new rule-firing scheme that causes the emergence of diverse patterns, which are unprecedented in
previous CA literature, is proposed.
In most CAs, the rules are applied synchronously on all cells in the system. 然而, several asyn-
chronous updating schemes have been reported in previous literature.
The simplest such scheme is the one-cell updating scheme, in which only one cell is updated at a time
[7]. This is comparable to blockwise asynchronous updating in which the whole system is divided into
several blocks and different firing schemes are applied from block to block, such that inter-block up-
dating is asynchronous and intra-block updating is synchronous [15, 16]. Because updating within the
block is synchronous, blockwise updating could not be considered genuinely asynchronous.
The probabilistic CA also involves a kind of asynchronous updating, in which the rules fire with some
probability [8]. 在某些情况下, asynchronous updating generated natural patterns, such as the color
patterns of mollusks. 因此, a proposal followed that asynchrony is intrinsic to living systems
[6]. 然而, natural patterns resulting from such CAs are limited to a few types. One such type is
the snow crystal pattern [2, 9, 12]. Packardʼs snowflake is the simplest pattern within the snow crystal
类别 [9], for which an integer-valued hexagonal cell is used. Real-valued CAs, also known as fuzzy
CAs, demonstrated the power of the CA as a means to generate more diverse and complex snow crystal
图案 [2, 12]. 然而, the patterns were limited to snow crystals.
The present article suggests a method of partial firing of CA rules on 2D hexagonal cells. The firing
scheme is similar to that of the blockwise asynchronous CA. The key difference is how the updating block
is defined. In the present study, the block is defined in terms of the neighborhood conditions rather
than the spatial location of the cells. 此外, an efficient method of identifying patterns is proposed,
so that any pattern generated has its own identification number, which can be decoded later to restore
模式.
* School of Mechanical Engineering, Yeungnam University, Kyongsan, 712-749, 韩国. 电子邮件: jkshin@yu.ac.kr
© 2011 麻省理工学院
人工生命 17: 21–32 (2011)
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
A
r
t
我
/
/
我
A
r
t
我
C
e
–
p
d
F
/
/
/
/
1
7
1
2
1
1
6
6
2
7
5
6
A
r
t
我
/
_
A
_
0
0
0
1
5
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3
J. K. Shin
2 模型
Identifying Patterns from One-Rule-Firing Cellular Automata
The CA system in the present study is composed of a hexagonal array of cells in the 2D plane. 一个
occupied cell possesses values, or color codes, 范围从 1 to m. Each occupied cell is called an
element. 为了方便, an empty cell is assigned a color code value of 0. 因此, a cell can be in any
of the M = m + 1 possible cell states. Once defined, an element does not change its value or return to
being an empty cell. A cell has a set of neighborhood cells composed of its six nearest cells. The six
neighborhood cells are designated as b1, b2, …… , b6, 如图 1. The neighborhood cells are
always numbered clockwise starting from the top center cell. An empty cell is called a surface cell if it has
at least one element in its neighborhood. The numbering of the elements and of the surface cells is
important for the present study and will be discussed in further detail later.
The CA rule is applied in a synchronous manner to only a few of the surface cells. A rule determines
the value (or color code) of a surface cell at the next time step as a function of the states of the neighbor-
ing cells at the present time step. 一般来说, the number of possible states for the six neighboring cells
will be M6. A rule set has M6 rules, each of them mapping the states of the neighboring cells to a value.
Because the number of rules in a rule set increases vary fast with M, it is not easy to express the rules in
compact form, even for small values of M. 例如, when M = 7, a rule set has 76 = 117,649 规则. 在
order to describe each rule set, 我们需要 117,649 digits, where each digit represents a rule value. This study
investigates a manner in which we can overcome this difficulty and conveniently specify a rule set.
Starting from a single element at time step 0, the system evolves into a complex pattern, applying the
rules repeatedly to the surface cells. One of the main purposes of the present article to observe the
patterns that emerge with the application of the rules.
3 One-Rule-Firing Scheme
The six-color problem in which m = 6 and M = 7 is the only problem considered in the present study,
unless stated otherwise. Because of the very large number of possible rule sets, the present study will be
limited to a certain category of rules. 尤其, symmetry-preserving rule sets are considered. 这
key idea of the present study is to fire the rules selectively. In typical CAs with synchronous updating,
the rules are applied to all of the candidate cells at a given time step. In the present article, only one rule is
fired in a time step. 因此, the process of choosing the single rule that is to be fired should be
clearly defined.
Rules are defined in terms of the states of the six neighboring cells. A state of the six neighbors will
be represented with a six-digit number such as 335012, where each digit represents the state (color code)
of the neighboring elements and/or empty cells. 一般来说, a different rule can be specified for each of
the different neighborhood states. 然而, rotational symmetry is assumed in the present study: 任何
数字 1. Six neighbors of an element.
22
人工生命量 17, 数字 1
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
A
r
t
我
/
/
我
A
r
t
我
C
e
–
p
d
F
/
/
/
/
1
7
1
2
1
1
6
6
2
7
5
6
A
r
t
我
/
_
A
_
0
0
0
1
5
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3
J. K. Shin
Identifying Patterns from One-Rule-Firing Cellular Automata
cyclic rotation of a given set of six represents the same state. With rotational symmetry implied, 这
number of rules in a rule set is reduced to 19,684. 在这种情况下, a rule set can be represented with
19,684 digits. An example of it might look like 110346…6001 (19,684 digits), keeping in mind that
the first digit is for the rule value of the first rule, 等等. 为了方便, the neighborhood states
will be used to denote the rule number. If the neighborhood state of a surface cell is 001234 或者 234001,
例如, then the rule number to be applied will be 1234.
A single seed element at time step 0 will be used as an example to demonstrate the key concepts of this
present study. At time step 0, only one element, e1, exists in the system. Throughout the present study,
assume that the seed element e1 possesses a color code of 1. This will be represented as e1 = 1. 这
element e1 has six neighbors. Each of the six neighbor cells is currently a surface cell and has the same
neighborhood state, equivalent to 000001. The rule number to be applied will simply be 1. Assume, 为了
例子, the rule value for rule 1 是 3, or rule(1) = 3. Applying the rule to the six surface cells will end
iteration 1. Regardless of the synchronous updating scheme, the order of the updating should be carefully
monitored, solely for the purpose of determining the order of the newly generated elements. The updating
should start from surface cell 1 在这种情况下, or from the lowest numbered surface cells in general. 后
iteration 1, 数字 2 is obtained. Elements are denoted by shaded cells in which the identifying numbers
are marked at the centers of the cells. They are numbered according to birth order. The small number in
each element cell represents the color of the element. The color (designated as 3) of e2 through e7 was
determined from the application of rule(1) = 3. After the first iteration, the system contained a total of
12 surface cells, 如图 2. The surface cells are numbered elementwise first, and then neigh-
borhoodwise. 换句话说, the surface cells contacting the lowest-numbered elements should be
numbered first. 图中 2, the three surface cells S1, S2, and S3 neighbor e2, possessing lower surface
cell numbers than the other surface cells. Each of these three surface cells is located on the b1, b2, and b6
neighborhood positions of element e2, as defined in Figure 1. Assigning a lower surface cell number to a
lower neighborhood position, we get S1, S2, and S3, exactly as shown in Figure 2. S3 is observed again
when handling the surface cells contacting element e7. 然而, since S3 was previously numbered, 这是
skipped when approaching element e7. Surface cell numbering is scratched after each iteration, and restarts
in every iteration. Once an element number is chosen, it is maintained throughout later time steps.
In the subsequent process, the CA rules are applied to the 12 surface cells of the present time step.
桌子 1 illustrates the details. The rules are applied to the surface cells depending on their neighborhood
地位. 例如, surface cells S1, S4, S6, S8, S10, and S12 each possess a neighborhood status
数字 2. Numbering of elements and surface cells.
人工生命量 17, 数字 1
23
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
A
r
t
我
/
/
我
A
r
t
我
C
e
–
p
d
F
/
/
/
/
1
7
1
2
1
1
6
6
2
7
5
6
A
r
t
我
/
_
A
_
0
0
0
1
5
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3
J. K. Shin
Identifying Patterns from One-Rule-Firing Cellular Automata
桌子 1. Application of rules, assuming r(1) = 3, r(3) = 4, r(33) = 6.
Iteration
Surface cell
Neighborhood code
Valuea
Fired
1
2
S1
S2
.
..
S6
S1
S2
S3
S4
.
..
S9
S10
S11
S12
1
1
.
..
1
3
33
33
3
.
..
33
3
33
3
是
是
.
..
是
是
是
.
..
是
是
.
..
3
.
..
(6)乙
4
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
A
r
t
我
/
/
我
A
r
t
我
C
e
–
p
d
F
/
/
/
/
1
7
1
2
1
1
6
6
2
7
5
6
A
r
t
我
/
_
A
_
0
0
0
1
5
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3
aMarked only when the rule first appears with backward counting of sur-
face cells.
bRule value is defined, but not fired, at least in present iteration.
equivalent to 000003, indicating that rule 3 should be applied to these cells. The neighborhood status for
the other cells, including S2, S3, ……, S11, is equivalent to 000033, 并统治 33 should be applied, if ever,
to these cells. The rule number and rule value that correspond to each of the surface cells are shown in
桌子 1, columns 2 和 3. Two new rule values are assumed: 规则(3) = 4 并统治(33) = 6. In a con-
ventional CA, the two rules 3 和 33 will be fired at time step 2, resulting in the potential generation of
twelve new elements.
然而, the present study proposes a new variation, in which only one rule is fired in a given time
step. Among several easily conceived possible one-rule firing schemes, last-nonzero-rule firing is the
main scheme utilized here. Among the rules to be fired in a given time step, the last rule not possessing
值为 0 was chosen. 这里, the last refers to the surface cell number. 例如, at iteration 2,
规则 3 和 33 were waiting to be fired. Of the two rules, 规则 3 is the last rule of the time step, as it
is combined with the last surface element of the time step. Because the value (equal to 4) of rule 3 不是
零, 规则 3 was chosen to be fired at iteration 2. 规则 3 is the last nonzero rule in time step 2. 规则 33
is not fired in this time step, and the six surface cells S2, S3, S5, S7, S9, and S11 remain as empty cells
even after iteration 2. By applying rule 3, six new elements of color code 4 are generated at iteration 2.
The fired surface cells are marked in the last column of Table 1. The same process was already applied
in iteration 1. If a rule is ever fired, it proceeds from the lowest-numbered surface cells that could
be applied. The order of firing is important, as it determines the numbering of the newly generated
24
人工生命量 17, 数字 1
J. K. Shin
Identifying Patterns from One-Rule-Firing Cellular Automata
元素, 哪个, 反过来, determines the numbering of the surface cells in the next time step. 在里面
fourth column of Table 1, the rule values are given when the rule is first considered to be fired through-
out an entire iteration. As seen before, some of those rules do not fire at the time step in which they first
出现. In actuality, 规则 33 does not contribute to the system up to time step 2.
Continuing on with the process, we can easily imagine that different rule sets generate different pat-
燕鸥. 和 719,684 ≈ 9 × 1016,634 rule sets, we can predict that to be the number of patterns in the 2D
space of CA. 另一方面, every pattern that appears will have its own rule set, composed of
19,684 规则. Theoretically speaking, a pattern can be identified with its rule set. This means that we need
19,684 characters in order to identify a pattern, in which each character represents a rule value. 什么时候
the size of a rule set is sufficiently small, we can directly represent the rules with a manageable number of
characters. 例如, in a one-dimensional space for a CA, a rule set can be identified by only three
digits [18]. But when the number of rules increases, it will be inconvenient to use a long sequence of
codes in order to identify a pattern. The present study demonstrates an efficient method that compen-
sates for this difficulty.
综上所述, we can only list the rule values that were fired, as shown in the fourth column of Table 1.
例如, the sequence of rule values 34 and so forth can identify the pattern. It is unnecessary to
memorize the rule number for each rule value fired. The rule number is embedded in the pattern itself. 这
sequence of the rule values will be called the F-code (for “code of fired rules”) for convenience.
然而, one problem remains to be solved: How do we address the situation where the value of
the last rule is zero? 例如, assume rule(3) = 0 in the example case given in Table 1. 案子
is explained in Table 2. The first iteration is the same as before. But for the second iteration, 因为
桌子 2. Application of rules, assuming r(1) = 3, r(3) = 0, r(33) = 6.
Iteration
Surface cell
Neighborhood code
Value
Fired
1
2
S1
S2
.
..
S6
S1
S2
S3
S4
.
..
S9
S10
S11
S12
1
1
.
..
1
3
33
33
3
.
..
33
3
33
3
是
是
.
..
是
是
是
.
..
是
是
.
..
3
.
..
6
0
人工生命量 17, 数字 1
25
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
A
r
t
我
/
/
我
A
r
t
我
C
e
–
p
d
F
/
/
/
/
1
7
1
2
1
1
6
6
2
7
5
6
A
r
t
我
/
_
A
_
0
0
0
1
5
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3
J. K. Shin
Identifying Patterns from One-Rule-Firing Cellular Automata
the value for last rule is 0, we cannot fire it. Firing a rule possessing the value 0 does not alter the
图案, and it is the same as doing nothing. So we skip the rule of value 0. For the case shown in
桌子 2 at iteration 2, 规则(33) = 6 is the last nonzero rule, which is then chosen as the rule to be
fired. 在这种情况下, we can include the code 0 in the F-code so as to remember that the rule is not
fired on the last surface cell. 因此, the F-code will be 306 而不是 36, for the case shown in
桌子 2. It should be noted that a rule already contributed to the F-code in an earlier time step does
not enter again in an F-code, even if it fires again in later time steps. 一般来说, the length of the F-
code can increase with the time step. But the length should be far shorter than 19,684 大多数情况下.
We can identify a pattern with F-codes a few to a few hundred characters in length.
4 Example Patterns
Generating F-codes using the previous procedure is not difficult. 例如, start with generating
a rule set at random. For clarity, a procedure for generating a pattern, or equivalently an F code, 是
listed as follows:
Step 1. Choose a rule set composed of 19,684 规则.
Step 2. Choose a seed element.
Step 3.
Identify surface elements of the present time step, and order them elementwise first
and then neighborhoodwise.
Step 4. Apply the last nonzero rule to all the corresponding surface cells. Application of a rule
is simultaneous, but the ordering of newly added elements depends on the order of the
surface cell on which the element is generated.
Step 5.
If the last nonzero rule in step 4 is a new rule that has never been fired up to this time step,
update the F-code by concatenating the rule value (代码) at the end of the present F-code.
Step 6. To continue the process, go to step 3.
As generalizations, we may consider different possibilities of rule sets for step 1. Step 2 can also
be generalized. 原则, any set of initial conditions is welcome. The initial conditions should
specify the spatial position(s) and color code(s) of the initial element(s), including their numbering.
It should be noted that the F-codes for two different initial conditions should not be compared
直接地. We can consider different firing schemes for step 4. A different firing scheme indicates a
separate F-code system. The F-code scheme is quite general; 然而, the conditions under which
the F-code is generated must be thoroughly understood.
Because of the rotational symmetry imposed on the rules, all the patterns generated in this study
have a sixfold rotational symmetry about the center cell. 数字 3 illustrates the simplest forms found
during the present study. 尤其, the shape shown in Figure 3a is the simplest pattern in which
the F-code retains the value 1, or F = 1. Only one rule, 规则 1, with rule(1) = 1, is necessary to
generate this pattern. This pattern is well known as Packardʼs snowflake [9]. It is surprising that such
a complex shape can be generated with a single rule. But in actuality, this pattern is known to be
obtained when an element is added whenever a cell has only one neighborhood. This is implied by
F = 1. 为了方便, we call this pattern F1.
For later discussion, consider the validity of an F-code. When we consider, 例如, a ran-
domly generated code such as F = 120314, we soon find that the codes, except for the first appear-
ance of 1, are meaningless. When the first value of an F-code is 1, the pattern can grow infinitely
without consuming any other rules. Thus the code F = 1 is the only code that can start with color
代码 1. 一般来说, an arbitrary sequence of rule values is not worth its full length. From now on,
only the F-codes that are valid through their full length will be considered.
26
人工生命量 17, 数字 1
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
A
r
t
我
/
/
我
A
r
t
我
C
e
–
p
d
F
/
/
/
/
1
7
1
2
1
1
6
6
2
7
5
6
A
r
t
我
/
_
A
_
0
0
0
1
5
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3
J. K. Shin
Identifying Patterns from One-Rule-Firing Cellular Automata
数字 3. Simple patterns: (A) F = 1, (乙) F = 201, (C) F = 20222.
We can categorize the valid F-codes into two groups: finished and unfinished. A finished F code
signifies that additional codes are unnecessary in the continuation of the iteration to an arbitrary time
step. Finished F-codes can be further distinguished into two subgroups. 在一些, like the case in
which F is equivalent to 1 和 21, the patterns can grow infinitely with the given codes. On the other
手, certain F-codes reach completion, because the patterns discontinue growth after some itera-
的. This happens when all surface cells at a given time step are assigned to a rule (or rules) of value 0.
例如, for F = 200 and F = 320110132021010133031003122312101123103023 the pattern dies
at iterations 3 和 80, 分别.
Unfinished F-codes require more explanation. 例如, F = 2032 is an unfinished F-code. If we
decode F = 2032, a new rule will be necessary after firing the last given code. If we supply a next code of
1, 例如, then the F-code grows to F = 20321. This sequence may continue excessively. 和-
finished F-codes exist because the iterations are not continued infinitely. Theoretically, an unfinished
F-code cannot exist if the iteration is continued infinitely. This is because the maximum length of the
F-code is 19,684. If we consider all F-codes up to that maximum length, all F-codes should be finished.
然而, it is more realistic to state that an F-code is unfinished up to a specified time step. 此外,
if an F code is not proven to be finished at the specified time step, it will also be taken as unfinished. 这
finished and the unfinished codes will be distinguished in the following manner: A lowercase f signifies
an unfinished F-code, while an uppercase F designates a finished code. 因此, F = 2342 represents a
finished F-code, and f = 2032 represents an unfinished one.
A relatively small number of patterns were observed with short F-codes. We have already seen that
F = 1 is the only F-code of length one. 此外, only one group of patterns exists for an F-code of
length 2: F = 22, 33, 44, 55, 和 66 generates similar patterns to F1, but possesses two colors, indicating
different cell values. The number of colors used in the pattern can be counted simply by observing an
F-code. 例如, F = 201 is generated using two rules, whose values are 2 和 1. 这意味着
F = 201 uses two colors. When counting the number of colors used, we should remember the initial
seed element, which has color code 1. Thus F = 22 is a two-color pattern, including the initial element.
Figure 3b shows the third simplest pattern, which has an F-code of length 3. The branches in Figure 3b
grow endlessly with the time step. Each of F = 201, 301, 401, 501, 和 601 generates the same pattern
as shown in Figure 3b. The main observable difference among the aforementioned codes is the color
retained by each. Figure 3c shows a pattern with F = 20222.
All possible F-codes cannot be listed, but sample patterns can be easily generated using the afore-
mentioned method. The single-rule-firing scheme produces many interesting patterns. 数字 4 节目
a few examples. The patterns are shown according to increasing lengths of the F-codes (or f-codes).
Figure 4a illustrates a similar shape to F1, differing only in color. If we neglect the colors, we observe that
the shape of F1 repeatedly occurs whenever F-codes do not include 0. 例如, F = 1, 22, 323,
2344, 32541, 和 325462 result in the shape of F1. From an exhaustive simulation for all F-codes up
to length 7, the conclusion followed that the maximum length of F-codes not containing 0 is six. 在
人工生命量 17, 数字 1
27
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
A
r
t
我
/
/
我
A
r
t
我
C
e
–
p
d
F
/
/
/
/
1
7
1
2
1
1
6
6
2
7
5
6
A
r
t
我
/
_
A
_
0
0
0
1
5
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3
J. K. Shin
Identifying Patterns from One-Rule-Firing Cellular Automata
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
A
r
t
我
/
/
我
A
r
t
我
C
e
–
p
d
F
/
/
/
/
1
7
1
2
1
1
6
6
2
7
5
6
A
r
t
我
/
_
A
_
0
0
0
1
5
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3
数字 4. Miscellaneous patterns: (A) Multicolored F1, F = 264531, Iter = 91. (乙) A snow crystal, F = 20212020, Iter = 61. (C)
A flower pattern, f = 530220402410633633421424631012641254064350520610000 (51 digits), Iter = 421. (d) Palm tree,
f = 6203203210253346253045601315350161554520132566153342200260605623524521546616555235110616445151-
60365425413323 (108 digits), Iter = 1221.
一般的, the maximum length of F-codes without 0 corresponds to the number of colors used in the
rule set. If an F-code contains a 0, the shape deviates from the F1 pattern, as observed in the patterns
of F = 201 和 20222 listed in Figure 3.
More diverse shapes are shown in Figure 4b–d. The length of an F-code can exceed 6 only when the
F-code includes a 0. The following is a brief explanation as to why F-codes not containing a 0 result in
the same shape: For codes not containing a 0, the rule always fires on the last surface cell in each time
step. But when a zero is assigned to the last surface cell, the rule is fired on a cell other than the last
surface cell. 随后, altering the firing location gives birth to diverse shapes. 因此, a necessary
condition for the shape deviation from the basic pattern of F1 is that the F-code should contain at least
one zero. 然而, the converse does not generally hold true. 那是, instances are found in which the
F-code contained at least one 0 and still resulted in a shape the same as, or at least similar to, F1. 这
pattern in Figure 4b has an F-code of length 8. This pattern resembles a snow crystal. Only two colors are
used in this case. The snow crystal patterns were observed frequently when only two colors were used
in the F-code. All three patterns shown in Figure 3 and the pattern in Figure 4b are generated with only
two colors. 然而, this does not mean that snow crystals cannot be obtained with multiple colors.
The length of an F-code measures the complexity of the corresponding patterns, indicating the num-
ber of rules used to generate the pattern. Conceptually, it is similar to Birkhoffʼs measure of the complex-
ity of an image, which is defined as the number of elements composing the image [5]. Because F-codes
of different lengths can yield the same shapes, we can conclude that color is one origin of the complexity.
28
人工生命量 17, 数字 1
J. K. Shin
Identifying Patterns from One-Rule-Firing Cellular Automata
例如, the shape F1 is found to have a complexity of up to the number of colors used. 上
另一方面, because long F-codes can be generated using only two colors, especially when 0 is included
in the F-code, we find that shape is another source of the complexity. With the combined contribution
of shape and color, a wide variety of complex patterns emerge. In Figure 4c,d, two patterns with long
f-codes are shown. For these two patterns, the length continually grows up to time steps 421 和 1221,
分别. If we increase the time step, new rules will appear and commence to be fired. The last two
patterns shown in Figure 4 interestingly resemble flowers and plants, 分别. Purely geometric pat-
燕鸥, such as snow crystals, and lifelike patterns can emerge under the same algorithm.
The aforementioned patterns sufficiently illustrate the effects of the one-rule firing scheme. If we use
a conventional all-rule-firing scheme, the resulting patterns are quite different. 图中 5, a comparison
is made between the patterns generated from the one-rule-firing and an all-rule-firing scheme. 为了这
比较, a full set of 19,684 rules were generated first, and the iteration is processed as explained in
the present study. Figure 5a shows the resulting pattern from one-rule firing up to iteration 301. 这
pattern in Figure 5b is the same up to iteration 91. Figure 5c is a pattern generated by firing all the rules
up to time step 91. In every time step, all the surface cells with nonzero rule values are fired. When all
the rules are fired, the pattern grows very rapidly. Roughly the same scale is maintained for these three
patterns in Figure 5. 在多数情况下, the shape generated under the all-rule-firing scheme has one of the
two shapes. The shape of F1 appears most frequently under all-rule firing, but a circular shape as shown
in Figure 5c appears at times. This example clearly shows the magic of the one-rule firing strategy. By one-
rule firing, we can dig buried flowers out of a mud ball.
Among the patterns generated in the present study, flowerlike patterns are the most interesting, 在
view of the clearly distinguishable characteristics that separate them from geometric patterns found in
the previous literature. The F-codes are reminiscent of genetic codes in biological systems. 例如,
we can mutate F-codes to find variations of the original flower patterns. 数字 6 shows three flowers
in which the f-codes are the same except at a single location, differing only at the 20th location, 这是
represented as X. The three patterns with X = 0, 1, 和 5 possess similar shapes near the center. 如何-
曾经, differences emerge as the pattern expands outward from the center. 此外, two F-codes
could be crossed in order to find daughter flowers.
5 讨论
The one-rule-firing scheme first provides a new dimension, shape, to the patterns that depended only on
the color of the all-rule firing scheme. It was a startling speculation that diverse shapes can result from
数字 5. One-rule firing and all-rule firing: (A) f = 652040430032650204605024105 (27 digits), Iter = 301. (乙) f =
6520404300326502046050 (22 digits), Iter = 91. (C) All-rule firing, Iter = 91.
人工生命量 17, 数字 1
29
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
A
r
t
我
/
/
我
A
r
t
我
C
e
–
p
d
F
/
/
/
/
1
7
1
2
1
1
6
6
2
7
5
6
A
r
t
我
/
_
A
_
0
0
0
1
5
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3
J. K. Shin
Identifying Patterns from One-Rule-Firing Cellular Automata
数字 6. Cloning the flowers: f = 4501430233150000020X006500620055, Iter = 211: (A) X = 0, (乙) X = 1, (C) X = 5.
differential growth along different directions. The partial rule-firing scheme realizes the concept of
differential growth, 和 (毫不奇怪) numerous patterns were discovered, including geometric pat-
燕鸥 (snow crystals) and flowerlike patterns. Without resorting to the complex rules of the fuzzy cellular
automaton [2, 11], the one-rule-firing scheme successfully generated snow crystals with a conventional
discrete CA. The natural patterns generated in the present study are reminiscent of the L-system as a
classic rule-based system to represent natural patterns [10, 14]. One interesting aspect of the one-rule-
firing CA is in its diversity: Both natural and non-natural patterns can be represented under the same
scheme. Another notable CA system comparable to the present one-rule CA may be the mobile cellular
automaton [18], in which the rule is updated only in one active cell. It is called mobile because the location
of the active cell moves from iteration to iteration. In the mobile CA, an additional rule is necessary to
describe which one is the active cell for each of the time steps. 相反, both the evolution rules
and the active cells are included in a single F-code.
Although an F-code can efficiently identify a pattern, it should be stressed that it is valid only
within a specified boundary. An F-code should be defined under a given set of conditions, 包括
(我) the color of the initial seed element, (二) the numbering schemes of the neighborhoods, the ele-
评论, and the surface cells, (三、) the firing strategy, 和 (四号) the equivalence relation between the
states of the surface cells (in addition to the basics of the CA, such as cell shapes). If at least one of
the above definitions is different for two F-codes, they cannot be compared directly.
In actuality, the last-nonzero-rule firing is only one of the many possible partial firing schemes. 为了
例子, 数字 7 shows two flower patterns that were obtained by firing all the rules that have the same
rule value with the last nonzero rule at a given time step. The F-codes are not given in these cases, as it
数字 7. Flowers generated with another rule-firing scheme.
30
人工生命量 17, 数字 1
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
A
r
t
我
/
/
我
A
r
t
我
C
e
–
p
d
F
/
/
/
/
1
7
1
2
1
1
6
6
2
7
5
6
A
r
t
我
/
_
A
_
0
0
0
1
5
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3
J. K. Shin
Identifying Patterns from One-Rule-Firing Cellular Automata
is meaningless to directly compare the F-codes of two different firing schemes. If we focused on a
simpler coding system, we could think of a rule-firing scheme that works without numbering the surface
cells and the elements. 例如, if we choose to fire the rule with the smallest rule number in the
present time step, we do not need to keep track of the numberings of the surface cells and the elements.
This simplifies the process, allowing for pattern growth to easily occur. When implemented during the
present study, the patterns generated under this minimum-rule-firing scheme were found to be less
diverse than those from the last-rule-firing scheme.
The present firing scheme can also be applied to systems based on different types of cells. 对于前-
充足, 数字 8 shows patterns generated on 2D square cells. Four colors (m = 4) are used for these
examples. Although the cell type and the number of colors used are changed, the patterns generated can
be similarly classified. Figure 8a shows the F1 pattern under the new category. It consumes only one code
and can grow infinitely. This pattern is already known in the literature as code 942 [18]. The other two
figures in Figure 8 show a geometric pattern and a flowerlike one, 分别. Some complex patterns on
2D square cells were also reported in a special type of sandpile system in which grains are added to only
one site of the system [13]. It is not presently clear whether such sandpile patterns can be represented
in terms of the F-code, just as the Packard-type snow crystal is identified as F = 1. 一般来说, it is of
theoretical interest whether a pattern can be represented by an F-code or not. 此外, one may ques-
tion the uniqueness of the F-code. It is clear that an F-code can define a pattern uniquely. It seems that the
reverse is not always true. 例如, each of the F-codes 201, 301, 401, 501, 和 601 generates the
monochrome pattern shown in Figure 3b. These five patterns differ only in color. Because these patterns
are monochrome, they are essentially the same. But it is not known whether two different codes can
result in exactly the same pattern, both in color and in shape. The solution of this problem is not a main
focus of the present study and is left as a topic for future study.
In addition to the uniqueness question, the present study elicits several interesting questions. Firstly,
how many possible finished F-codes can be generated at a given length? Up to iteration 60, totals of 1,
10, 70, 305, 875, 3780, 和 19765 F-codes were identified from length 1 to length 7, 分别. Ex-
tending the numbers to longer F-codes is challenging. The second question at hand is whether we can
classify the rules, or equivalently the patterns, as in the cases of Wolfram [17] and other researchers
[3, 4]. 最后, do the flowerlike patterns possess any relation to real flowers? In addition to these the-
oretical questions, finding interesting patterns using different partial-firing schemes (together with, 例如,
an application of a genetic algorithm) will be an exciting game.
6 结论
The partial firing of rules on a growing cellular automaton generated myriad patterns, 范围从
natural shapes, such as flowers, to the well-known snow crystals and simple geometric patterns. A list
数字 8. Patterns from square cell system with m = 4: (A) F1 on square cell, Iter = 61. (乙) Geometric pattern, f =
(16 digits), Iter = 151. (C) Flower-like pattern, f = (31 digits), Iter = 241.
人工生命量 17, 数字 1
31
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
A
r
t
我
/
/
我
A
r
t
我
C
e
–
p
d
F
/
/
/
/
1
7
1
2
1
1
6
6
2
7
5
6
A
r
t
我
/
_
A
_
0
0
0
1
5
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3
J. K. Shin
Identifying Patterns from One-Rule-Firing Cellular Automata
of all the fired-rule values (F-codes) to generate a pattern is suggested as an efficient identifier of the
pattern. The Packard type of snowflake, which is the only shape resulting from a single-digit F-code, 曾是
identified as the simplest of all the shapes under the assumed category of patterns defined in the present
学习. Some complex shapes were found having F-codes with more than one hundred digits. A large
number of F-codes containing up to seven digits were identified through exhaustive numerical search.
A method of obtaining new patterns by mutating the F-codes was demonstrated through an example.
还, the length of an F-code is suggested as a natural measure of the complexity of the given pattern,
indicating the number of different rules necessary to generate the pattern. The complexity of patterns is
believed to originate from two distinct sources: color and shape. 尤其, the existence of code 0
in the F-codes was found to be a necessary condition for generating diverse shapes. 最后, a number of
topics for future research were discussed.
致谢
This research was supported by Yeungnam University research grants in 2010.
参考
1. Guy, R。, 康威, J。, & Berlekamp, 乙. (1982). Winning ways: For your mathematical plays: 卷. 2. 圣地亚哥, CA:
学术出版社.
2. Coxe, A。, & 赖特, C. (2003). Fuzzy hexagonal automata and snowflakes. Computers and Graphics, 27, 447–454.
3. Emmert-Streib, F. (2010). Exploratory analysis of spatiotemporal patterns of cellular automata by clustering
compressibility. Physical Review E, 81, 026103.
4. Gerling, 右. (1990). Classification of triangular and honeycomb cellular automata. Physica A: Statistical and
Theoretical Physics, 162(2), 196–209.
5. Rigau, J。, Feixas, M。, & Sbert, 中号. (2007). Conceptualizing Birkhoffʼs aesthetic measure using Shannon
entropy and Kolmogorov complexity. 在D中. 瓦. 坎宁安, G. 迈耶, & L. 诺伊曼 (编辑。),
Computational Aesthetics, 2007, Eurographics Workshop on Computational Aesthetics in Graphics, 可视化,
and Imaging. Boca Raton, FL: CRC Press.
6. Gunji, 是. (1990). Pigment color patterns of mollusks as an autonomous process generated by asynchronous
automata. 生物系统公司, 23(4), 317–334.
7. Ingerson, T。, & Buvel, 右. (1984). Structure in asynchronous cellular automata. Physica D, 10, 59–68.
8. 李, J。, Adachi, S。, & Peper, F. (2007). Reliable self-replicating machines in asynchronous cellular automata.
人工生命, 13, 397–413.
9. 征收, S. (1992). 人工生命. 纽约: Vintage Books.
10. Lindenmayer, A. (1968). Mathematical models for cellular interaction in development. Journal of Theoretical
生物学, 18, 280–315.
11. von Neumann, J. (1966). The theory of self-reproducing automata, A. 瓦. Burks (埃德。). Champaign-Urbana, 伊尔:
伊利诺伊大学出版社.
12. Ning, C。, & 赖特, C. (2007). A cellular model for three-dimensional snow crystallization. Computers and
Graphics, 31, 668–677.
13. Ostojic, S. (2003). Patterns formed by addition of grains to only one site of an abelian sandpile. Physica A,
318, 187–199.
14. Prusinkiewicz, P。, & Lindenmayer, A. (1991). The algorithmic beauty of plants. 柏林: Springer-Verlag.
15. Schoenfisch, B., & Roos, A. (1999). Synchronous and asynchronous updating in cellular automata.
生物系统公司, 51, 123–143.
16. Suzudo, 时间. (2004). Spatial pattern formation in asynchronous cellular automata with mass conservation.
Physica A, 343, 185–200.
17. Wolfram, S. (1984). Universality and complexity in cellular automata. Physica D, 10, 1–35.
18. Wolfram, S. (2002). A new kind of science. Champaign-Urbana, 伊尔: Wolfram Media.
32
人工生命量 17, 数字 1
我
D
哦
w
n
哦
A
d
e
d
F
r
哦
米
H
t
t
p
:
/
/
d
我
r
e
C
t
.
米
我
t
.
e
d
你
A
r
t
我
/
/
我
A
r
t
我
C
e
–
p
d
F
/
/
/
/
1
7
1
2
1
1
6
6
2
7
5
6
A
r
t
我
/
_
A
_
0
0
0
1
5
p
d
.
F
乙
y
G
你
e
s
t
t
哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3
