Information Technology Reference
In-Depth Information
Theorem 1.
Suppose that the local rule f ofaCAA,r,f consists of a pos-
itive number n (
0
=
n ≤ |A|
2
r
+1
)
of l-admissible blocks. Then, the following
statements are equivalent:
i
)
the corresponding subshift is not trivial (S
f
=
∅);
ii
)
there exists a finite block of length n
+2
r
+1
consisting of l-admissible blocks;
iii
)
there is at least one cycle in the associated AG
f
graph.
Theorem 2.
Let AG
f
be the graph associated to the subshift generated by the
CA A,r,f. Then |S
f
|
=+
∞ if at least one of the following conditions holds:
i
)
there exists a spatially aperiodic configuration x ∈ S
f
;
ii
)
there exist two cycles in the graph AG
f
differently labelled and connected by
at least one edge;
Proposition 2.
If the AG
f
graph consists of n independent cycles of order
k
1
,... ,k
n
, then |S
f
|
=
i
=1
k
i
.
For what concerns the dynamical behavior of a CA subshift, we are particularly
interesting to the (positive) transitivity and to some stronger conditions such as
topological mixing and strong transitivity.
Definition 4.
A DTDS X, g is said topologically mixing iff for any pair A, B
of nonempty open subsets of the phase space X, there exists an integer n
0
∈
N
such that ∀n>n
0
,g
n
(
A
)
∩B
=
∅. A DTDS is called M-chaotic iff it is D-chaotic
and topologically mixing.
Definition 5.
A DTDS X, g is said strongly transitive iff for any nonempty
open subsets A of the phase space X,
n∈
N
g
n
(
A
)=
X. A DTDS is called ST-
chaotic iff it is D-chaotic and strongly transitive.
For a subshift (positive) transitivity implies regularity. Moreover, if the subshift
has infinite cardinality, positive transitivity is equivalent to D-chaoticity. Analo-
gous result holds for topological mixing: for a infinite subshift, topological mixing
is equivalent to M-chaos. Differently, a strong transitive subshift is necessarily a
finite and transitive subshift whose configurations are mutually different periodic
points. Therefore, it cannot be D-chaotic.
The study of subshifts generated by an ECA rule leads to the following result:
the set of all ECA transitive rules is just the set theoretic union of all mixing
and all strong transitive rules. This fact is proved in [4].
We can summarize the subshift behaviour of transitive ECA in the following
way:
1. ECA which are
both
mixing
and
strong transitive subshifts are
nonempty
trivial
: their
AG
f
graphs are composed by a unique node with a loop and
so the subshift spaces are the trivial ones, either the singleton
{
0
}
or the
singleton
{
1
}
.
