Computational mechanics of cellular automata: an example. (English) Zbl 1194.37022
Summary: We illustrate and extend the techniques of computational mechanics in explicating the structures that emerge in the space-time behavior of elementary one-dimensional cellular automaton rule 54. The dominant regular domain of the cellular automation is identified and a domain filter is constructed to locate and classify defects in the domain. The primary particles are identified and a range of interparticle interactions is studied. The deterministic equation of motion of the filtered space-time behavior is derived. Filters of increasing sophistication are constructed for the efficient gathering of particle statistics and for the identification of higher-level defects, particle interactions, and secondary domains. We define the emergence time at which the space-time behavior condenses into configurations consisting only of domains, particles, and particle interactions. Taken together, these techniques serve as the basis for the investigation of pattern evolution and self-organization in this representative system.
MSC:
| 37B15 | Dynamical aspects of cellular automata |
| 82C20 | Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics |
References:
| [1] | Wolfram, S., Universality and complexity in cellular automata, Physica D, 10, 1 (1984) · Zbl 0562.68040 |
| [2] | Hanson, J. E.; Crutchfield, J. P., The attractor-basin portrait of a cellular automaton, J. Stat. Phys., 66, 1415 (1992) · Zbl 0892.58051 |
| [3] | Crutchfield, J. P.; Hanson, J. E., Attractor vicinity decay for a cellular automaton, Chaos, 3, 215 (1993) · Zbl 1055.37508 |
| [4] | Crutchfield, J. P.; Hanson, J. E., Trubulent pattern bases for cellular automata, Physica D, 69, 279 (1993) · Zbl 0794.68111 |
| [5] | Hanson, J. E., Computational mechanics of cellular automata, (Ph.D. Thesis (1993), University of California: University of California Berkeley), Published by University Microfilms, Ann Arbor, MI · Zbl 1194.37022 |
| [6] | Wolfram, S., Computation theory of cellular automata, Commun. Math. Phys., 96, 15 (1984) · Zbl 0587.68050 |
| [7] | Nordahl, M. G., Formal languages and finite cellular automata, Complex Systems, 3, 63 (1989) · Zbl 0734.68067 |
| [8] | Culik, K.; Hurd, L. P.; Yu, S., Computation theoretic aspects of cellular automata, Physica D, 45, 357 (1990) · Zbl 0729.68052 |
| [9] | Lindgren, K.; Nordahl, M., Universal computation in simple one-dimensional cellular automata, Complex Systems, 4, 299 (1990) · Zbl 0724.68072 |
| [10] | Steiglitz, K.; Kamal, I.; Watson, A., Embedding computation in one-dimensional automata by phase coding solitons, IEEE Trans. Comput., 37, 138-144 (1988) |
| [11] | Aizawa, Y.; Nishikawa, I.; Kaneko, K., Soliton turbulence in one-dimensional cellular automata, Physica D, 45, 307-327 (1990) · Zbl 0728.58010 |
| [12] | Gacs, P., Nonergodic one-dimensional media and reliable computation, Contemporary Mathematics, 41, 125 (1985) · Zbl 0565.60084 |
| [13] | Crutchfield, J. P.; Mitchell, M., The evolution of emergent computation, (Proc. Natl. Acad. Sci., 92 (1995)), (23) · Zbl 0960.68639 |
| [14] | Boccara, N.; Nasser, J.; Roger, M., Particlelike structures and their interactions in spatio-temporal patterns generated by one-dimenersional deterministic cellular automaton rules, Phys. Rev. A, 44, 866 (1991) |
| [15] | Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701 |
| [16] | Crutchfield, J. P.; Young, K., Inferring statistical complexity, Phys. Rev. Lett., 63, 105 (1989) |
| [17] | Crutchfield, J. P., The calculi of emergence: Computation, dynamics, and induction, Physica D, 75, 11-54 (1994) · Zbl 0860.68046 |
| [18] | Crutchfield, J. P., Unreconstructible at any radius, Phys. Lett. A, 171, 52-60 (1992) |
| [19] | Das, R.; Crutchfield, J. P.; Mitchell, M.; Hanson, J. E., Evolving globally synchronized cellular automata, (Eshelman, L. J., Proc. 6th Int. Conf. on Genetic Algorithms (1995), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA) |
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.
