细胞自动机与有限型位移映射
Cellular Automata and Shifts of Finite Type
DOI: 10.12677/PM.2019.97103, PDF,    国家自然科学基金支持
作者: 赵晓旭, 匡 锐：华南理工大学数学学院，广东 广州
关键词: 细胞自动机；有限型位移映射；拓扑熵；符号系统；Cellular Automata； Shifts of Finite Type； Topological Entropy； Symbolic System
摘要: 本论文中，我们从拓扑动力系统的角度把细胞自动机看作是符号空间上的连续自映射，对细胞自动机的单射、满射、同胚性质进行研究。我们利用拓扑熵的一般性质证明了经典的Garden定理，即一维细胞自动机为同胚映射当且仅当它为单射。并且，利用该方法可以很方便地将Garden定理推广到高维情形，即任意维细胞自动机为同胚映射等价于它为单射。
Abstract: In this paper, we consider the cellular automaton as a continuous self-mapping on the symbol space from the perspective of the topological dynamic system, and study the injective, surjective, and homeomorphic properties of the cellular automata. We use the general properties of topological entropy to prove the classical Garden theorem, that is, a one-dimensional cellular automaton maps is homeomorphic if and only if it is injective. Moreover, using this method, Garden’s theorem can be easily generalized to the high-dimensional situation, that is, the cellular automata of any dimension is homeomorphic mapping equivalent to it being injective.
文章引用：赵晓旭, 匡锐. 细胞自动机与有限型位移映射[J]. 理论数学, 2019, 9(7): 791-798. https://doi.org/10.12677/PM.2019.97103

参考文献

[1] Neumann, J.V. and Burks, A.W. (1966) Theory of Self-Reproducing Automata. University of Illinois Press, Cham-paign.
[2] Hedlund, G.A. (1969) Endomorphisms and Automorphisms of the Shift Dynamical System. Mathematical System Theory, 3, 320-375.
[Google Scholar] [CrossRef] 
[3] Berlekamp, E.R., Conway, J.H. and Guy, H.K. (1982) Winnning Ways for Your Mathematical Plays. Acadamic Press, New York.
[4] Wolfram, S. (1983) Statistical Mechanics of Cellular Automata. Review Modern Physics, 55, 601-644.
[Google Scholar] [CrossRef] 
[5] Wolfram, S. (1984) Universality and Complexity in Cellular Automata. Journal of Physics D, 10, 1-35.
[Google Scholar] [CrossRef] 
[6] Wolfram, S. (1986) Theory and Applications of Cellular Automata. World Scientifc, Singapore.
[7] Wolfram, S. (2002) A New Kind of Science. Wolfram Media, Champaign.
[8] Chua, L.O., Yoon, S. and Dogaru, R. (2002) A Nonlinear Dynamics Perspective of Wolfram’s New Kind of Science. Part I: Threshold of Complexity. Interna-tional Journal of Bifurcation and Chaos, 12, 2655-2766.
[Google Scholar] [CrossRef] 
[9] Chua, L.O., Sbitnev, V.I. and Yoon, S. (2005) A Nonlinear Dynamics Per-spective of Wolfram’s New Kind of Science. Part IV: From Bernoulli-Shift to 1/f Spectrum. International Journal of Bifurcation and Chaos, 15, 1045-1223.
[Google Scholar] [CrossRef] 
[10] Chua, L.O., Sbitnev, V.I. and Yoon, S. (2006) A Nonlinear Dynamics Per-spective of Wolfram’s New Kind of Science. Part VI: From Time-Reversible Attractors to the Arrows of Time. International Journal of Bifurcation and Chao, 16, 1097-1373.
[Google Scholar] [CrossRef] 
[11] Chua, L.O., Guan, J.B., Valery, I.S. and Shin, J. (2007) A Nonlinear Dynamics Perspective of Wolfram’s New Kind of Science. Part VII: Isle of Eden. International Journal of Bifurcation and Chaos, 17, 2839-3012.
[Google Scholar] [CrossRef] 
[12] Moore, E.F. (1962) Machine Models of Self-Reproduction. Proceedings of Symposia in Applied Mathematics, 14, 17-33.
[Google Scholar] [CrossRef] 
[13] Myhill, J. (1963) The Converse to Moore’s Garden-of-Eden Theorem. Proceedings of the American Mathematical Society, 14, 685-686.
[Google Scholar] [CrossRef] 
[14] 周作领. 符号动力系统[M]. 上海: 上海科技教育出版社, 1997: 56-67.
[15] Kitchens, B.P. (1998) Countable State Markov Shifts. In: Kitchens, B.P., Ed., Symbolic Dynamics, Universitext, Springer, Berlin, Heidelberg, 195-240.
[Google Scholar] [CrossRef] 
[16] Wiggins, S. (1990) Introduction to Applied Nonlinear Dynamical Systems and Chaos. Springer, Berlin.
[Google Scholar] [CrossRef] 
[17] 陈芳跃. CNN符号动力系统[D]: [博士学位论文]. 上海: 上海大学, 2003.
[18] Codd, E.F. (1968) Cellular Automata. Academic Press, New York.
[19] Walters, P. (1982) An Introduction to Ergodic Theory. Springer Verlag, New York.
[Google Scholar] [CrossRef] 
[20] Berger, R. (1966) Theundecidability of the Domino Problem. Memoirs of the American Mathematical Society, 66, 1-72.
[21] 熊金城. 点集拓扑讲义[M]. 第4版. 北京: 高等教育出版社, 2011: 198-209.

为你推荐