Information Technology Reference
In-Depth Information
-
if
X
has infinite cardinality, then full transitivity and regularity together
imply sensitivity to initial condition.
-
full transitivity implies indecomposability.
-
in the case of homeomorphic DTDS on compact space full transitivity is not
equivalent to positive transitivity. In other words, the notion of transitivity
given in [6] is different from the one considered in [7].
2 Subshifts in 1D CA
In this section we briefly outline the behavior of simple subshifts generated by
1D CA. Precisely we focus our attention to some components of chaotic behavior
such as (positive) transitivity and stronger conditions such as topological mixing
and strong transitivity.
At first, let us recall the formal notion of subshift.
Definition 1.
A (two-sided)
subshift
over the alphabet A
=
{
0
,
1
,... ,k−
1
}
(k ≥
2
)isaDTDS S, σ
S
, where S is a closed (S
=
S) strictly σ-invariant
(σ
(
S
)=
S) subset of A
Z
, and σ
S
is the restriction of the shift map σ (σ
:
A
Z
→
A
Z
, ∀i ∈
Z[
σ
(
x
)]
i
=
x
i
+1
) to this subset.
A subshift
S, σ
S
distinguishes the words or finite blocks constructed over the
alphabet
A
in two types: admissible blocks, i.e., blocks appearing in some con-
figuration of
S
and blocks which are not admissible, called forbidden. We will
write
w ≺ x
to denote that the
A
-word
w
=(
w
1
,... ,w
n
)
∈A
∗
appears in the
configuration
x ∈A
Z
, formally
∃i ∈
Z s.t.
x
i
=
w
1
,... ,x
i
+
n−
1
=
w
n
. We will
denote by
w ≺ x
the fact that
w
does not appear in the configuration
x
.
A subshift can be generated by a set of words considered as a set of forbidden
blocks. Precisely, let
F
be any subset of
A
∗
, and let us construct the set
S
(
F
)=
{x ∈A
Z
:
∀w ∈F,w ≺ x}
. Then
S
(
F
) is a subshift, named the subshift
generated by
F
. Now we illustrate a su
@
cient condition on the local rule in order
that the global dynamic turns out to be a subshift. For this goal, a suitable set
of forbidden blocks with respect to the local CA rule will be constructed.
Definition 2.
Let A,r,f be a CA. A finite block w
−r
...w
−
1
w
0
w
1
...w
r
∈
A
2
r
+1
is said to be left-forbidden (resp., right-forbidden) with respect to the CA
local rule f iff f
(
w
−r
...w
0
...w
r
)
=
w
1
(resp., f
(
w
−r
...w
0
...w
r
)
=
w
−
1
).
Conversely, the block is called left-admissible (resp., right-admissible).
Proposition 1.
Let A,r,f beaCAand
A
Z
,F
f
be the associated DTDS.
Let F
2
r
+1
(
f
)=
{w
−r
...w
0
...w
r
∈A
2
r
+1
:
f
(
w
−r
...w
0
...w
r
)
=
w
1
} be the
set of all left-forbidden blocks of the local rule f and let S
f
=
{x ∈A
Z
:
∀w ∈
F
2
r
+1
(
f
)
,w ≺ x} be the set of all configurations which do not contain any local
rule left-forbidden block. Then S
f
,F
f
is a subshift.
An analogous result holds considering the right-forbidden blocks of a local rule.
From now on we will give some CA left-subshift properties; the analogous ones
for CA right-subshift can be obtained in a dual way.
