ABSTRACT

Recent progress in symbolic dynamics of cellular automata (CA) shows that many CA exhibit rich and complicated Bernoulli-shift properties, such as positive topological entropy, topological transitivity and even mixing. Noticeably, some CA are only transitive, but not mixing on their subsystems. Yet, for one-dimensional CA, this paper proves that not only the shift transitivity guarantees the CA transitivity but also the CA with transitive non-trivial Bernoulli subshift of finite type have dense periodic points. It is concluded that, for one-dimensional CA, the transitivity implies chaos in the sense of Devaney on the non-trivial Bernoulli subshift of finite types.

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 onis defined by

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 withthen 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

and

where is a finite set since Then, it follows that.

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

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

and let. It is clear that is closed and. Because is -invariant and closed, one has and. Obviously,

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.

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

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

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

be the sequence corresponding to this path. Then, its any -subsequences belong to.

Now, construct a cyclic configuration

where

.

Obviously, and, where

is the length of. Thus, and, i.e., and.

Therefore, the sets of periodic points is dense in.

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

Proposition 3 There exists a BSFT of,

such that, where and

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.

It is clear that the transition matrix corresponding to is

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.

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).

REFERENCES