# Complex Dynamic Behaviors in Cellular Automata Rule 14

Authors: Qi Han; Xiaofeng Liao; Chuandong Li
Journal: Discrete Dynamics in Nature and Society
 (2012)

---

## Abstract

Wolfram divided the 256 elementary cellular automata rules informally into four classes using dynamical concepts like periodicity, stability, and chaos. Rule 14, which is Bernoulliστ-shift rule and is a member of Wolfram’s class II, is said to be simple as periodic before. Therefore, it is worthwhile studying dynamical behaviors of rule 14, whether it possesses chaotic attractors or not. In this paper, the complex dynamical behaviors of rule 14 of one-dimensional cellular automata are investigated from the viewpoint of symbolic dynamics. We find that rule 14 is chaotic in the sense of both Li-Yorke and Devaney on its attractor. Then, we prove that there exist fixed points in rule 14. Finally, we use diagrams to explain the attractor of rule 14, where characteristic function is used to describe that all points fall into Bernoulli-shift map after two iterations under rule 14.


---

## Body

## 1. Introduction

Cellular automata (CA) was first introduced by von Neumann in 1951 [1]. CA is a mathematical model consisting of large numbers of simple identical components with local interactions [2]. The simple components act together to produce complex global behavior. CA performs complex computation with high degree of efficiency and robustness. Therefore, many applications of CA have been reported, especially in cryptography [3, 4] and image processing [5, 6].Here, we will only consider Boolean automata for which the cellular statex∈{0,1}. A cellular automata consists of a number of cells which evolve by a simple local rule (identical rule). The value of each cell in the next stage is determined by the values of the cell and its neighbor cells in the current stage under the local rule [4]. The identical rule contained in each cell is essentially a finite-state machine, usually specified in the form of a rule table, with an entry for every possible neighborhood of a cell consists of itself and the adjacent cells [7]. The cellular array is d-dimensional, where d=1,2,3 is used in practice. In this paper, we will concentrate on d=1. For a one-dimensional CA, a cell is connected to r local neighbors (cells) on either side where r is referred to as the radius. A one-dimensional CA has n cells linked in a line or in a circle. Denote the value in the ith cell at the tth stage by xi[t]. For 2-state 3-neighborhood CA (r=1), the evolution of ith cell can be represented as a function of the present states of (i-1)th, (i)th, and (i+1)th. The local function fi is a deterministic function to determine the next-stage value of the ith cell, xi[t+1]=fi(xi-1[t],xi[t],xi+1[t]). For example, the rule 14 is a one-dimensional CA, and its rule table is shown in Table 1. Thus, we have f(000)=0, f(001)=1, f(010)=1, f(011)=1, f(100)=0, f(101)=0, f(110)=0, and f(111)=0.Table 1
The truth table of Boolean function of rule 14.
xi-1xixi+1[f14(x)]ixi-1xixi+1[f14(x)]i00001000001110100101110001111110In 1980s, Wolfram proposed CA as models for physical systems which exhibit complex or even chaotic behaviors based on empirical observations, and he divided the 256 ECA (binary one-dimensional CA with radius 1) rules informally into four classes using dynamical concepts like periodicity, stability, and chaos [8–10]. However, some authors [11–14] found that some rules of Bernoulli στ-shift rules are chaotic in the sense of both Li-York and Devaney, where these rules were said to be simple as periodic by Wolfram. Rule  24 is belonging to Bernoulli στ-shift rules. Therefore, we need to research the rule 24 and to find its some new dynamical properties. The rest of the paper is organized as follows. In Section 2, the Boolean function of rule 14 is also presented, and the expressions of its attractors are given. In Section 3, the dynamical behaviors of rule 14 are studied. In Section 4, characteristic function is used to describe that all points fall into Bernoulli-shift map after several iterations under rule 14, and Lameray diagram is used to show clearly the iterative process of an attractor. Section 5 presents some conclusions.


## 2. Preliminaries

For simplicity, some notations about symbolic dynamics can refer to [11, 14].In this paper, we will use some notations about CA as follows.Chua et al. [15] mentioned that each rule has three globally equivalent local rules determined by three corresponding global transformations, namely, left-right transformation T†, global complementation T̅, and left-right complementation T*. Each equivalence class is identified by εmκ, where κ is complexity index, and m is index of κth class. In [16], the authors presented that 112 rules of 256 local rules were Bernoulli στ-shift rules. Each of the 112 Bernoulli στ-shift rules has an ID code BN[α,β,τ], where α denotes the number of attractors of rule N, β denotes the slope of the Bernoulli στ-shift map, and τ denotes the relevant forward time-τ. Hence, the space-time evolution of any one of the 112 rules on their attractors can be uniquely predicted by two parameters: β=±2σ and τ. For example, the attractors of rule 14 are (β=-1/2, σ=-1, τ=1) and (β=2, σ=1, τ=1).It follows from [17] that the Boolean function of rule 14 is(2.1)[f14(x)]i=x̅i-1⋅xi⊕x̅i-1⋅x̅i⋅xi+1,
for ∀x∈SZ, i∈Z, where “·”, “−”, and “⊕” stand for “AND”, “NOT”, and “XOR” logical operation, respectively. Sometimes, “·” is omitted for simplicity. The truth table of Boolean function of rule 14 is shown in Table 1.The subsets denoted byΛ114, Λ214 are derived from the parameters of rule 14: β=-1/2, σ=-1,  and   τ=1 and β=2, σ=1,  and τ=1, respectively, that is,(2.2)Λ114={x∈SZ∣[f14(x)]i=x̅i-1,∀i∈Z},Λ214={x∈SZ∣[f14(x)]i=xi+1,∀i∈Z}.


## 3. Dynamical Behaviors off14 on Two Subsystems

In this section, we investigate the complexity and chaotic dynamic behaviors off14. In order to give our results, some definitions need be introduced.Definition 3.1 (see [18]).
A square{0,1} matrix A is irreducible if for every pair of indices i and j, there is an n such that Aijn>0.Definition 3.2 (see [18]).
A square{0,1} matrix A is aperiodic if there exists N, such that Aijn>0, n>N, ∀i,j.Definition 3.3 (see [18]).
Suppose thatg:X→Y is a continuous mapping, where X is a compact topological space. g is said to be topologically mixing if, for any two open sets U,V⊂X, ∃N>0, such that gn(U)∩V≠∅, ∀n≥N.Definition 3.4 (see [13]).
Let(X,f) and (Y,g) be compact spaces, we say f and g are topologically conjugate if there is a homeomorphism h:X→Y, such that h∘f=g∘h.Based on the above definitions, we investigate the complexity behaviors off14 on two subsystems as follows.Proposition 3.5.
For rule 14, there exists a subsetΛ114⊂SZ which satisfies f14|Λ114=ς114∘T̅|Λ114=Γ14|Λ114 if and only if   ∀x=(…,x-1,x0,x1,…)∈Λ114, and  xi-1, xi, and xi+1 cannot be 0 simultaneously, ∀i∈Z.Proof.
(Necessity) Suppose that there exists a subsetΛ114∈SZ such that f14|Λ114=Γ14|Λ114, then ∀x=(…,x-1,x0,x1,…)∈Λ114, and we have [f14(x)]i=x̅i-1,∀x∈Z.
Ifxi=1, then x̅i-1xi⊕x̅i-1x̅ixi+1=1⊕xi-1⊕0=x̅i-1, so we get xi-1=0,xi+1=0; xi-1=0, xi+1=1;   xi-1=1, xi+1=0;   xi-1=1,  xi+1=1; if  xi=0, then x̅i-1xi⊕x̅i-1x̅ixi+1=0⊕x̅i-1xi+1, so we get xi+1=1, xi-2=1; if  xi-1=1, then xi+1=1 or xi+1=0.
(Sufficiency) Suppose that there exists a subsetΛ114⊂SZ, ∀x∈Λ114,  xi-1,xi, and xi+1 cannot be 0 simultaneously, ∀i∈Z. This yields that xi-1+xi+xi+1=1. Thus, (xi-1+xi+xi+1)⊕xi-1=x̅i-1, namely,  x̅i-1xi⊕x̅i-1x̅ixi+1=x̅i-1. Therefore, we have proven that  f14(x)=Γ14(x), ∀x∈Λ114.Remark 3.6.
A condition of bit strings according to Bernoulliστ-shift evolution under f14 is obtained in Proposition 3.5. From Proposition 3.5, we can know that a bit string belonging to Λ114 is evolved on the basis of shifting the bit string to the right by 1 bit and then complementing (changing 0 to 1 and changing 1 to 0) to obtain the next bit string after one iteration under f14.Remark 3.7.
From the definition of subsystem, we know that(Λ114,f14) are subsystems of (SZ,f14).Proposition 3.8.
Γ14=ς14∘T̅=T̅∘ς14.Proposition 3.9.
ς14:SZ→SZ and Γ14:SZ→SZ are not topologically conjugate.
(Λ114,ς14) is topologically mixing if and only if (Λ114,Γ14) is topologically mixing.
The topological entropyent(ς14|Λ114)=ent(Γ14|Λ114).Proof.
(a) Suppose thatς14 and Γ14 are topologically conjugate, we give a proof by contradiction. Since ς14 and Γ14 are topologically conjugate, then there exists a homeomorphism h such that h∘ς14=Γ14∘h, so we have h∘ς14=T̅∘ς14∘h. Because of h∘ς14=ς14∘h, then we obtain that T̅ is identical map, which leads to a contradiction.
(b) Let any nonempty open setsU,V⊂Λ114.
(Sufficiency) Assume thatΓ14|Λ114 is topologically mixing, then there exists N1>0, such that (Γ14|Λ114)n(U)∩V≠∅, ∀n≥N1. Since T̅ is a homeomorphism, T̅(V) is also a nonempty open set in Λ114, hence there exists N2>0, such that (Γ14|Λ114)n(U)∩T̅(V)≠∅, ∀n≥N2. Therefore, T̅-1((Γ14|Λ114)n(U)∩T̅(V))≠∅, ∀n≥N2. Then, we show that there exists a N>0 such that (ς14|Λ114)n(U)∩V≠∅, ∀n≥N. Let N=max(N1,N2).
(i)
Ifn=2k,k∈Z+, then
(3.1)(ς14∣Λ114)n(U)∩V=T̅n∘(ς14∣Λ114)n(U)∩V=T̅∘ς∣Λ114∘⋅∘T̅∘ς∣Λ114︸n=2k(U)∩V=(Γ14∣Λ114)n(U)∩V≠∅.(ii)
Ifn=2k+1, k∈Z+, then
(3.2)(ς14∣Λ114)n(U)∩V=T̅-1∘T̅((ς14∣Λ114)n(U)∩V)=T̅-1∘(T̅∘(ς14∣Λ114)n(U)∩T̅(V))=T̅-1∘((Γ14∣Λ114)n(U)∩T̅(V))≠∅.
(Necessity) Suppose thatς14|Λ114 is topologically mixing, then there exists an N1>0, such that (ς14|Λ114)n(U)∩V≠∅, ∀n≥N1. Since T̅ is a homeomorphism, T̅(U) is also a nonempty open set in Λ114, hence for open sets T̅(U) and V, there exists an N2>0, such that (ς14|Λ114)n∘T̅(U)∩V≠∅. Let N=max(N1,N2).(i)
Ifn=2k,k∈Z+, then
(3.3)(Γ14∣Λ114)n(U)∩V=T̅n∘(ς14∣Λ114)n(U)∩V=(ς14∣Λ114)n(U)∩V≠∅.(ii)
Ifn=2k+1, k∈Z+, then
(3.4)(Γ14∣Λ114)n(U)∩V=T̅∘(ς14∣Λ114)n(U)∩V=(ς14∣Λ114)n∘T̅(U)∩V≠∅.
(c)(Γ14|Λ114)2=(T̅∘ς14|Λ114)2=(T̅)2∘(ς14|Λ114)2=(ς14|Λ114)2.
Hence,ent(ς14|Λ114)=ent(Γ14|Λ114). The proof is complete.Because off14|Λ114=Γ14|Λ114, the following corollaries are immediate.Corollary 3.10.
ς14|Λ114 and f14|Λ114 are not topologically conjugate.Corollary 3.11.
(Λ114,ς14) is topologically mixing if and only if (Λ114,f14) is topologically mixing.Corollary 3.12.
The topological entropyent(ς14|Λ114)=ent(f14|Λ114).Remark 3.13.
By Proposition3.5, we know that the determinative block system of Λ114 is P1={r0,r1,r2,r3,r4,r5,r6}, where r0=(001), r1=(010), r2=(011), r3=(100), r4=(101), r5=(110), and r6=(111). We have Λ114=ΛP1.Letϖ1={(rr′)∣r=(b0b1b2),r′=(b0′b1′b2′)∈P1,∃1≤j≤2 such that bj≠bj-1′}. ϖ1 is considered as the excluded block system [19] Λϖ1, where Λϖ1={r=(…r-1,r0,r1…)∈P1∣ri∈P1,riri+1⊀ϖ1,∀i∈Z}. Obviously,  ς14:Λϖ1→Λϖ1, ς14(…,r-1r̂0r1,…)→(…,r̂-1r0r1,…). Therefore, it is easy to calculate the transition matrix B1 of the ς|Λϖ1 as(3.5)B1=[0110000000110000000111000000011000000011000000011],
where B1=(Bij1)|P1|×|P1|(3.6)Bij1={1,rirj≺ϖ1,0,else.Obviously,B1 is a square {0,1} matrix. A square {0,1} matrix corresponds to a directed graph. The vertices of the graph are the indices for the rows and columns of B1. There is an edge from vertex i to vertex j if Bij1=1. A square {0,1} matrix A is irreducible if and only if the corresponding graph is strongly connected. If ΛA is a two-order subshift of finite type, then it is topologically mixing if and only if A is irreducible and aperiodic [18].We give the corresponding graphG114 of matrix B1 in Figure 1, where vertices are the elements of set P1. It is obvious that G114 is a strongly connected graph.Figure 1
The corresponding graphG114 of the matrix B1.Carefully observing Figure1, we find that there are several strongly connected subgraphs: r0→r1→r3→r0, r0→r1→r4→r1→r3→r0, r0→r2→r5→r3→r0, r0→r2→r6→r5→r4→r1→r3→r0,  r1→r4→r1, r2→r5→r4→r2, r2→r6→r5→r4→r2, r6→r6, and so forth. The elements of ΛP114 will be composed by all vertices of those strongly connected subgraphs, respectively. For example, if  x1∈ΛP114, x1 is composed by vertices of subgraph r1→r4→r1, then we have r0,r2,r3,r5, and r6⊀x1, and all vertices of the subgraph will occur in x1 if |x1|=2k, k=1,2,…. If x2∈ΛP1142 and x2 is composed by vertices of subgraph r2→r5→r4→r2, then we have r0,r1,r3, and r6⊀x2, and all vertices of the subgraph will occur in x2 if |x2|=3k. Therefore, we can deduce the elements of set Λ114 via the corresponding strongly connected graph of matrix B1.Based on the above analysis, we have the following proposition.Proposition 3.14.
(a)ς14:Λ114→Λ114 and ς14:Λϖ1→Λϖ1 are topologically conjugate.
(b)ς14|Λ114 is topologically mixing.
(c) The topological entropyent(ς14|Λ114)=0.6094.Proof.
(a) Define(3.7)h:Λ114⟶Λϖ1,x=(…,x-1,x*0,x1,…)⟼(…,r-1,r*0,r1,…),
where ri=(xixi+1xi+2), ∀i∈Z. In fact, by the definition of Λϖ1, we have h(x)∈Λϖ1, ∀x∈Λ114; thus, h(Λ114)⊆h(Λϖ1). Then, it is easy to check that h is homeomorphism and h∘ς14|Λ114→ς14|Λϖ1∘h. Therefore, ς14|Λ114 and ς14|Λϖ1are topologically conjugate.
(b) Because(B1)n>0, ∀n≥4,  the transition matrix B1 of subshift of finite type ς is irreducible and aperiodic. By [18, 19], ς14|Λ114 is topologically mixing.
(c) Because two topological conjugate systems have the same topological entropy, and the topological entropyς14 on Λϖ1equals logρ(B1), where ρ(B1) is the spectral radius of the transition matrix B114  of the subshift Λϖ1. So ent(ς14|Λ114)=logρ(B1)=0.6094.Remark 3.15.
By Corollaries3.11 and 3.12, we know that (Λ114,f14) is topologically mixing and ent(f14∣Λ114)=0.6094.Theorem 3.16.
f14 is chaotic in the sense of both Li-Yorke and Devaney on Λ114.Proof.
It follows from [19] that the positive topological entropy implies chaos in the sense of Li-Yorke, and a system with topologically mixing property has chaotic properties in different senses such as Devaney. Therefore, rule N=14 possesses very rich and complicated dynamical properties on Λ114.Proposition 3.17.
For rule 14, there exists a subsetΛ214⊂SZ which satisfies f14|Λ214=υ14|Λ214 if and only if  ∀x=(…,x-1,x0,x1,…)∈Λ214, and xi-1, xi, and xi+1 have the following relations:(i)
ifxi=1, then xi-1=0, xi+1=1, and xi+2=0;    xi-1=1, xi+1=0,andxi+2=0,(ii)
ifxi=0, then xi-1=0, xi+1=0;    xi-1=1,xi+1=0;    xi-1=0, xi+1=1, and xi+2=1.
LetP2={r0,r1,r2,r3,r4} be a new state set, where r0=(000), r1=(001), r2=(011), r3=(100), and  r4=(110).Remark 3.18.
From the definition of subsystem, we know that(Λ214,f14) is subsystem of (SZ,f14).
The transition matrix of subshift(Λ2142,υ14) is
(3.8)B2=[1100000100000011100000010].
We give the corresponding graphG214 of matrix B2 in Figure 2, where vertices are the elements of set P2.Figure 2
The corresponding graphG214 of the matrix B2.Proposition 3.19.
(a)f14|Λ214 is topologically mixing.
(b) The topological entropyent(f14|Λ214)=0.3223.Theorem 3.20.
f14 is chaotic in the sense of both Li-Yorke and Devaney on Λ214.Theorem 3.21.
For rule 14, there exist fixed points off14.Proof.
A example is given as follows. Let(3.9)y=(…0,1,0,1,0,1︸repetition of(0,1),0,1,0*,1,0,1,0,1,0,1…︸repetition of(0,1)).
By Table 1, we have
(3.10)f14(y)=(…0,1,0,1,0,1︸repetition of(0,1),0,1,0*,1,0,1,0,1,0,1…︸repetition of(0,1))=y.
Therefore, there exists a set of fixed points of rule 14.Remark 3.22.
By Theorem3.21, we know that rule 14 has garden of Eden [20] (An bit string is said to be a garden of Eden of rule N if and only if it does not have a predecessor under the local rule transformation fN) in the finite case. By definition of garden of Eden, the incoming and outgoing bit strings are the same in a garden of Eden, while the basin of attraction of an attractor Λ must contain, at least, one point not belonging to Λ. However, in this paper, we consider garden of Eden as a kind of special attractor. Then, we find that (000), (001), (010), (011), (100), (101), (110), or (111)≺Λ14=Λ114∪Λ214. Furthermore, we guess that all initial bit strings after sufficient iterations will belong to Λ14 under rule f14.


## 4. Characteristic Function of Rule 14

First, we give a definition on global characteristic function [16]. Given any local rule N, and binary configuration x=[x0x1·xI-1xI] for CA, where xi∈{0,1}, then we can uniquely associate the Boolean string x with the binary expansion of a real number 0•x0x1·xI-1xI on the unit interval [0,1],(4.1)x=[x0x1⋅xI-1xI]⟼ϕ=0•x0x1⋅xI-1xI,
where ϕ=∑i=0I2-(i+1)xi is the decimal form of Boolean string x=[x0x1·xI-1xI]. The CA’ characteristic function χN of rule N is defined as(4.2)χN:Q[0,1]⟶Q[0,1],i.e.ϕn=χN1(ϕn-1),
where Q denotes rational numbers. By [19], the express of characteristic function of rule 14 is(4.3)χ141=∑i=0Iδ[-2xi-1+xi+xi+1-12]2-(i+1),
where
(4.4)δ{w}={1,w>0,0,w≤0.In order to transform every concrete bit string into abstract decimal digit, we use characteristic functionχN. Next, we plot the characteristic function diagram for rule 14. We choose I=14. Figure 3 describes that all points fall into Bernoulli-shift map after eight iterations under rule 14, which shows that Λ14 is global attractor of f14. The phenomenon also shows that the prediction in Remark 3.22 is correct. Two sets Λ114  and Λ214 can also be found in Figure 3. The dots in the two straight lines, whose slope is -1/2, are in the set Λ114; the dots in the two straight lines, whose slope is 2, are in the set Λ214.Figure 3
All points fall into Bernoulli-shift map after seven iterations under rule 14, whereI=13.Two isles of Eden are shown in Figure4. We find that the bit string y=(…,0,1,…︸repetition of(0,1)) is isle of Eden, when the length |y| is even. Some attractors are shown in Figure 5. Figure 5(a) shows that the period of attractor is 1; Figure 5(b) shows that the period of attractor is six, where β=2, σ=1, and τ=1; Figure 5(c) shows that the period of attractor is six, where β=-1/2, σ=-1, and τ=1; Figure 5(d) shows that after two iterations, the initial string is attracted. We find that the possible periods of attractors are 1 and 6 if  I=5. By Proposition 3.5, the attractors of Figures 4 and 5(c) belong to Λ114. By Proposition 3.17, the attractors of (a), (b), and (d) belong to Λ214. There is a interesting phenomenon, that is, Figure 5(d), where one iteration accords with Proposition 3.5; however, the two iterations accord with Proposition 3.17, and the attractor belongs to Λ214. The phenomenon shows that these two propositions can switch in some situation. The bit string of attractor in Figure 5(c) corresponds with strongly connected subgraph r0→r2→r5→r4→r1→r3→r0 in Figure 1.Figure 4
Two isles of Eden are shown, where|x|=6.Some attractors of rule 14, whereI=5, and the white pixel stands for 0 and black for 1.
(a)(b)(c)(d)Next, we use Lameray diagram [21] to present our attractors. The diagrams show clearly the iterative process of attractors. The evolution of characteristic function of period-5 attractor is shown in Figure 6, where I=4, and the values of characteristic function are 0.0938, 0.1875, 0.3750, 0.7500, and 0.5313, respectively. The five points fall into the time-1 map (ϕn=χN(ϕn-1)) in Figure 5. Then we can associate this particular period-5 attractor of rule 14 as a period-5 point of a continuous map f:[0,1]→[0,1] which we know that it is chaotic because “period-5” implies chaos based on Li-York theorem [22] and Sarkovskii theorem [23]. According to Sarkovskii theorem, period-5 implies that the number of periods of f14 are infinite.Figure 6
The evolution of characteristic function of the period-5 attractor, where the values of characteristic function of the attractor are 0.0938, 0.1875, 0.3750, 0.7500, and 0.5313, respectively.In recent years, associative memory was researched in many papers [24, 25]. It is obvious that rule 14 can be used in associative memory. By strongly connected graph of rule 14, we can get the elements on its attractors. Then, we can choose a bit string which belongs to an attractor as memory pattern. For example, bit string 110000 in Figure 5(b) can be chosen as a memory pattern. Since there are infinite orbits, the storage capability is very large. The associative memory model provides a solution to problem where time to recognize a pattern is independent of the number of patterns stored.


## 5. Conclusion

In this paper, the dynamical behaviors of rule 14 of global equivalence classε131 in ECA, where rule 14 is Bernoulli στ-shift rule, are carefully investigated from, the viewpoint of symbolic dynamics. We derive the conditions according to Bernoulli στ-shift evolution for rule 14. Then, we prove that rule 14 is chaotic in the sense of both Li-Yorke and Devaney on their attractors, respectively. We use diagrams to explain the attractor of rule 14, where characteristic function and Lameray diagram are used to describe that all points fall into Bernoulli-shift map after several iterations and to show clearly the iterative process of an attractor, respectively.



---

*Source: 258309-2012-04-22.xml*