1. Introduction
The dynamics of cellular automata have been investigated widely in mathematics, physics and theoretical computer science. Presently, there are many constructions of cellular automata in metric Cantor space of right infinite words
, which are:
positively expansive and topologically conjugated to a one-sided full shift or a one-sided subshift of finite type (SFT) [
1,
2]
bijective, expansive and topologically conjugated to a two-sided full shift or a two-sided SFT [
3–
5]
strongly transitive with non-zero memory [
6].
The dynamics of transitive cellular automata in metric Cantor spaces
and
has been intensively investigated [
6–
9]. It has been established that any positively expansive cellular automaton in
is topologically conjugated with a one-sided, topologically mixing SFT [
1,
2], is non-injective [
1,
10,
11], E-chaotic [
12] and has topological entropy
[
1]. In particular, a one-sided full shift defined over n−elementary alphabet A is a positively expansive cellular automaton and has topological entropy log(n).
In our papers [
13–
15], for any integer n ≥ 2 we have presented a construction of non-injective, D-chaotic [
16] cellular automaton
, which has radius r = 1, continuum of fixed points and topological entropy equal to log(n). This means that it can achieve the topological entropy of any fixed positively expansive cellular automaton in
. Cardinality of the set of periodic points with the fixed period m ≥ 1 is an invariant of topological conjugacy [
17] which asserts that for any integer n ≥ 2 an automaton
, is not topologically conjugated to any positively expansive cellular automaton defined in
[
1,
2]. Additionally, a positively expansive cellular automaton defined in
need not be topologically conjugated to a one-sided full shift [
2,
18]. Hence in this context it is natural to ask whether there exists in
a non-injective, D-chaotic cellular automaton with continuum of periodic points with a fixed period m ≥ 1 and topological entropy log(n) for an integer n ≥ 2 which is not topologically conjugated to
.
In the paper we present a cellular automaton
with radius 1 defined for any prime number p. We prove that this automaton is not injective, is D-chaotic, has no fixed points, but has continuum of periodic points with the period 2 and topological entropy log(p). Thus we obtain a positive answer for the above question and additionally for any integer n ≥ 2, we are able to construct a cellular automaton
, which has the listed properties of
, but its topological entropy is equal to log(n). In fact, if n = p, then F
n = F and A
n = B. For a non-prime integer n ≥ 2 and p any fixed prime from the factorization of n (for example the least one) we have n = p · k. For this k a one-sided full shift σ, defined over k−elementary alphabet, is a topologically mixing cellular automaton with radius r = 1, which has topological entropy log(k) and k fixed points. Now basing on the properties of F for a prime p, we conclude from Theorem 2 in [
19] and Theorem 7.10 in [
20] that the cartesian product F ×σ is topologically conjugated to a cellular automaton
, which has the expected properties.
The obtained results coincide with research directions pointed out by papers [
1,
2,
6,
7,
11,
13–
15,
18].
2. Preliminaries
This section contains all notions and notations to be used in the paper. We denote by ℕ, ℤ, ℝ the sets of non-negative integers, integers and real numbers, respectively. #Y stands for the cardinality of a set Y. A finite (non-empty) word w over an alphabet B, that is a finite and non-empty set, is a function
defined on a discrete interval [0, k], where k ≥ 0. The set of all such defined words with concatenation of words is a free semigroup (B+, ·). The length of a word w, denoted by |w| is equal to the cardinality of its domain. The set of all words in B+ with the length equal to n is denoted Bn. (B∗, ·) stands for a free monoid of words after the empty word λ , the unit element of concatenation, is added. By the definition |λ| = 0 and B0 = {λ}. A right infinite word is a function on ℕ or equivalently on a discrete interval [0, ∞) with values in B. The set of all right infinite words is denoted by
. It is convenient to extend naturally concatenation to pairs of words in
with values in
. We will use also in the sequel words defined on finite discrete intervals of the form I = [i, j], where i ≤ j, are non-negative integers. If i = j, then we denote such degenerated interval by [i, i], [i] or {i}. For two discrete intervals I, J such that J ⊂ I and for a word u defined on I we denote by uJ the restriction of u to J.
In the sequel we assume that #B ≥ 2.
We define metric
putting for any
where i = min{j ≥ 0 : x(j) ≠ y(j)}.
The obtained topological space
is a Cantor space [
6,
10,
21] and the family of balls
is its base. For
, every open ball in
with the radius 2
−n, is of the form
, where
w =
x[0,n] ∈
Bn+1. We denote by
Xω an infinite concatenation of a set of words
X.
Let us fix
and assume that there is given a mapping
F′ : Br+1 →
B. For any
,
there exists
w ∈
Br+1 such that
w(
j) =
x(
i +
j) for any
j ∈ [0,
r]. We put in this case
F′(
x[i,i+r]) =
F′(w). A mapping
such that
F (x)(i) =
F′ (x[i,i+r]) for any
and
is referred to as one-sided cellular automaton [
1,
22].
F′ : Br+1 → B is called the local rule of
F. Any cellular automaton
F is continuous. If for
u ∈
B+, it holds |
u| >
r, then we define
F′(u) putting
F′ (u)(i) = F′(u[i,i+r]) for any
i ∈ [0, |
u| −
r). If
and for any
w ∈
Br, b ∈
B there exists exactly one
a ∈
B such that
F′(
aw) =
b (
F′(
wa) =
b), then
F is referred to as left (right) permutative [
1,
21]. If
is left (right) permutative then it is surjective [
23]. A cellular automaton
F is right-closing, if for any
equalities:
F (
x) =
F (
y),
x[0,i] =
y[0,i] for some
i ≥
r, imply
x =
y (compare [
24]).
Assume, in what follows that
S is a closed subset of
. Let ψ :
S →
S be a continuous mapping. A pair (
S, ψ) is referred to as a symbolic dynamical system, SDS in the abbreviated form [
21]. A point
y ∈
S is periodic for ψ if and only if there exists
such that ψ
n(
y) =
y. The set of all periodic points of ψ is denoted Per(ψ). If ψ(
y) =
y, then
y is a fixed point of ψ. If there exists ε > 0 such that for any
x,
y ∈
S,
y ≠
x there exists
such that
d(ψ
n(
x),
ψn(
y)) ≥ ε, then ψ is positively expansive. A mapping ψ is transitive, if it is surjective and for any not empty open sets
U,
V ⊂
S there exists an integer
such that
U ∩ ψ
−n(
V) ≠ θ [
1,
20]. If additionally
S is infinite and ψ :
S →
S is surjective then SDS (
S, ψ) is referred to as D-chaotic (or chaotic in the Devaney’s sense) [
16,
21,
25] if and only if
the set Per(ψ) is dense in S, that is for any y ∈ S, and n ∈ N, Per(ψ) ∩ K(y, 2−n) ≠ θ (K(y, 2−n) ⊂ S ),
for any
, K(y, 2−n) ⊂ S, and for any K(x, 2−n) ⊂ S, there exists
such that K(y, 2−n) ∩ ψ−m(K(x, 2−n)) ≠ ∅, that is ψ : S → S is transitive.
If (
S, ψ) is D-chaotic and additionally ψ :
S →
S is positively expansive, then (
S, ψ) is referred to as E-chaotic [
12]. In particular a cellular automaton
is SDS. A mapping π :
is a surjective SDS morphism if it is surjective, continuous and
π ◦
F = ψ ◦ π. In this case (
S, ψ) is a factor of
. If additionally π is a bijection, then it is a topological conjugacy. In this case SDS (
S, ψ),
are topologically conjugated.
Assume that σ(
x)(
i) =σ′(
x[i,i+1]) =
x(
i + 1) for any
and
. In such a case a cellular automaton
is called a one-sided full shift. If S is a closed subset of
and σ(
S) ⊂
S, then a SDS (
S, σ) is called a one-sided subshift [
10,
21].
Two objects are associated with a cellular automaton
defined by a local rule
F′:
B2 →
B. The first, a one-sided subshift (
SF, σ) where
[
6,
26]. The second, a surjective SDS morphism
[
1]. In such a case topological entropy
of SDS
is given by the equality
[
1,
22,
27].
3. Cellular Automaton F
This section starts from the introduction of a one-sided cellular automaton F, whose form depends on the chosen prime number p. The main objective of the section is to describe its basic properties.
In the sequel p is a fixed prime number. We use the following notation:
We introduce a mapping φ′ : B → A, defining φ′(a) = 2 ⌊a/2⌋ , where ⌊ ⌋ denotes the floor function. Notice that φ′(a) is the closest integer in A not greater than a ∈ B.
Define a function f′ : B2 → E such that f′(a, b) = f′(a, φ′(b)), f′(a, b) ≠ f′( φ′(a)+(a+1)mod 2, b) for any a, b ∈ B. We define a cellular automaton
with a local rule G′ : A2 → A given by G′(a, b) =2 ((a/2 + b/2) mod p) for any a, b ∈ A.
The main object of our considerations in [
13–
15] are properties of some cellular automata
having a local rule
F′:
B2 →
B of the form
F′ (
a, b) =
f′(
a, b)+
G′(φ′ (
a), φ′(
b)).
Notice that this form of
F′:
B2 →
B does not guarantee transitivity of
(see Example 1 in [
15]). Observe that a cellular automaton
is right-permutative [
21] and thus surjective and positively expansive [
1]. Additionally it is a factor of a linear and transitive cellular automaton defined on
[
26,
28].
As a continuation of our research we consider, in what follows, a cellular automaton
of the same type. Its local rule F′: B2 → B is defined by a mapping f′ : B2 → E of the form: f′(a, b) = (a + 1 + [φ′(a)/2 + q][φ′(b)/2 + 1 − q]) mod 2 for q = b(p + 1)/2c mod 2 and p ≠ 3, f′(a, b) = (a + ρ(a)) mod 2 for
and p = 3.
We extend φ′: B → A to a morphism φ′ : B∗ → A∗. Additionally we introduce
putting φ(x) = y if and only if for any
for every
.
In a later part of this section we present basic properties of cellular automata
,
and relationships between them. It follows just from the definition that the dynamics of
is closely related to the dynamics of
. As a consequence of this dependance there are some generalized properties from [
15] proved in the following lemma.
Lemma 1. For the defined above mappings F, G, φ′, φ it holds:
φ′ : B∗ → A∗ is surjective and |φ′(u)| = |u| for any u ∈ B∗.
is a surjective SDS morphism.
for any a ∈
B we havefor any b ∈ A, there exists a unique c ∈ B such that for every b′ ∈ φ′−1(b), it holds F′(a, b′) = c,
φ′({F′(ab) : b ∈ A}) = A.
if and for any k ∈ [0, n) there exists c ∈ A such that F′(y(k)c) = y(k + 1) ∈ B then there exist 2n words w ∈ Bn and exactly one word φ′(w) ∈ An such that y =y(0) · F′(y(0) φ′(w))(0) · F′2(y(0) φ′(w))(0) · … · F′n(y(0)φ′(w))(0) = y(0) · F′(y(0)w)(0) · F′2(y(0)w)(0) · … · F′n(y(0)w)(0).
Proof. Assertions of Points 1 and 2 are obvious.
From these assertions and the fact that F′(a φ′(b)) = F′(ab) for any a, b ∈ B follows directly Point 3.
We prove the statement 4. We start for n = 3. According to Point 3 there are two possibilities of y1(l) ∈ B, one of φ′(y1(l)) ∈ A for l = 0, and then again one of y1(l) ∈ B for any l ∈ (0, 2] such that
As the result we obtain a word y1 ∈ B3. Analogically we obtain a subsequent word y2 ∈ B2.
According to Point 3. there are two possibilities of y2(l) ∈ B and one of φ′(y2(l)) ∈ A for l = 0, and then again one for y2(l) ∈ B for any l ∈ (0, 1] such that
Analogically we construct the last, in this case, word y3 ∈ B. According to Point 3, there are two possibilities of y3(0) ∈ B and one of φ′(y3(0)) ∈ A such that F′(y2(0)y3(0)) = y2(1) ∈ B.
Finally we obtain exactly one word φ′(w) ∈ A3 and 23 words w = y1(0)y2(0)y3(0) ∈ B3.
Now we assume that the assertion of the Point 4 is true for n ≥ 3. Assume that z ∈ Bn+2 and for any k ∈ [0, n] there exists c ∈ A such that F′(z(k)c) = z(k + 1) ∈ B. Let us assume that y = z[0, n] ∈ Bn+1. It follows from the assumption that the assertion of Point 4 is true for y.
Now, Point 3 implies that there is one possibility of a0 ∈ B such that
and then for any k ∈ [1, n − 1] there is one possibility of ak ∈ B such that
Finally Point 3 implies that there are two possibilities of an ∈ B and one possibility of φ′(an) ∈ A such that
Now, from the assumption there exist 2n+1 words wan ∈ Bn+1 and exactly one word φ′(wan) ∈ An+1 such that
□
The following lemma simplifies the description of infinite words—elements of a one-sided subshift (SF, σ).
Lemma 2.
Proof. Inclusion “⊂” is obvious. The inclusion in the opposite direction follows according to Point 4 of Lemma 1. □
The obtained result simplifies the computation of a topological entropy
[
1,
22] of a cellular automaton
.
The following lemma presents basic properties of F. Notice that all properties listed in the below lemma except for left-permutativity, are invariants of a topological conjugacy.
Lemma 3. Cellular automaton F
has topological entropy,
is left-permutative, surjective and not injective,
has continuum of periodic points with the period 2,
has no fixed points.
Proof. Lemma 2 assures that y ∈ SF if and only if for any
there exists c ∈ A such that F′(y(i)c) = y(i + 1). Now from Lemma 1 we have for any a ∈ B, #{F′(ac) : c ∈ A} = p. Hence starting from these #B words of the length 1, in the subsequent steps from 1 to n it is possible to construct exactly #B · pn words z ∈ Bn+1 fulfilling the following condition: for any i ∈ [0, n − 1] there exists c ∈ A such that F′(z(i)c) = z(i + 1). According to the above remarks and the definition of topological entropy of SDS
the equality of point 1. holds.
For the proof of Point 2, notice that just from the definition of F′ : B
2 → B, for any fixed b, c ∈ B, there exists exactly one
a = φ′(
a) +
amod 2 ∈
B such that
F′(
ab) =
c. Hence
is left-permutative [
21] and surjective [
23].
To prove that F is not injective observe that for p = 2, we have F (1111⋯) = F (3333⋯) = 000⋯, for p = 3, we have F (242424⋯) = F (424242⋯) = 00000⋯.
Now consider p ≥ 5 and assume that a = p − 1 and b = p + 2. Thus
Notice that p mod 2 = 1 and [(p + 1)/2 + 1 − q] mod 2 = 1. If q = 0, then ((p − 1)/2) mod 2 = 1 and consequently F′(ab) = 0. If q = 1, then ((p − 1)/2) mod 2 = 0 and consequently F′(ab) = 0.
Similarly for a = p + 2, b = p − 1, we obtain F′(ab) = 0 for q = 0 or q = 1.
Finally, if
, x′(2i + 1) = x(2i) = p − 1, x′(2i) = x(2i + 1) = p + 2 for any
, then
.
Thus in these three cases F is not injective for any prime number p.
For Point 3 observe that F′(ac) = 1 − a for any a, c ∈ E. Hence, if
, then F 2(x) = x. Observe that the cardinality of the set
is equal to continuum.
Finally for the assertion number 4. let us assume that there exist a, b, c ∈ B,
such that F (x) = x. Hence F′(ab) = a. From Points 1 and 2 in Lemma 1, we have G′(φ′(ab)) = φ′(a) and (φ′(a) + φ′(b)) mod 2p = φ′(a). Thus φ′(b) = 0 and b ∈ E. Analogically F′(bc) = b and G′(φ′(bc)) = φ′ (b), (φ′(b) + φ′(c)) mod 2p = φ′(b).
Hence φ′(c) = 0 and consequently b, c ∈ E.
Just from the definition of a local rule we have F′(bc) = 1 − b for any b, c ∈ E which creates the contradiction. □
If a ∈ B, w ∈ B+, then F′(aw) = F′(a φ′(w)). Additionally, if a, a′∈ B, a 6= a′, w ∈ B+, φ′(a) = φ′(a′) (φ′(a) ≠ φ′(a′)), c = F′(aw)(0), c′ = F′ (a′w)(0), then c ≠ c′, φ′(c) = φ′(c′) (φ′(c) ≠ φ′(c′)).
These properties are generalized in the lemma below, which can be proved exactly in the same way as its counterparts in [
14,
15].
Lemma 4. (1) if a ∈ B, w ∈ B+,
, a0 = a, ai = F′(ai−1G′i−1(φ′(w)))(0) for i ∈ [1, n], then ak = F′k(aw)(0) for any k ∈ [0, n],
(2) if w ∈ B+,
, a, a′ ∈ B and for any k ∈ [0, n] :
a′ ≠ a, φ′(a) = φ′(a′), F′k(aw)(0) = c ∈ B, F′k(a0w)(0) = c′ ∈ B, then c′ ≠ c, φ′(c) = φ′(c′),
φ′(a) ≠ φ′(a′), F′k(aw)(0) = c ∈ B, F′k(a′w)(0) = c′ ∈ B, then φ′(c) ≠ φ′(c′).
Similarly as in [
14] the above result could be used in the proofs of Lemmas 7, 8, 10, 11 and 13.
It is not difficult to show that for any a, b ∈ A,
, w ∈ A∗, |w| = pn − 1 the formula
takes values G′(ab). This implies hat the value
does not depend on a chosen word
.
Exactly such a case is presented in the following lemma and its easy, inductive proof is left to the reader.
Lemma 5. If a, b, c ∈ A, G′(ab) = c, then, w ∈ A∗, |w| = pn − 1.
Similarly as in [
14] the above result could be used in the proofs of Lemmas 7, 8, 10 and 11.
The greatest difficulty in the proof of transitivity of
(see Theorem 5.1) is the case p ≥ 5. Possibility of defining a local rule F′ : B2 → B without applying a function ⌊ ⌋ is the first step to overcome this difficulty. An alternative possibility of defining F′ : B2 → B is presented in the lemma below.
Lemma 6. (compare [14]) For p ≥ 5
and any j, k ∈ [0,
p − 1]
and αk, γ ∈ [0, 1],
F′(2k + ((j + 1 − q)(q + k) + 1 + αk)mod 2, 2j + γ) = 2((j + k)mod p) + αk.
Proof. Let
We have
Additionally
4. Transitivity of F for p ≥ 5
The main goal of this section is to prove transitivity of the cellular automaton
for p ≥ 5. We present also lemmas and some properties that lead to the justification of Corollary 14. All along this section it is assumed that p ≥ 5.
The lemma presented below can be considered as a counterpart of Lemma 5 but it is formulated for
.
In contrast to the formula for
in Lemma 5 the formula presented below for
depends on a chosen word
. The choice of
determines values of coefficients i ∈ [0, p − 1] and ik ∈ [0, 1] which occur in the formula for any k ∈ [0, p − 1].
The lemma could be proved exactly in the way as its counterpart in [
14] making use of Lemmas 1 and 4–6.
Lemma 7. Let us assume that, w ∈ B∗, |w| = pn − 1. For any j, k ∈ [0, p − 1], αk ∈ [0, 1], and some fixed i ∈ [0, p − 1], ik ∈ [0, 1],
The following conclusions can be derived from Lemma 7 for any fixed m ∈ [1, p − 1].
Under the assumptions of the lemma, if j = (i + m)mod p, b = 2(mmod p), a = 2((k + i)mod p) + (ik + 1 + αk)mod 2 for k = q and some αq ∈ [0, 1], then for the following equalities a0 = a,
for any l ∈ [1, p], we obtain al = 2((lm + q + i)mod p) + α((l−1)m+q)modp for k = ((l − 1)m + q) mod p and for any l ∈ [1, p], α((l−1)m+q) mod p = ((j + 1 − q) [q + k] + ik + 1 + αk) mod 2 for k = (lm + q) mod p and for any l ∈ [1, p−1]. Notice that in view of Point 1 in Lemma 4 and Lemma 5 to calculate al for any l ∈ [1, p], we can apply
to a word
.
A generalization of this observation leads to the lemma formulated below. The formulation is preceded by the introduction of some denotations.
We will use in the sequel the following notations: e∞(a) = a000… = a0ω, e0(a) = a, ek(a) = a0k for any a ∈ A,
, θ(d) = d mod 2 for any d ∈ B. Assume now that
, w ∈ B∗, |w| = pn − 1. Lemma 7 implies that for any j, k ∈ [0, p − 1], αk ∈ [0, 1],
for some fixed i ∈ [0, p − 1], ik ∈ [0, 1].
Now, let us fix m ∈ [1, p − 1] and j = (i + m)mod p, b = 2((j + p − i)mod p), a = 2((q + i)mod p) + (iq + 1 + αq)mod 2 for αq ∈ [0, 1]. Additionally let
,
.
Lemma 8. The following statements are true:
,
,
if s = 0, then,
Proof. The first statement is left to the reader.
From Point 1 in Lemma 4 and Lemma 5 follows that for any l ∈ [0, p − 2],
To finish the proof of Point 2, observe that the following equation holds:
Thus
The Point 3 follows according to Point 2, Lemmas 4, 5 and
Equations (1)–
(4). We have for l ∈ [1, (p − 1)/2],
For Point 4 observe that putting o = α
q, the
Equation (5) gives
for l ∈ [(p + 1)/2, p]. Consequently
.
Point 5 could be proved as above putting o = (1 + α
q)
mod 2 in the
Equation (5). □
The results proved above can be applied in the proofs of Lemmas 9, 10, 11, 13.
For a, b which fulfills exactly the assumptions introduced before Lemma 8 and for a fixed word w ∈ B∗, such that |w| = pn − 1,
, let us consider the following set
If the set is independent of choosing and fixing m ∈ [1, p − 1] (remind that in fact b depends on m) we put
and say, that the Condition (*) is fulfilled for any m ∈ [1, p − 1].
In a similar way as in [
14] the properties established in Lemma 8 give reason for an indirect proof of the lemma presented below. A contradiction is obtained by considering a system of linear equations formulated over
assuming that the Condition (*) is fulfilled for any m ∈ [1, p − 1].
Lemma 9. If, w ∈ B∗, |w| = pn − 1, then Condition (*) does not hold.
The statement of the lemma means that there exist m1, m2 ∈ [1, p − 1], m1 ≠ m2,
such that
Consequently,
there exist
, l2 ∈ [1, p] such that,
,
,
(Lemma 8, point 3)
Similarly as in [
14] the above property and Lemma 11 play a key role in the proof of transitivity of
(see Lemma 13).
A subsequent lemma, rather a technical one, can be proved exactly as its counterpart in [
14] and in the proof Lemma 4, 5 and 8 are used.
Lemma 10.
If a ∈ B, w ∈ B+, pn − 1 > |w| ≥ pn−1,
, then
If w ∈
B+,
|w| =
pn − 1,
,
thenif a ∈ B, then,
if a ∈ B,
,
for any l1 ≠ l2, l1, l2 ∈ [0,p−1], k ∈ [0, 2pn − 1], then φ′(c) ≠ φ′(c′).
It is easy to notice that for any fixed b ∈ A \ {0}, any expression of the form ek(p − 1) for some
, which occurs in the assertion of the above Lemma could be replaced by ek(b).
The same observation is true for Lemma 11.
Let us denote
for any
. Notice that, if
,
then |w| = pn.
Lemmas 4, 8 and 10 play a key role in an inductive proof of the following lemma. The proof is left to the reader.
Lemma 11. For any the following assertions are true:
for every
,
.
The result of the above lemma is used later when we prove that
is D-chaotic. For
and
, let us denote:
From Lemma 11 for any
we have
for any
and
. Since the family
is a base of
then we obtain the following corollary.
Corollary 12. Per(F) is dense in.
For
,
, c ∈ B, i ∈ [0, pn) define a word
putting for j ∈ [0, pn)
and w[i, c](j) ∈ B for j < i.
The above denotation facilities presentation of the following observations.
According to Lemma 9 Condition (*) does not hold. Thus Point 1 of Lemma 4 implies that for i ∈ [1, pn), there exist m1, m2 ∈ [1, p − 1], m1 ≠ m2,
such that
Additionally, from Lemma 11 we have
Observations made above, the possibility of choosing
and the fact that i varies in the range from i = p
n − 1 to i = 0 play an essential role in the proof of the subsequent lemma. This proof, based also on Lemmas 4, 8, 9 and 11 is analogical to the proof of its counterpart in [
14].
Lemma 13. Let us assume that
There exists
such that
Lemma 3 implies that
is surjective. Observe that the family
is a base of
and thus it is enough to prove that for any
, t,
there exists
such that tBω ∩ F −m(t′Bω) ≠ θ. From Lemma 11 we have
for any
Thus Lemma 13 implies the following corollary.
Corollary 14. Cellular automaton is transitive.
5. Main Result
This section contains the main result concerning the cellular automaton
, that is a theorem presented below. It exposes these properties of F, which are invariants of a topological conjugacy.
Theorem 15. For any prime number p the considered automaton defined over an alphabet B of 2p elements has the following properties:
is not injective,
has no fixed points,
has continuum of periodic points with period equal to 2,
has topological entropy,
is D-chaotic.
Proof. From Lemma 3 follows that F is not injective, is surjective and has no fixed points, has continuum of periodic points with period 2 and finally its topological entropy is equal to log(p) > 0.
The last assertion is proved considering two subcases.
For the first subcase assume that p ≤ 3. A form of the local rule
allows for a construction of oriented graphs having properties exactly as required in [
13,
15]. Arguing analogically as in [
13,
15] we finally obtain density of P er(F ) in
, and transitivity of F.
For the second subcase assume that p ≥ 5. From Corollary 12 P er(F ) is dense in
and Corollary 14 implies that F is transitive. Hence in any case F is D-chaotic. □
The following conclusions points out some possibilities of classification of the cellular automaton
in Cantor metric space
.
A positively expansive cellular automaton defined in
is topologically conjugated with a one-sided subshift of finite type (SFT) [
1,
2], which has no infinite set of periodic points with the period 2. Cardinality of the set of periodic points with the period 2 is an invariant of a topological conjugacy. Hence basing on Point 3 of Theorem 15 the following corollary could be derived.
Corollary 16. Cellular automaton F is not positively expansive.
Defined for any prime p, and presented in [
13–
15] a one-sided cellular automaton associated to F has continuum of fixed points and topological entropy log(p). Cardinality of the set of fixed points is an invariant of a topological conjugacy. Thus Point 2 of Theorem 15 leads to the following corollary.
Corollary 17. For any fixed prime number p, the cellular automaton F is not topologically conjugated with an associated one-sided, D-chaotic cellular automaton presented in [13–15] having continuum of fixed points and topological entropy log(p).
Below we present an example of a cellular automaton
which is not transitive. It is defined in
, by a local rule
over an alphabet B = {0, 1, 2, .…, 2p − 1} for which a mapping
defined in Section 3 is a surjective morphism SDS, F′(aφ′(b)) = F′ (ab) for any a, b ∈ B, and has the following properties:
is left permutative,
is right-closing,
is surjective and non-injective,
has no fixed points,
has continuum of periodic points with the period 2,
is non transitive.
Example 1. Let us consider
Just from the definition of F′, for any fixed b, c ∈ B there exists exactly one symbol
such that F′ (ab) = c. Hence
is left-permutative [
21] and so surjective [
23].
Additionally, if F′ (da) = F′ (db) for some d, a, b ∈ B and a 6 ≠ b, then
and F′ (ac) ≠ F′ (bc) for any c ∈ B. Thus
is right-closing and has a dense set of jointly periodic points [
24].
For p ≥ 3, if we take
, such that
then
For p = 2 we have
Additionally F′ (ac) ≠ a for any a, c ∈ B. Consequently is not injective and has no fixed points. Notice that F′ (ac) = 1 − a for any a, c ∈ E. Hence, if, then F 2(x) = x and cardinality of the set is continuum.
Just from the definition of F′ : B2 → B follows that
Hence, for any t ∈ C = A2 ∪ (B \ A)2 and t′ ∈ B2 \ C we have F′ (ts) ≠ t′ for every s ∈ B. It means, that for any t ∈ C, t′∈ B2 \ C and any integer
it holds tBω ∩ F −m(t′Bω) = ∅. It excludes transitivity of
.