Infinite Number of Disjoint Chaotic Subsystems of Cellular Automaton Rule 106 ()
1. Introduction
Cellular Automata (CA), first conceived around 1950 by von Neumann [1] , are a class of spatially and temporally discrete mathematical structure by local interactions and an inherently parallel form of evolution. The whole structure is able to produce complex and interesting dynamical phenomena by means of designing simple transition rule. Due to their simple mathematical constructions and distinguishing features, CA have drawn a great deal of attention from various scientists. In 1969, the study of topological dynamics of CA was developed by Hedlund [2] , who viewed one-dimensional CA in the context of symbolic dynamics as endo- morphisms of the shift dynamical system, where the main results are the characterizations of surjective and open CA. In 1970, Conway proposed game of life [3] , which received widespread interests among researchers in different fields. In the early 1980s, Wolfram proposed CA as models for physical systems exhibiting complex or even chaos behaviors and elementary CA (ECA) that consist of a one-dimensional array of finite binary cells, each interacting only with the two nearest neighbors [4] - [6] . He classified 256 ECA rules informally into four classes using dynamical concepts like periodicity, stability and chaos. In 2002, Wolfram introduced his work A New Kind of Science [6] . Based on this work, Chua et al. have concluded the dynamics of ECA from a nonlinear dynamics perspective [7] - [10] . And he divided 256 ECA rules into four classes: period-
rules
, Bernoulli-shift rules, complex Bernoulli-shift rules and hyper Bernoulli-shift rules.
Gratefully, the research of CA has drawn more and more scientists’ attention in the last 20 years. Many concepts of topological dynamics have been used to describe and classify them [11] - [15] . And the dynamical properties of some robust Bernoulli-shift rules have been studied in the bi-infinite symbolic sequence space [14] , [15] . Rule 106 belonging to hyper Bernoulli-shift rules possesses complex and distinctive dynamical behaviors. In a paper [16] , the authors introduced the notion of permutivity of a map in a certain variable. Then they proved that every one-dimensional CA based on the local rule which is permutive either in the leftmost or rightmost variable is Devaney chaotic. Rule 106 is in this situation. Presently, this work is devoted to an in-depth study of rule 106 from the perspective of nonlinear dynamics under the framework of bi-infinite symbolic sequence space, and mainly studies the complex dynamics on its infinite number of subsystems.
The rest of the paper is organized as follows: Section 2 presents the basic concepts of one-dimensional CA and symbolic dynamics. Based on these concepts, it shows a subsystem of rule 106. Section 3 explores the complex dynamical behaviors of rule 106. Section 4 describes that there exist infinitely many disjoint chaotic subsystems in this chaotic subsystem. Finally, Section 5 concludes this paper.
2. Preliminaries
For a finite symbol
, a word over
is finite sequence
of elements of
. The length
of a is denoted by
. Denote the set of all words of length
by
. If
is a finite or infinite word
and
is an interval of integers on which
is defined, put
and
.
is a subword of
, denoted by
, if
, for some interval
; otherwise,
denoted
. The set of bi-infinite configurations is denoted by
and a metric “
” on
is defined as
, where
, and
is the metric on
defined as
. It is well known that
is a compact, perfect and totally disconnected metric
space.
By a theorem of Hedlund, a map
is a cellular automata iff it is continuous and commutes with
shift map
, i.e.,
, where
is defined by
. For any CA there exists
radius
and a loca rule
such that
. Moreover,
is a com- pact dynamical system. To enhance readability, it is desirable to write a CA as
for local rule
.
A set
is
-invariant if
, and strongly
-invariant if
. If
is closed
and
-invariant, then
or simply
is called a subsystem of
. For instance, let
denote a set
of some finite words over
, and
is the set which consists of the bi-infinite configurations made up of all the words in
. Then
is subsystem of
, where
is said to be the determinative block system of
.
For bi-infinite ECA,
and
is denoted by
. Each local rule can be expressed by a Boolean
function. For example, the Boolean function of rule 106 is
,
, where “.”, “
” and “?” stand for “AND”, “XOR” and “NOT” logical operations, respectively [11] .
Thus the global map of rule 106 is induced as follows: for any
,
,
, where
denotes the
th symbol of
. For clarity, the truth table of rule 106 is depicted in Table 1.
Based exclusively on this truth table, a subsystem of rule 106 in
is shown as follows.
Proposition 1. For rule 106, there exists a subset
such that
iff
,
,
, where
.
Proof: (Necessity) Suppose that there exists a subset
such that
, then,
, one has
According to the Boolean function
of rule 106, one has
this implies
so
and
can
not be 1 simultaneously,
. Additionally, if there exists
such that
then it
must satisfy that
or
, this is contradictory with
Hence, the
determinative block system of
is
.
(Sufficiency) The proof of sufficiency can be verified directly, the details are omitted here. The proof of the proposition is completed.
For illustration, simulations of the spatial and temporal evolution of rule 106 with a random initial configuration and an initial configuration of
are shown in Figure 1, where the black pixel stands for 1 and white for 0.
3. Complex Dynamics of 
In this section, the dynamical behaviors of
on
are exploited. As the topological dynamics of a subshift of finite type is largely determined by the properties of its transition matrix, it is helpful to briefly review some
definitions from [17] . A matrix A is positive if all of its entries are nonnegative; irreducible if
such
that
; aperiodic if
, such that
. If
is a 2-order subshift of finite type,
| | | |
000 | 0 | 100 | 0 |
001 | 1 | 101 | 1 |
010 | 0 | 110 | 1 |
011 | 1 | 111 | 0 |
翻译:
Table 1. Logical table of rule 106.

(a) (b)
Figure 1. (a) The evolution of rule 106 from random initial configuration, (b) The evolution of rule 106 from an initial configuration of
.
then the associated transition matrix
is the
matrix with
, if
; otherwise
.
Denote a 2-order subshift of finite type by
It is known that a 2-order subshift of finite type is
topologically mixing if and only if its transition matrix is irreducible and aperiodic [17] [18] .
The nonlinear dynamical behavior of
on
is discussed by establishing the topologically conjugate
relationship between
and a 2-order subshift of finite type. Let
be a new symbolic
set, where
,
, represent the elements in
, respectively. Then one can construct a new
symbolic space
on
. Denote by
.
Then, the 2-order subshift
of
is defined by
. Moreover, it is clear to see that the transition
matrix A of the subshift
is:

Theorem 1. 1)
and
are topologically conjugate;
2)
is topologically mixing;
3) the topological entropy of
satisfies
, where
is the spectral
radius of the transition matrix
.
Proof: 1) Define a map from
to
as follows:


where
. Then, it follows from the definition of
that for any
, one has
; namely,
. Then, it is easily to check that
is a homeomorphism and
.
Hence,
and
are topologically conjugate.
2)
satisfies
; namely,
is irreducible and aperiodic, which implies that
is
topologically mixing on
. Then, one can deduce
is topologically mixing according to Theorem 1 1)
and Proposition 1.
3) As
, where
is the spectral radius of the transition matrix
and
is the positive real root of
. And
and
are topologically conjugate, so
.
It is noted that a positive topological entropy is an important signature of the complexity of the system. It follows from [18] that the positive topological entropy implies chaos in the sense of Li-Yorke. And the topologically mixing is a very complex property of dynamical systems. A system with topologically mixing property has many chaotic properties in different senses. Therefore, the above mathematical analysis provides the following result.
Theorem 2. 1)
is chaotic in the sense of Li-Yorke;
2)
is chaotic in the sense of both Li-Yorke and Devaney on
.
4. Infinitely Many Chaotic subsystems of
in 
It is helpful to review some definitions and basic properties of releasing transformation before we discuss the
dynamics of
on infinite number of subsystems. Let
be a symbolic set, where
and
represent new symbols, respectively, and
. Denote by
the space of bi-infinite configurations over
and induce a
matric “
” onto
as defined in the preceding section. Then, the releasing transformation R is defined as follows:


where

Proposition 2. [19] Releasing transformation
is a continuous and injective map.
Let
,
,
, and
be a new sym- bolic set. Denote by
the subshift in
determined by the transition matrix as
. Then induce
, where
is the classical left-shift map. And let
be
, then induce
, where
. Then considering
and Proposition 1, one can easily obtain the following propo- sition.
Proposition 3. For each
,
is closed and
-invariant.
Proposition 4. For each
,
and
are topologically conjugate.
Proof: It is clear that the following diagram is commutative. The rest of proof can be completed by applying Proposition 2.

Theorem 3. For each
, 1)
is topologically mixing on each
;
2) the topologically entropy of
on
equals to
; therefore, the topologically entropy of
on
equals to
.
Proof: 1) It is clear to check that
is irreducible and aperiodic, thus
is topologically mixing on
,
. For each
,
and
are topologically conjugate, so
is topologically
mixing on each
and thus
is topologically mixing on each
based on Proposition 1 and Proposition
3.
2) Since
, where
is the the spectral radius of the transition
matrix
,
. Therefore,
according to Proposition 3. Then the
topologically entropy of
on each
equals to
; therefore, the topologically entropy of 
on each
equals to
.
Theorem 4. For each
, 1)
is topologically mixing on
;
2)
is chaotic in the sense of both Li-Yorke and Devaney on
.
Proof: 1) One can use the definition of the topologically mixing to prove that
is topologically mixing
on each
. i.e. for any two nonempty open subsets
,
, such that
. For each
, the following are two conditions to illustrate:
Case 1.
. According to theorem 3 (1),
is topologically mixing, namely, for any two nonempty
open sets
,
, such that
, so
,
.
Case 2.
,
. Firstly one need to prove that
is a
homeomorphism. Since
and
is
-invariant, then
is surjective. Suppose that there exist
, such that
, so
, which implies
, thus
. So
is injective. Since
is a compact Hausdorff space,
is one to one, onto and
continuous map.
exists and continuous. Therefore,
is a homeomorphism. This
implies that
is also an open set, thus, one has
, where
.
2) It is easily deduced by Theorem 3 (2) and Theorem 4 (1).
Note that
, where
,
. Let
, then
. Observe that
, then for each
,
is
closed and
-invariant. Thus Theorem 3 and 4 also hold for
, where
.
Remark 1. It is important to point out that the topologically entropy of
on
approaches 0 as
approaches
. Meanwhile, it has been proved that there exists a “big” subsystem of rule 106, including
infinite disjoint chaotic subsystems
. This analytical assertion provides an enlightening fact that the
hyper Bernoulli-shift rule 106 is full of infinite “small” chaotic subsystems in a “big” subsystem, demonstrating its very rich and complex dynamics.
5. Conclusion
One of the main challenges is to explore the quantitative dynamics in cellular automata evolution. Hyper Bernoulli-shift rules possess very interesting and complicated dynamical behaviors [19] [20] , for example, rule 180 possesses infinitely many generalized sub-shifts [20] [21] . This paper is devoted to an in-depth study of cellular automaton rule 106 in the framework of symbolic dynamics. Indeed, rule 106 actually is topologically mixing and possesses positive topological entropy on a subsystem. Furthermore, in this chaotic subsystem, rule 106 defines infinitely number of chaotic subsystems with rich and complex dynamical behaviors, such as topologically mixing, positive topological entropies and chaos in the sense of Li-Yorke and Devaney. Although in this work, one obtains some interesting results, to rule 106, it still needs much deeper research in the future.
Acknowledgements
This research was supported by the NSFC (Grant No. 11171084).