×

Kolmogorov complexity and cellular automata classification. (English) Zbl 0973.68088

Summary: We present a new approach to Cellular Automata (CA) classification based on algorithmic complexity. We construct a parameter \(\kappa\) which is based only on the transition table of CA and measures the “randomness” of evolutions; \(\kappa\) is better, in a certain sense, than any other parameter recursively definable on CA tables. We investigate the relations between the classical topological approach and ours. Our parameter is compared with Langton’s \(\lambda\) parameter: \(\kappa\) turns out to be theoretically better and also agrees with some practical evidences reported in literature. Finally, we propose a protocol to approximate \(\kappa\) and make experiments on CA dynamical behavior.

MSC:

68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
68Q80 Cellular automata (computational aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Banks, J.; Brooks, J.; Davis, G.; Cairns, G.; Stacey, P., On Devaney’s definition of chaos, Amer. Math. Monthly, 99, 332-334 (1992) · Zbl 0758.58019
[2] Berlekamp, E. R.; Conway, J. H.; Guy, R. K., Winning Ways for Your Mathematical Plays, Vol. 2 (1982), Academic Press: Academic Press New York · Zbl 0485.00025
[3] Blanchard, F.; Kurka, P.; Maas, A., Topological and measure-theoretic properties of one-dimensional cellular automata, Physica D, 103, 86-99 (1997) · Zbl 1194.37002
[4] Braga, G.; Cattaneo, G.; Flocchini, P.; Quaranta Vogliotti, C., Pattern growth in elementary cellular automata, Theoret. Comput. Sci., 45, 1-26 (1995) · Zbl 0874.68219
[5] Calude, C., Information and Randomness (1994), Springer: Springer Berlin · Zbl 0922.68073
[6] Cattaneo, G.; Formenti, E.; Margara, L.; Mazoyer, J., A shift-invariant metric on
((S^Z\) inducing a non-trivial topology, (Privara, I.; Rusika, P., Mathematical Foundations of Computer Science (MFCS’97), Lecture Notes in Computer Science, Vol. 1295 (1997), Bratislava, Springer: Bratislava, Springer Berlin) · Zbl 0941.37006
[7] Crutchfield, J. P.; Haber, P. T.; Mitchell, M., Revisting the edge of chaosevolving cellular automata to perform computations, Comput. Systems, 7, 89-130 (1993)
[8] Čulik, K.; Pachl, J.; Yu, S., On the limit set of cellular automata, SIAM J. Comput., 18, 167-175 (1989)
[9] Davaney, R. L., Introduction to Chaotic Dynamical Systems (1989), Addison-Wesley: Addison-Wesley Reading, MA
[10] B. Durand, Zs. Róka, The game of life: universality revisited, in: J. Mazoyer, M. Delorme (Ed.), Cellular Automata: A Parallel Model, Kluwer, Dordrecht, 1999.; B. Durand, Zs. Róka, The game of life: universality revisited, in: J. Mazoyer, M. Delorme (Ed.), Cellular Automata: A Parallel Model, Kluwer, Dordrecht, 1999.
[11] H. Gutowitz, C. Langton, Mean field theory and the edge of chaos, in proc. 3rd Europ. Conf. on Art. Life, 1995.; H. Gutowitz, C. Langton, Mean field theory and the edge of chaos, in proc. 3rd Europ. Conf. on Art. Life, 1995.
[12] Hedlund, G. A., Endomorphism and automorphism of the shift dynamical systems, Math. Systems Theory, 3, 320-375 (1969) · Zbl 0182.56901
[13] Hurley, M., Attractors in cellular automata, Ergodic. Theory Dynamical Systems, 10, 131-140 (1990) · Zbl 0666.58029
[14] Kari, J., Rice’s theorem for the limit set of cellular automata, Theoret. Comput. Sci., 127, 229-254 (1994) · Zbl 0824.68078
[15] Knudsen, C., Chaos without nonperiodicity, Amer. Math. Monthly, 101, 563-565 (1994) · Zbl 0840.54031
[16] Kurka, P., Languages, equicontinuity and attractors in cellular automata, Ergodic Theory Dynamical Systems, 17, 417-433 (1997) · Zbl 0876.68075
[17] Langton, C., Computation at the edge of chaosphase transitions and emergent computation, Physica D, 42, 12-37 (1990)
[18] Li, M.; Vitányi, P., An Introductioin to Kolmogorov Complexity and its Applications (1997), Springer: Springer Berlin
[19] Martin-Löf, P., The definition of random sequences, Inform. and Control, 9, 602-619 (1966) · Zbl 0244.62008
[20] Martin-Löf, P., Complexity oscillations in infinite binary sequences, Z. Wahrsch. Ver. Geb., 19, 223-230 (1971) · Zbl 0212.23103
[21] Uspensky, V. A.; Semenov, A. L.; Shen, A. Kh., Can individual sequences of zeros and ones be random?, Russian Math. Surveys, 45, 121-189 (1990) · Zbl 0702.03038
[22] Uspensky, V. A.; Shen, Kh., Relations between varieties of Kolmogorov complexities, Math. Systems Theory, 29, 3, 270-291 (1996) · Zbl 0849.68059
[23] Wolfram, S., Computation theory of cellular automata, Comm. Math. Phys., 96, 15-57 (1984) · Zbl 0587.68050
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.