Research ArticleOpen AccessGoogle Scholar indexed
Transitivity and Chaoticity in 1-D Cellular Automata
School of Science, Hangzhou Dianzi University, Hangzhou, China
Department of Electronic Engineering, City University of Hong Kong, Hong Kong, China
College of Pharmaceutical Sciences, Zhejiang Chinese Medical University, Hangzhou, China
- 1 School of Science, Hangzhou Dianzi University, Hangzhou, China
- 2 Department of Electronic Engineering, City University of Hong Kong, Hong Kong, China
- 3 College of Pharmaceutical Sciences, Zhejiang Chinese Medical University, Hangzhou, China
International Journal of Modern Nonlinear Theory and Application·Volume 02 (2013)·Pages 69–73·Published 29 March 2013·DOI10.4236/ijmnta.2013.21A008
Copy link · social · email
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.
KeywordsBernoulli Subshift of Finite TypeCellular AutomataDevaney ChaosSymbolic DynamicsTopological Transitivity
- J. von Neumann, “Theory of Self-Reproducing Automata,” University of Illinois Press, Urbana and London, 1966.
- 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
- S. Wolfram, “Computation Theory of Cellular Automata,” Communications in Mathematical Physics, Vol. 96, No. 1, 1984, pp. 15-57. doi:10.1007/BF01217347
- S. Wolfram, “Theory and Application of Cellular Automata,” Word Scientific, Singapore Cty, 1986.
- S. Wolfram, “A New Kind of Science,” Wolfram Media, Inc., Champaign, 2002.
- 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
- 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
- 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
- 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
- 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
- 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.
- 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.
- 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.