IJMNTA  Vol.2 No.1 A , March 2013
Transitivity and Chaoticity in 1-D Cellular Automata
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.

Cite this paper
F. Chen, G. Chen and W. Jin, "Transitivity and Chaoticity in 1-D Cellular Automata," International Journal of Modern Nonlinear Theory and Application, Vol. 2 No. 1, 2013, pp. 69-73. doi: 10.4236/ijmnta.2013.21A008.
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

 
 
Top