1. Introduction
1.1. Cellular Automata
Cellular automata (CA), formally introduced by von Neumann in the late 1940s and early 1950s, are a class of spatially and temporally discrete deterministic systems, characterized by local interactions and an inherently parallel form of evolution [1]. In the late 1960s, Conway proposed his now-famous Game of Life, which shows the great potential of CA in simulating complex systems [2]. In the 1980s, Wolfram focused on the analysis of dynamical systems and studied CA in detail [3,4]. In 2002, he introduced the monumental work A New Kind of Science [5]. In fact, mathematical theory of CA was firstly developed by Hedlund about two decades after Neumann’s seminal work [6]. Since 2002, Chua et al. provided a rigorous nonlinear dynamical approach to Wolfram’s empirical observations [7-10]. All elementary CA (ECA) rules are reorganized into four groups in terms of finite bit stings. There are 40 topologically-distinct period-
rules
, 30 topologically-distinct Bernoulli shift rules, 10 complex Bernoulli shift rules, and 8 hyper Bernoulli shift rules. Recently, the dynamical properties of Chua’s periodic rules and robust Bernoulli-shift rules with distinct parameters have been investigated from the viewpoint of symbolic dynamics [11-17].
By a theorem of Hedlund [6], a map
is an one-dimensional cellular automata (1-D CA) if and only if it is continuous and commutes with the shift map
. For any 1-D CA, there exists a radius
and a local map
such that
where notetions will be precisely defined below. In particular,
is an ECA global map when
and
. Each ECA can be expressed by a 3-bit Boolean function and coded by an integer
, which is the decimal notation of the output binary sequence of the Boolean function [5,7,18].
1.2. Definition of Chaos
Let
be a metric space and
:
be a continuous map.
is said to be topologically transitive or simply transitive if, for any non-empty open subsets
and
of
there exists a natural number
such that
;
is topologically mixing or simply mixing if there exists a natural number
such that
for all
;
is sensitive to initial conditions (or simply sensitive) if there exists a
such that, for
and for any neighborhood
of
, there exists a
and a natural number
such that
, where
is a distance defined on
.
Let
be the set of periodic points of
.
is said to be a dense subset of
if, for any
and any constant
, there exists a
such that
.
Definition 1.
is chaotic on
in the sense of Devaney if (1)
is transitive, (2)
is a dense subset of
, (3)
is sensitive [19].
It has been proved that additive 1-D CA are chaotic [20]. For general dynamical systems, it has been proved that (1) and (2) together imply (3) [21], and for 1-D CA, (1) implies (3) [22]. In the next section of this paper, it will be proved that, for 1-D CA with Bernoulli subshift of finite type (BSFT), (1) also implies (2).
1.3. Symbolic Dynamical Systems and SFT
For a finite alphabet
, a word over
is a finite sequence
of elements of
. Denote by
the set of all words of length
. If
is a finite or infinite word and
is an interval of integers on which
is defined, then denote
. Moreover,
is said to be a subword of
, denoted as
, if
for some interval
, where
is the set of all integers. The set of bi-infinite configurations is denoted by
, and a distance
on
is defined by
![](https://www.scirp.org/html/1-2340062\6aa5e71a-c702-4cea-bb8e-282a0a64a6a7.jpg)
where
,
, and
if
, or
otherwise. It is known that
is a compact, perfect and totally disconnected metric space [23].
For a map
, a set
is said to be
if
. If
is closed and
then
is called a subsystem of the dynamical system
. For example, let
be a set of some words of length
over
, and
be the set of the bi-infinite configurations consisting of all the words in
. Then,
is a subsystem of
, where
is the left shift
(or the right shift
) defined on
, and
is called the determinative block system of
. The subsystem
, or simply
is called a subshift of finite type (SFT) with respect to
.
Furthermore,
can be described by a finite directed graph,
, where each vertex is labeled by a word in
, and
is the set of edges connecting the vertices in
. Two vertices
and
are connected by an edge
if and only if
. One can think of each element of
as a bi-infinite path on the graph
. Whereas a directed graph corresponds to a square transition matrix
with
if and only if there is an edge from vertex
to vertex
, where
is the number of elements in
, and
(or
) is the code of the corresponding vertex in
,
. Thus,
is precisely defined by the transition matrix
.
Remarkably, a
square matrix
is irreducible if, for any
, there exists an
such that
; aperiodic if there exists an
such that
for all
, where
is the
entry of the power matrix
. If
is an SFT of
, then it is transitive if and only if
is irreducible; it is mixing if and only if
is aperiodic. Equivalently,
is irreducible if and only if for every ordered pair of vertices
and
there is a path in
starting at
and ending at
[23,24].
2. Transitivity and Chaoticity
In this section, it is proved that, for any 1-D CA restricted on its Bernoulli-shift subsystem, the shift transitivity implies the CA transitivity, and transitive nontrivial Bernoulli subshift of finite type (BSFT) has dense periodic points. Consequently, for 1-D CA, transitivity implies chaos in the sense of Devaney on the non-trivial BSFT.
2.1. Shift Transitivity Implies CA Transitivity
Definition 2. A closed invariant subset
of a 1-D CA
is called a Bernoulli-shift subsystem if there exists an integer pair
with
such that
, where
is the radius of the local map
of the CA
and
is the left (or right) shift map.
For simplicity, only consider
as the left shift in the following discussion.
Proposition 1. If
is a Bernoulli-shift subsystem of a 1-D CA
with
then there exists a
-sequence set
such that
.
Proof: If
is the local map of
, then one can get the
times iteration of
Thus,
, if and only if
for all
. Let
![](https://www.scirp.org/html/1-2340062\bea9c226-7443-475a-88de-2136d03430e3.jpg)
and
where
is a finite set since
Then, it follows that
.![](https://www.scirp.org/html/1-2340062\85d1a880-f009-4ea8-8f5d-405b4154a632.jpg)
Definition 3. The Bernoulli-shift subsystem
in Proposition 1 is called the Bernoulli subshift of finite type (BSFT), and
is called the determinative block system of
. If BSFT is an infinite set, then it is said to be non-trivial.
Based on Definitions 1, 3 and Proposition 1, an obvious result is the following proposition.
Proposition 2. Consider two BSFTs,
and
, of a 1-D CA
with
.
Then,
if and only if
.
Theorem 1. Let
be a BSFT of a 1-D CA
with
If the shift
is transitive, then
is also transitive.
Proof: Since the transitivity of
on
is equivalent to the existence of a
such that
where
![](https://www.scirp.org/html/1-2340062\975ee916-cb67-4a56-8f5b-1e085ebab242.jpg)
is the orbit of
starting from
and
is its closure [14,15]. It can be verified that for any
, there exists at least an
such that
.
Conversely, for any
, the
.
For the
above, consider the orbit
![](https://www.scirp.org/html/1-2340062\ccee9128-75f5-4c51-8734-6d6a620248bc.jpg)
and let
. It is clear that
is closed and
. Because
is
-invariant and closed, one has
and
. Obviously, ![](https://www.scirp.org/html/1-2340062\56c10641-ce3f-46a9-a813-0f22fe071480.jpg)
is transitive on
.
Let
denote the determinative block system of
. On one hand, based on Proposition 2 and
, one has
. On the other hand, since
, it follows that
, but the
-sequence set consisting of
is
. This implies
and
. Thus,
, i.e.,
is transitive on
.![](https://www.scirp.org/html/1-2340062\18f908e5-2898-4cd6-8283-f3b051020bec.jpg)
Remark 1.
1) Theorem 1 gives a convenient method to check if a CA
is transitive on a BSFT, since
is transitive on SFT if and only if the transition matrix corresponding to the SFT is irreducible [23,24].
2) Theorem 1 shows that the shift transitivity implies the CA transitivity on the BSFT, but the inverse implication may not be correct, with a counter example of ECA
. One has
, where ![](https://www.scirp.org/html/1-2340062\a5f8af96-f85a-4d21-bd5e-164dcd213dce.jpg)
and
,
, so
contains two points. It is clear that
is transitive but
is not. In case BSFT is an infinite set, whether the CA transitivity implies the shift transitivity on the BSFT is still an open problem.
3) When a BSFT
is a finite set on which
is transitive, then it is a set of
points,
for some
and
, it is said that
is trivial.
Remark 2.
Recall two claims proved in [22]: 1) transitive 1-D CA is always sensitive; 2) a 1-D CA
is transitive but not sensitive on a SFT
if and only if
for some
and
. It is easy to be verified that
and they are common multiples of
and
.
2.2. Transitivity Implies Density of Periodic Points
Theorem 2 Let
be a BSFT of a 1-D CA
with
. If the shift
is transitive, then the set of periodic points of ![](https://www.scirp.org/html/1-2340062\0601c965-1f34-47ff-85cf-761008009e0e.jpg)
is dense in
.
Proof: Let
be the BSFT, and
be its determinative block system. For any
and
, there exists a positive integer
such that
and for
it follows that
.
Since
is transitive on
there exists a path from
to
in the graph
. Let
![](https://www.scirp.org/html/1-2340062\f74668c6-36f3-42ca-b367-386553cfa3fe.jpg)
be the sequence corresponding to this path. Then, its any
-subsequences belong to
.
Now, construct a cyclic configuration
where
.
Obviously,
and
, where ![](https://www.scirp.org/html/1-2340062\0783a780-563a-454f-9cbe-05957b561a94.jpg)
is the length of
. Thus,
and
, i.e.,
and
.
Therefore, the sets of periodic points
is dense in
.![](https://www.scirp.org/html/1-2340062\e5330dc1-1f16-481e-a86e-c9fe07a12c0e.jpg)
By Theorem 2 and some results in [21], the following two theorems are obtained.
Theorem 3. If
is transitive on a non-trivial BSFT of a 1-D CA
, then
is sensitive on the BSFT.
Theorem 4. A 1-D CA
is chaotic in the sense of Devaney on its transitive non-trivial BSFT.
2.3. An Example of Transitive ECA Rule
Rule 26 is a member of Wolfram’s class IV and Chua’s hyper Bernoulli-shift rules, which defines many subsystems with rich and complex dynamics. This rule’s local map is
and
for all other triples
, and the corresponding global map is denoted by ![](https://www.scirp.org/html/1-2340062\78ebf7f3-6aab-48a4-8500-479841459821.jpg)
Proposition 3 There exists a BSFT of
,
![](https://www.scirp.org/html/1-2340062\a1f461e9-5a87-4291-ac6c-6999c87e23e4.jpg)
such that
, where
and
![](https://www.scirp.org/html/1-2340062\04595378-6f28-4267-a52c-b00a0f67ef0f.jpg)
Proof: Firstly,
is a closed set because
is an open set. Then, it can be easily verified that
for any
and
for any
. This implies that
for
.![](https://www.scirp.org/html/1-2340062\cb62d82f-ea4c-4449-8499-94b93fc03eb4.jpg)
It is clear that the transition matrix corresponding to
is
![](https://www.scirp.org/html/1-2340062\1409e8ae-222a-420c-8fad-995e2c75b6da.jpg)
Proposition 4. The transition matrix
is irreducible, so
is transitive on
.
Proof: Let
, where
is the identity matrix, and let
denote the elements of the power matrix
. It can be easily verified that
for all
, so
is aperiodic. Recall that a matrix
is irreducible if and only if
is aperiodic [23,24]. Hence,
is irreducible and so
is transitive on
.![](https://www.scirp.org/html/1-2340062\ee43c8c0-3ba4-4dbc-8887-4bbdf7eea2aa.jpg)
Theorem 5
is chaotic in the sense of Devaney on
.
3. Conclusion
As a particular class of dynamical systems, CA have been widely used for modeling and simulating many physical phenomena. Despite their apparent simplicity, 1-D CA can display rich and complex evolutions, but many properties of their temporal evolutions are undecidable [25,26]. Although checking the transitivity based on its definition is very difficult [27], and it alone is not sufficient for chaos to exist in general dynamical systems, this work has rigorously proved that the shift transitivity implies the CA transitivity, and the CA with transitive non-trivial BSFT are chaotic in the sense of Devaney, partly answer the open question whether Devaney chaos in 1-D CA is equivalent to transitivity [28].
4. Acknowledgments
This research was jointly supported by the NSFC (Grants No. 11171084 and No. 60872093), the Hong Kong Research Grants Council (Grant No. CityU1117/10) and Foundation of Zhejiang Chinese Medical University (Grant No. 17211076).