Ergodic properties of certain surjective cellular automata
Tóm tắt
We consider one-dimensional cellular automata, i.e. the mapsT:P
ℤ
→P
ℤ
(P is a finite set with more than one element) which are given by (Tx)
i
=F(x
i+l
, ...,x
i+r
),x=(x
i
)∈ℤ∈P
ℤ
for some integersl≤r and a mappingF∶P
r−l+1→P. We prove that ifF is right- (left-) permutative (in Hedlund's terminology) and 0≤l0 andT is surjective, then the natural extension of the system (P
ℤ
, ℬ, μ,T) is aK-automorphism. We also prove that the shift ℤ2-action on a two-dimensional subshift of finite type canonically associated with the cellular automatonT is mixing, ifF is both right and left permutative. These results answer some questions raised in [SR].
Tài liệu tham khảo
[B]Billingsley, P.: Ergodic Theory and Information. New York: Wiley. 1965.
[CFS]Cornfeld, I. P., Fomin, S. V., Sinai, Ya. G.: Ergodic Theory. New York: Springer. 1981.
[C]Coven, E. M.: Topological entropy of block maps. Proc. Amer. Math. Soc.78, 590–594 (1980).
[CP]Coven, E. M., Paul, M.: Endomorphisms of irreducible shifts of finite type. Math. Syst. Theory8, 165–177 (1974).
[DGS]Denker, M., Grillenberger, C., Sigmund, K.: Ergodic Theory on Compact Spaces. Lect. Notes Math. 527. Berlin-Heidelberg-New York: Springer. 1976.
[G]Gilman, R. H. Classes of linear automata. Ergod. Theory Dynam. Syst.7, 105–118 (1987).
[H]Hedlund, G. A.: Endomorphisms and automorphisms of the shift dynamical system. Math. Syst. Theory3, 320–375 (1969).
[Hu]Hurley, M.: Attractors in cellular automata. Ergod. Theory Dynam. Syst.10, 131–140 (1990).
[L]Ledrappier, F.: Un champ markovien peut être d'entropie nulle et mélangeant. C. R. Acad. Sci. Paris, Ser. A,287, 561–562 (1978).
[Li]Lind, D.: Applications of ergodic theory and sofic systems to cellular automata. Physica10D, 36–44 (1984).
[O1]Ornstein, D. S.: Ergodic Theory, Randomness and Dynamical Systems. New Haven, Connecticut: Yale University Press. 1974.
[O2]Ornstein, D. S.: Imbedding Bernoulli shifts in flows. In: Lect. Notes Math. 160. pp. 178–218. Berlin-Heidelberg-New York: Springer. 1970.
[O3]Ornstein, D. S.: Two Bernoulli shifts with infinite entropy are isomorphic. Adv. Math.5, 339–348 (1970).
[R]Rohlin, V. A.: Exact endomorphisms of a Lebesgue space. Amer. Math. Soc. Translations (2)39, 1–36 (1964).
[Sch1]Schmidt, K.: Algebraic Ideas in Ergodic Theory. CBMS Regional Conf. Ser. in Math. 76. Providence RI: Amer. Math Soc. 1990.
[Sch2]Schmidt, K.: Asymptotic properties of unitary representations and mixing. Proc. London Math. Soc.48, 445–460 (1984).
[SA]Shereshevsky, M. A., Afraimovich, V. S.: Bipermutative cellular automata are topologically conjugate to the one-sided Bernoulli shift. Random and Computational Dynamics 1 (1992). To appear.
[SR]Shirvani, M., Rogers, T. D.: On ergodic one-dimensional cellular automata. Commun. Math. Phys.136, 599–605 (1991).
[W]Wolfram, S.: Universality and complexity in cellular automata. Physica10D, 1–35 (1984).