Classifying 1D elementary cellular automata with the 0-1 test for chaos. (English) Zbl 1525.37017
Summary: We utilise the 0-1 test to automatically classify elementary cellular automata. The quantitative results of the 0-1 test reveal a number of advantages over Wolfram’s qualitative classification. For instance, while almost all rules classified as chaotic by Wolfram were confirmed as such by the 0-1 test, there were two rules which were revealed to be non-chaotic. However, their periodic nature is hidden by the high complexity of their spacetime patterns and not easy to see without looking very carefully. Comparing each rule’s chaoticity (as quantified by the 0-1 test) against its intrinsic complexity (as quantified by its Chua complexity index) also reveals a number of counter-intuitive discoveries; i.e. non-chaotic dynamics are not only found in simpler rules, but also in rules as complex as chaos.
MSC:
| 37B15 | Dynamical aspects of cellular automata |
| 68Q80 | Cellular automata (computational aspects) |
| 68Q19 | Descriptive complexity and finite models |
Software:
JBoolReferences:
| [1] | Aulbach, B.; Kieninger, B., On three definitions of chaos, Nonlinear Dyn. Syst. Theory, 1, 1, 23-37 (2001) · Zbl 0991.37010 |
| [2] | Cattaneo, G.; Finelli, M.; Margara, L., Investigating topological chaos by elementary cellular automata dynamics, Theoret. Comput. Sci., 244, 1-2, 219-241 (2000) · Zbl 0945.68134 |
| [3] | Blanchard, F.; Cervelle, J.; Formenti, E., Some results about the chaotic behavior of cellular automata, Theoret. Comput. Sci., 349, 3, 318-336 (2005) · Zbl 1085.37007 |
| [4] | Martinez, G. J., A note on elementary cellular automata classification (2013), arXiv preprint arXiv:1306.5577 · Zbl 1280.68133 |
| [5] | Gottwald, G. A.; Melbourne, I., On the implementation of the 0-1 test for chaos, SIAM J. Appl. Dyn. Syst., 8, 1, 129-145 (2009) · Zbl 1161.37054 |
| [6] | Wolfram, S.; Gad-el Hak, M., A new kind of science, Appl. Mech. Rev., 56, 2, B18-B19 (2003) |
| [7] | De Sales, J.; Martins, M.; Moreira, J., One-dimensional cellular automata characterization by the roughness exponent, Physica A, 245, 3-4, 461-471 (1997) |
| [8] | Cattaneo, G.; Vogliotti, C. Q., The “magic” rule spaces of neural-like elementary cellular automata, Theoret. Comput. Sci., 178, 1-2, 77-102 (1997) · Zbl 0901.68136 |
| [9] | Dürr, C.; Rapaport, I.; Theyssier, G., Cellular automata and communication complexity, Theoret. Comput. Sci., 322, 2, 355-368 (2004) · Zbl 1068.68087 |
| [10] | Dubacq, J.-C.; Durand, B.; Formenti, E., Kolmogorov complexity and cellular automata classification, Theoret. Comput. Sci., 259, 1-2, 271-285 (2001) · Zbl 0973.68088 |
| [11] | Terry-Jack, M., Novel lossless compression method based on the Fourier transform to approximate the Kolmogorov complexity of elementary cellular automata, J. Soft. Eng. Appl., 15, 10, 359-383 (2022) |
| [12] | Peitgen, H.-O.; Jürgens, H.; Saupe, D.; Feigenbaum, M. J., Chaos And Fractals: New Frontiers of Science, Vol. 7 (1992), Springer · Zbl 0779.58004 |
| [13] | Banks, J.; Brooks, J.; Cairns, G.; Davis, G.; Stacey, P., On devaney’s definition of chaos, Amer. Math. Monthly, 99, 4, 332-334 (1992) · Zbl 0758.58019 |
| [14] | Mayo-Wilson, C., Structural chaos, Philos. Sci., 82, 5, 1236-1247 (2015) |
| [15] | Cattaneo, G.; Formenti, E.; Manzini, G.; Margara, L., Ergodicity, transitivity, and regularity for linear cellular automata over zm, Theoret. Comput. Sci., 233, 1-2, 147-164 (2000) · Zbl 0953.37002 |
| [16] | Chatterjee, S.; Yilmaz, M. R., Chaos fractals stat., Statist. Sci., 7, 1, 49-68 (1992) · Zbl 0955.37500 |
| [17] | Oxley, A., Detecting the phenomenon of strange non-chaotic attractors, ANZIAM J., 51, C612-C624 (2009) · Zbl 1386.37037 |
| [18] | Gottwald, G. A.; Melbourne, I., A new test for chaos in deterministic systems, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 460, 2042, 603-611 (2004) · Zbl 1042.37060 |
| [19] | Brown, R.; Chua, L. O., Clarifying chaos II: Bernoulli chaos, zero Lyapunov exponents and strange attractors, Int. J. Bifurcation Chaos, 8, 01, 1-32 (1998) · Zbl 0959.37025 |
| [20] | Danca, M.-F.; Kuznetsov, N., Hidden strange nonchaotic attractors, Mathematics, 9, 6, 652 (2021) |
| [21] | Dawes, J.; Freeland, M., The ‘0-1 test for chaos’ and strange nonchaotic attractors, 1210 (2008), Preprint 1209 |
| [22] | Gottwald, G. A.; Melbourne, I., The 0-1 test for chaos: A review, Chaos Detect. Predict., 221-247 (2016) |
| [23] | Thunberg, H., Periodicity versus chaos in one-dimensional dynamics, SIAM Rev., 43, 1, 3-30 (2001) · Zbl 1049.37027 |
| [24] | Smith, L. A., Predictability and chaos, Encycl. Atmospheric Sci., 4, 1777-1785 (2003) |
| [25] | Schüle, M.; Stoop, R., A full computation-relevant topological dynamics classification of elementary cellular automata, Chaos, 22, 4, Article 043143 pp. (2012) · Zbl 1319.37008 |
| [26] | Chua, L. O.; Yoon, S.; Dogaru, R., A nonlinear dynamics perspective of Wolfram’s new kind of science part I: Threshold of complexity, Int. J. Bifurcation Chaos, 12, 12, 2655-2766 (2002) · Zbl 1043.37009 |
| [27] | Crama, Y.; Hammer, P. L., Boolean Functions: Theory, Algorithms, and Applications (2011), Cambridge University Press · Zbl 1237.06001 |
| [28] | C.E. Lobry, Chaos and Cellular Automata. · Zbl 0491.93036 |
| [29] | Touhey, P., Chaos: the evolution of a definition, Irish Math. Soc. Bull, 40, 60-70 (1998) · Zbl 0936.37009 |
| [30] | Vellekoop, M.; Berglund, R., On intervals, transitivity=chaos, Amer. Math. Monthly, 101, 4, 353-355 (1994) · Zbl 0886.58033 |
| [31] | Knudsen, C., Chaos without nonperiodicity, Amer. Math. Monthly, 101, 6, 563-565 (1994) · Zbl 0840.54031 |
| [32] | Manzini, G.; Margara, L., A complete and efficiently computable topological classification of D-dimensional linear cellular automata over Zm, Theoret. Comput. Sci., 221, 1-2, 157-177 (1999) · Zbl 0930.68090 |
| [33] | Skokos, C. H.; Gottwald, G. A.; Laskar, J., Chaos Detection and Predictability, Vol. 1 (2016), Springer · Zbl 1339.37002 |
| [34] | J.P. Crutchfield, J.D. Farmer, N.H. Packard, R.S. Shaw, 1995. Chaos. |
| [35] | Boxdorfer, G., A Study of Visualization Approaches and Fractal Dimension Classification of Certain Boolean Networks (2021), University of Nebraska at Omaha, (Ph.D. thesis) |
| [36] | Freistetter, F., Fractal dimensions as chaos indicators, Celestial Mech. Dynam. Astronom., 78, 1, 211-225 (2000) · Zbl 1083.37511 |
| [37] | Liang, Z.; Feng, Z.; Guangxiang, X., Comparison of fractal dimension calculation methods for channel bed profiles, Procedia Eng., 28, 252-257 (2012) |
| [38] | Gottwald, G. A.; Melbourne, I., On the validity of the 0-1 test for chaos, Nonlinearity, 22, 6, 1367 (2009) · Zbl 1171.65091 |
| [39] | Hu, J.; Tung, W.-w.; Gao, J.; Cao, Y., Reliability of the 0-1 test for chaos, Phys. Rev. E, 72, 5, Article 056207 pp. (2005) |
| [40] | Webel, K., Chaos in german stock returns—New evidence from the 0-1 test, Econom. Lett., 115, 3, 487-489 (2012) |
| [41] | Xin, B.; Zhang, J., Finite-time stabilizing a fractional-order chaotic financial system with market confidence, Nonlinear Dynam., 79, 1399-1409 (2015) · Zbl 1345.91024 |
| [42] | Litak, G.; Syta, A.; Wiercigroch, M., Identification of chaos in a cutting process by the 0-1 test, Chaos Solitons Fractals, 40, 5, 2095-2101 (2009) |
| [43] | Nair, V.; Sujith, R., A reduced-order model for the onset of combustion instability: physical mechanisms for intermittency and precursors, Proc. Combust. Inst., 35, 3, 3193-3200 (2015) |
| [44] | Swathy, P.; Thamilmaran, K., Dynamics of SC-CNN based variant of MLC circuit: An experimental study, Int. J. Bifurcation Chaos, 24, 02, Article 1430008 pp. (2014) · Zbl 1287.94128 |
| [45] | Leon, F., Design and evaluation of a multiagent interaction protocol generating behaviours with different levels of complexity, Neurocomputing, 146, 173-186 (2014) |
| [46] | Krese, B.; Govekar, E., Analysis of traffic dynamics on a ring road-based transportation network by means of 0-1 test for chaos and Lyapunov spectrum, Transp. Res. C, 36, 27-34 (2013) |
| [47] | Martinsen-Burrell, N.; Julien, K.; Petersen, M. R.; Weiss, J. B., Merger and alignment in a reduced model for three-dimensional quasigeostrophic ellipsoidal vortices, Phys. Fluids, 18, 5, Article 057101 pp. (2006) · Zbl 1185.76478 |
| [48] | Erzgräber, H.; Wieczorek, S.; Krauskopf, B., Dynamics of two semiconductor lasers coupled by a passive resonator, Phys. Rev. E, 81, 5, Article 056201 pp. (2010) |
| [49] | Tsai, T.-L.; Dawes, J. H., Dynamics near a periodically-perturbed robust heteroclinic cycle, Physica D, 262, 14-34 (2013) · Zbl 1284.37021 |
| [50] | Skokos, C.; Antonopoulos, C.; Bountis, T.; Vrahatis, M., Detecting order and chaos in Hamiltonian systems by the SALI method, J. Phys. A: Math. Gen., 37, 24, 6269 (2004) |
| [51] | Culik, K.; Hurd, L. P.; Yu, S., Computation theoretic aspects of cellular automata, Physica D, 45, 1-3, 357-378 (1990) · Zbl 0729.68052 |
| [52] | Sutner, K., Classification of cellular automata, Encycl. Complex. Syst. Sci., 3, 755-768 (2009) |
| [53] | Zenil, H.; Villarreal-Zapata, E., Asymptotic behavior and ratios of complexity in cellular automata, Int. J. Bifurcation Chaos, 23, 09, Article 1350159 pp. (2013) · Zbl 1277.37026 |
| [54] | Zenil, H., Compression-based investigation of the dynamical properties of cellular automata and other systems (2009), arXiv preprint arXiv:0910.4042 |
| [55] | Borriello, E.; Imari Walker, S., An information-based classification of elementary cellular automata, Complexity, 2017 (2017) · Zbl 1373.68294 |
| [56] | Kurka, P., Topological Dynamics of One-Dimensional Cellular Automata, Encyclopedia of Complexity and System Sciences (2008), Springer-Verlag: Springer-Verlag Berlin |
| [57] | Li, G.; Yue, Y.; Xie, J.; Grebogi, C., Strange nonchaotic attractors in a nonsmooth dynamical system, Commun. Nonlinear Sci. Numer. Simul., 78, Article 104858 pp. (2019) · Zbl 1476.37058 |
| [58] | Al-Emam, M.; Kaurov, V., Cellular automata complexity threshold and classification: A geometric perspective, Complex Syst., 23, 4, 355-376 (2014) · Zbl 1357.68117 |
| [59] | Albantakis, L.; Tononi, G., The intrinsic cause-effect power of discrete dynamical systems—from elementary cellular automata to adapting animats, Entropy, 17, 8, 5472-5502 (2015) |
| [60] | Machicao, J.; Ribas, L. C.; Scabini, L. F.; Bruno, O. M., Cellular automata rule characterization and classification using texture descriptors, Physica A, 497, 109-117 (2018) · Zbl 1514.68151 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
