Transitivity and Chaoticity in 1-D Cellular Automata

Fangyue Chen, Guanrong Chen, Weifeng Jin

College of Pharmaceutical Sciences, Zhejiang Chinese Medical University, Hangzhou, China.
Department of Electronic Engineering, City University of Hong Kong, Hong Kong, China.
School of Science, Hangzhou Dianzi University, Hangzhou, China.

DOI: 10.4236/ijmnta.2013.21A008                

Abstract

Recent progress in symbolic dynamics of cellular automata (CA) shows that many CA exhibit rich and complicated Bernoulli-shift properties, such as positive topological entropy, topological transitivity and even mixing. Noticeably, some CA are only transitive, but not mixing on their subsystems. Yet, for one-dimensional CA, this paper proves that not only the shift transitivity guarantees the CA transitivity but also the CA with transitive non-trivial Bernoulli subshift of finite type have dense periodic points. It is concluded that, for one-dimensional CA, the transitivity implies chaos in the sense of Devaney on the non-trivial Bernoulli subshift of finite types.

Keywords

Bernoulli Subshift of Finite Type; Cellular Automata; Devaney Chaos; Symbolic Dynamics; Topological Transitivity

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	J. von Neumann, “Theory of Self-Reproducing Automata,” University of Illinois Press, Urbana and London, 1966.
[2]	M. Gardner, “The Fantastic Combinations of John Conway’s New Solitaire Game Life,” Scientific American, Vol. 223, No. 4, 1970, pp. 120-123. doi:10.1038/scientificamerican1070-120
[3]	S. Wolfram, “Computation Theory of Cellular Automata,” Communications in Mathematical Physics, Vol. 96, No. 1, 1984, pp. 15-57. doi:10.1007/BF01217347
[4]	S. Wolfram, “Theory and Application of Cellular Automata,” Word Scientific, Singapore Cty, 1986.
[5]	S. Wolfram, “A New Kind of Science,” Wolfram Media, Inc., Champaign, 2002.
[6]	G. A. Hedlund, “Endomorphisms and Automorphism of the Shift Dynamical System,” Mathematical System Theory, Vol. 3, No. 4, 1969, pp. 320-375. doi:10.1007/BF01691062
[7]	L. O. Chua, V. I. Sbitnev and S. Yoon, “A Nonlinear Dynamics Perspective of Wolfram’s New Kind of Science, Part IV: From Bernoulli-Shift to 1/f Spectrum,” International Journal of Bifurcation and Chaos, Vol. 15, No. 4, 2005, pp. 1045-1183. doi:10.1142/S0218127405012995
[8]	L. O. Chua, V. I. Sbitnev and S. Yoon, “A Nonlinear Dynamics Perspective of Wolfram’s New Kind of Scienc, Part VI: From Time-Reversible Attractors to the Arrows of Time,” International Journal of Bifurcation and Chaos, Vol. 16, No. 5, 2006, pp. 1097-1373. doi:10.1142/S0218127406015544
[9]	L. O. Chua, J. B. Guan, I. S. Valery and J. Shin, “A Nonlinear Dynamics Perspective of Wolfram’s New Kind of Science, Part VII: Isle of Eden,” International Journal of Bifurcation and Chaos, Vol. 17, No. 9, 2007, pp. 2839-3012. doi:10.1142/S0218127407019068
[10]	L. O. Chua, K. Karacs, V. I. Sbitnev, J. B. Guan and J. Shin, “A Nonlinear Dynamics Perspective of Wolfram’s New Kind of Science, Part VIII: More Isles of Eden,” International Journal of Bifurcation and Chaos, Vol. 17, No. 11, 2007, pp. 3741-3894. doi:10.1142/S0218127407019901
[11]	F. Y. Chen, W. F. Jin, G. R. Chen, F. F. Chen and L. Chen, “Chaos of Elementary Cellular Automata Rule 42 of Wolfram’s Class II,” Chaos, Vol. 19, No. 013140, 2009, pp. 1-6.
[12]	W. F. Jin, F. Y. Chen, G. R. Chen, L. Chen and F. F. Chen, “Extending the Symbolic Dynamics of Chua’s Bernoulli-Shift Rule 56,” Journal of Cellular Automata, Vol. 5, No. 1-2, 2010, pp. 121-138.
[13]	W. F. Jin, F. Y. Chen, G. R. Chen, L. Chen and F. F. Chen, “Complex Symbolic Dynamics of Chua’s Period-2 Rule 37,” Journal of Cellular Automata, Vol. 5, No. 4-5, 2010, pp. 315-331.
[14]	F. F. Chen and F. Y. Chen, “Complex Dynamics of Cellular Automata Rule 119,” Physica A, Vol. 388, No. 6, 2009, pp. 984-990. doi:10.1016/j.physa.2008.12.002
[15]	F. F. Chen, F. Y. Chen, G. R. Chen, W. F. Jin and L. Chen, “Symbolics Dynamics of Elementary Cellular Automata Rule 88,” Nonlinear Dynamics, Vol. 58, No. 1-2, 2009, pp. 431-442. doi:10.1007/s11071-009-9490-3
[16]	L. Chen, F. Y. Chen, W. F. Jin, F. F. Chen and G. R. Chen, “Some Nonrobust Bernolli-Shift Rules,” International Journal of Bifurcation and Chaos, Vol. 19, No. 10, 2009, pp. 3407-3415. doi:10.1142/S0218127409024840
[17]	F. Y. Chen, L. Shi, G. R. Chen and W. F. Jin, “Chaos and Gliders in Periodic Cellular Automaton Rule 62,” Journal of Cellular Automata, Vol. 7, No. 4, 2012, pp. 287-302.
[18]	J. B. Guan, S. W. Shen, C. B. Tang and F. Y. Chen, “Extending Chua’s Global Equivalence Theorem on Wolfram’s New Kind of Science,” International Journal of Bifurcation and Chaos, Vol. 17, No. 12, 2007, pp. 4245-4259. doi:10.1142/S0218127407019925
[19]	R. L. Devaney, “An Introduction to Chaotic Dynamical Systems,” Addison-Wesley, Hazard, 1989.
[20]	P. Favati, G. Lotti and L. Margara, “Additive One-Dimensional Cellular Automata Are Chaotic According to Devaney’s Definition of Chaos,” Theoretical Computer Science, Vol. 174, No. 1-2, 1997, pp. 157-170. doi:10.1016/S0304-3975(95)00022-4
[21]	J. Banks, J. Brooks, G. Cairns, G. Davis and P. Stacey, “On the Devaney’s Definition of Chaos,” The American Mathematical Monthly, Vol. 99, No. 4, 1992, pp. 332-334. doi:10.2307/2324899
[22]	B. Codenotti and L. Margara, “Transitive Cellular Automata Are Sensitive,” The American Mathematical Monthly, Vol. 103, No. 1, 1996, pp. 58-62. doi:10.2307/2975215
[23]	B. Kitchens, “Symbolic Dynamics: One-Sided, Two-Sided and Countable State Markov Shifts,” Springer-Verlag, Berlin, 1998.
[24]	Z. L. Zhou, “Symbolic Dynamics,” Shanghai Scientific and Technological Education Publishing House, Shanghai, 1997.
[25]	J. Banks, “Regular Periodic Decompositions for Topologically Transitive Maps,” Ergodic Theory and Dynamical Systems, Vol. 17, No. 3, 1997, pp. 505-529. doi:10.1017/S0143385797069885
[26]	K. Culik, L. P. Hurd and S. Yu, “Computation Theoretic Aspects of Cellular Automata,” Physica D, Vol. 45, No. 1-3, 1990, pp. 357-378. doi:10.1016/0167-2789(90)90194-T
[27]	T. K. S. Moothathu, “Homogeneity of Surjective Cellular Automata,” Discrete Continuous Dynamic Systems, Vol. 13, No. 1, 2005, pp. 195-202.
[28]	J. Kari, “Theory of Cellular Automata: A Survey,” Theoretical Computer Science, Vol. 334, No. 1, 2005, pp. 3-33. doi:10.1016/j.tcs.2004.11.021