Tutorials and ReviewsNo Access

A NONLINEAR DYNAMICS PERSPECTIVE OF WOLFRAM'S NEW KIND OF SCIENCE PART IX: QUASI-ERGODICITY

Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CA 94720, USA

Search for more papers by this author

GIOVANNI EGIDIO PAZIENZA

Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CA 94720, USA

Grup de Recerca en Sistemes Intel·ligents, Enginyeria i Arquitectura La Salle, Universitat Ramon Llull, Barcelona, Spain

Search for more papers by this author

LASZLO ORZO

Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CA 94720, USA

Cellular Sensory Wave Computing Laboratory, Computer and Automation Research Institute, SZTAKI, Hungarian Academy of Sciences, H-111 Budapest, Kende-u. 13, Hungary

Search for more papers by this author

VALERY I. SBITNEV

Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CA 94720, USA

B.P. Konstantinov Saint-Petersburg Nuclear Physics Institute, RAN, Russia

Search for more papers by this author

, and

JINWOOK SHIN

Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CA 94720, USA

Search for more papers by this author

https://doi.org/10.1142/S0218127408021853Cited by:17 (Source: Crossref)

Abstract

Our scientific odyssey through the theory of 1-D cellular automata is enriched by the definition of quasi-ergodicity, a new empirical property discovered by analyzing the time-1 return maps of local rules. Quasi-ergodicity plays a key role in the classification of rules into six groups: in fact, it is an exclusive characteristic of complex and hyper Bernoulli-shift rules. Besides introducing quasi-ergodicity, this paper answers several questions posed in the previous chapters of our quest. To start with, we offer a rigorous explanation of the fractal behavior of the time-1 characteristic functions, finding the equations that describe this phenomenon. Then, we propose a classification of rules according to the presence of Isles of Eden, and prove that only 28 local rules out of 256 do not have any of them; this result sheds light on the importance of Isles of Eden. A section of this paper is devoted to the characterization of Bernoulli basin-tree diagrams through modular arithmetic; the formulas obtained allow us to shorten drastically the number of cases to take into consideration during numerical simulations. Last but not least, we present some theorems about additive rules, including an analytical explanation of their scale-free property.

References

G. Cattaneo and C. Quaranta Vogliotti, Theoret. Comput. Sci. 178, 77 (1997), DOI: 10.1016/S0304-3975(96)00053-9. Crossref, Web of Science, Google Scholar
L. O. Chua , CNN: A Paradigm for Complexity ( World Scientific , Singapore , 1996 ) . Google Scholar
L. O. Chua, S. Yoon and R. Dogaru, Int. J. Bifurcation and Chaos 13, 2377 (2002). Link, Web of Science, Google Scholar
L. O. Chua, V. I. Sbitnev and S. Yoon, Int. J. Bifurcation and Chaos 13, 2377 (2003). Link, Web of Science, Google Scholar
L. O. Chua, V. I. Sbitnev and S. Yoon, Int. J. Bifurcation and Chaos 14, 3689 (2004). Link, Web of Science, Google Scholar
L. O. Chua, V. I. Sbitnev and S. Yoon, Int. J. Bifurcation and Chaos 15, 1045 (2005). Link, Web of Science, Google Scholar
L. O. Chua, V. I. Sbitnev and S. Yoon, Int. J. Bifurcation and Chaos 15, 3701 (2005). Link, Web of Science, Google Scholar
L. O. Chua, V. I. Sbitnev and S. Yoon, Int. J. Bifurcation and Chaos 16, 1097 (2006). Link, Web of Science, Google Scholar
L. O. Chuaet al., Int. J. Bifurcation and Chaos 17, 2839 (2007). Link, Web of Science, Google Scholar
L. O. Chuaet al., Int. J. Bifurcation and Chaos 17, 3741 (2007). Link, Web of Science, Google Scholar
M. Courbage, D. Mercier and S. Yasmineh, Chaos 9, 893 (1999), DOI: 10.1063/1.166462. Crossref, Web of Science, Google Scholar
M. Courbage and S. Yasmineh, Physica D 150, 63 (2001), DOI: 10.1016/S0167-2789(00)00213-X. Crossref, Web of Science, Google Scholar
Garay, B. M. & Chua, L. O. [2008] "Isles of Eden and the ZUK theorem in Rd," Int. J. Bifurcation and Chaos 18(10), in press . Google Scholar
G. A. Hedlund, Th. Comput. Syst. 3, 320 (1969). Google Scholar
K. Ireland and M. Rosen , A Classical Introduction to Modern Number Theory ( Springer-Verlag , 1990 ) . Crossref, Google Scholar
O. Martin, A. M. Odlyzko and S. Wolfram, Commun. Math. Phys. 93, 219 (1984), DOI: 10.1007/BF01223745. Crossref, Web of Science, Google Scholar
E. F. Moore, Proc. Symp. Appl. Math. 14, 17 (1962). Crossref, Google Scholar
J. Myhill, Proc. Amer. Math. Soc. 14, 685 (1963), DOI: 10.2307/2034301. Web of Science, Google Scholar
F. Ohi, Compl. Syst. 17, 295 (2007). Google Scholar
M. Pivato and R. Yassami, Journ'ees Automates Cellulaires 1, 119 (2008). Google Scholar
M. A. Shereshevsky, Mh. Math. 114, 305 (1992), DOI: 10.1007/BF01299385. Crossref, Web of Science, Google Scholar
M. Shirvani and T. D. Rogers, Commun. Math. Phys. 136, 599 (1991), DOI: 10.1007/BF02099076. Crossref, Web of Science, Google Scholar
A. Wuensche and M. Lesser , The Global Dynamics of Cellular Automata: An Atlas of Basin of Attraction Fields of One-Dimensional Cellular Automata ( Addison-Wesley , Reading, MA , 1992 ) . Google Scholar