Information Technology Reference
In-Depth Information
transition map F
f
:
A
Z
→ A
Z
induced by
f
, associates with any configuration
x ∈A
Z
the
next time step
configuration
F
f
(
x
) whose
i
-th component is expressed
by the local rule: [
F
f
(
x
)]
i
=
f
(
x
i−r
,... ,x
i
,... ,x
i
+
r
).
CA can display a rich and complex time evolution whose exact determination
is in general very hard. The empirical observation of 1D CA dynamics leads
to realize that many of them share a nontrivial subshift global behavior. A
(simple) subshift contained in a CA
A,r,f
is a DTDS
S
f
,σ
S
f
, where
S
f
is
the collection of the bi-infinite sequences
x ∈A
Z
on which the global transition
map
F
f
coincides with the shift (formally,
∀x ∈ S
f
:
F
f
(
x
)=
σ
(
x
)).
Several dynamical properties of CA have been investigated during the last
few years. We illustrate the chaotic behavior of simple subshifts generated by
ECA. We recall that a discrete time dynamical system (DTDS)
X, g
, where the
phase space X
is equipped with a distance
d
and the
next state map g
:
X → X
is continuous on
X
according to the metric
d
,is
topologically chaotic
according
to Devaney [7] (or D-chaotic) iff it is
Regular
(the set of periodic points is a
dense subset of the phase space, i.e., for any
x ∈ X
and any
>
0 there exists
a periodic point
p
such that
d
(
p, x
)
<
),
Transitive
(for every pair of nonempty
open subsets
A
and
B
of the phase space, there exists a positive integer
t
0
such that
g
t
0
(
A
)
∩ B
=
∅
) and
Sensitive to initial conditions
(there exists a
constant
>
0 such that for any state
x ∈ X
and for any
δ>
0 there must
be at least one state
y ∈ X
and one integer
t
0
∈
N such that
d
(
x, y
)
<δ
and
d
(
g
t
0
(
x
)
,g
t
0
(
y
))
≥
). In [1] it has been shown that if a DTDS with infinite
cardinality is regular and transitive, then it is also
sensitive to initial conditions
.
In order to establish the chaoticity of a DTDS, transitivity plays a central
role. On an interval of real numbers, transitivity is equal to chaos [12]. In the
case of the global DTDS
A
Z
,F
f
induced from a CA local rule
f
, the simple
condition of transitivity implies sensitivity to initial conditions [5]. Again, for a
subshift of infinite cardinality, transitivity is a condition equivalent to chaos [4].
Several definitions of “transitivity” can be found in literature. In this paper
we rename the above notion given in [7] as
positive transitivity
, since the integer
appearing in this definition belongs to N. Differently in [6] one can find a defi-
nition in which it is required that the integer
t
0
ranges over Z and that
X, g
is a homeomorphic DTDS on a compact space
X
. In other works ([8], [9] for
instance) the notion of transitivity is given in terms of the existence of a dense
orbit (that is, of a state
x
0
∈ X
whose positive motion starting from
x
0
is dense
in
X
).
We introduce the new notion of
full transitivity
(the integer belongs to Z) and
we study the relations among these two types of transitivity and other properties
such as existence a dense orbit, indecomposability, and topological chaos. The
results are:
-
existence of a dense orbit does not imply positive transitivity, not even if
X
is a compact space, whereas it always implies full transitivity. If
X
is a
perfect set (i.e., without isolated points) the positive transitivity is implied
by the existence of a dense orbit.
