Abstract
Local space-time structures, such as domains and the intervening dislocations, dominate a wide class of cellular automaton (CA) behavior. For such spatially-extended dynamics regular domains, vicinities, and attractors are introduced as organizing principles to identify the discretized analogs of attractors, basins, and separatrices: structures used in classifying dissipative continuous-state dynamical systems. We describe the attractor-basin portrait of nonlinear elementary CA rule 18, whose global dynamics is largely determined by a single regular attracting domain. The latter's basin is analyzed in terms of subbasin and portal structures associated with particle annihilation. The conclusion is that the computational complexity of such CA is more apparent than real. Transducer machines are constructed that automatically identify domain and dislocation structures in space-time, count the number of dislocations in a spatial pattern, and implement an isomorphism between rule 18 and rule 90. We use a transducer to trace dislocation trajectories, and confirm that in rule 18, isolated dislocation trajectories, as well as a dislocation gas, agree extremely well with the classical model of annihilating diffusive particles. The CA efficiently transforms randomness of an initial pattern ensemble into a random walk of dislocations in space-time.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
S. Wolfram,Theory and Applications of Cellular Automata (World Scientific, Singapore, 1986).
A. R. Smith, Simple computation-universal cellular spaces,J. ACM 18:339 (1971).
T. Toffoli, Cellular automata mechanics, Ph.D. thesis, University of Michigan, Michigan (1977).
S. Wolfram, Computation theory of cellular automata,Commun. Math. Phys. 96:15 (1984).
L. Hurd, Formal language characterizations of cellular automaton limit sets,Complex Systems 1:69 (1987).
E. R. Berlekamp, J. H. Conway, and R. K. Guy,Winning Ways for Your Mathematical Plays, Vol. 2 (Academic Press, New York, 1984).
T. Toffoli and N. Margolis,Cellular Automata Machines: A New Environment for Modeling (MIT Press, Cambridge, Massachusetts, 1987).
O. Martin, A. Odlyzko, and S. Wolfram, Algebraic properties of cellular automata,Commun. Math. Phys. 93:219 (1984).
K. Kaneko, Attractors, basin structures and information processing in cellular automata, inTheory and Applications of Cellular Automata, S. Wolfram, ed. (World Scientific, Singapore, 1986).
H. Ito, Intriguing properties of global structure in some classes of finite cellular automata,Physica 31D:318 (1988).
E. Jen, Cylindrical cellular automata,Commun. Math. Phys. 118:569 (1990).
S. Wolfram, Statistical mechanics of cellular automata,Rev. Mod. Phys. 55:601 (1983).
H. A. Gutowitz, J. D. Victor, and B. W. Knight, Local structure theory for cellular automata,Physica 28D:18 (1987).
W. Li, N. H. Packard, and C. G. Langton, Transition phenomena in cellular automata rule space,Physica 45D:77 (1990).
N. Boccara, J. Nasser, and M. Roger, Particle-like structures and their interactions in spatio-temporal patterns generated by one-dimensional deterministic cellular automaton rules,Phys. Rev. A 44:866 (1991).
J. Park, K. Steiglitz, and W. Thurston, Soliton-like behavior in automata,Physica 19D:423 (1986).
P. Grassberger, New mechanism for deterministic diffusion,Phys. Rev. A 28:3666 (1983).
C. G. Langton, Computation at the edge of chaos: Phase transitions and emergent computation, inEmergent Computation, S. Forrest, ed. (North-Holland, Amsterdam, 1990), p. 12.
K. Lindgren, Correlations and random information in cellular automata,Complex Systems 1:529 (1987).
D. R. J. Chillingworth,Differential Topology with a View to Applications (Pitman, London, 1976).
J. Guckenheimer and P. Holmes,Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields (Springer-Verlag, New York, 1983).
J. P. Crutchfield and J. E. Hanson, Computational mechanics of cellular automata: Space and time machines, In preparation (1992).
P. Grassberger, Chaos and diffusion in deterministic cellular automata,Physica D 10:52 (1984).
D. Griffeath,Additive and Cancellative Interacting Particle Systems (Springer, Berlin, 1979).
J. E. Hopcroft and J. D. Ullman,Introduction to Automata Theory, Languages, and Computation (Addison-Wesley, Reading, Massachusetts, 1979).
J. P. Crutchfield and K. Young, Computation at the onset of chaos, inEntropy, Complexity, and the Physics of Information, W. Zurek, ed. (Addison-Wesley, 1990), p. 223.
J. P. Crutchfield, Reconstructing language hierarchies, inInformation Dynamics, H. A. Atmanspracher and H. Scheingraber, eds. (Plenum New York, 1991), p. 45.
R. E. Blahut,Principles and Practice of Information Theory (Addison-Wesley, 1987).
D. A. Lind, Applications of ergodic theory and sofic systems to cellular automata,Physica 10D:36 (1984).
M. G. Nordahl, Formal languages and finite cellular automata,Complex Systems 3:63 (1989).
L. P. Hurd, Appendix. Table 10. Regular language complexities, inTheory and Applications of Cellular Automata, S. Wolfram, ed. (World Scientific, Singapore, 1986).
N. H. Packard, Complexity in growing patterns in cellular automata, inDynamical Behavior of Automata: Theory and Applications, J. Demongeot, E. Goles, and M. Tchuente, eds. (Academic Press, 1984).
S. Wolfram, Universality and complexity in cellular automata,Physica 10D:1 (1984).
F. Harary,Graph Theory (Addison-Wesley, 1969).
J. P. Crutchfield and J. E. Hanson, Computational mechanics of cellular automata: Space-time machines, In Preparation (1992).
E. Jen, Aperiodicity in one-dimensional cellular automata,Physica 44D:121 (1990).
E. Jen, Exact solvability and quasiperiodicity of one-dimensional cellular automata,Non-linearity 4:251 (1990).
K. Eloranta and E. Nummelin, The kink of cellular automaton rule 18 performs a random walk, Technical Report A296, Helsinki University of Technology, Institute of Mathematics (1991).
K. Lindgren and M. G. Nordahl, Complexity measures and cellular automata,Complex Systems 2:409 (1988).
J. P. Crutchfield, Subbasins, portals, and mazes: Transients in high dimensions,J. Nucl. Phys. B 5A:287 (1988).
J. P. Crutchfield and K. Young, Inferring statistical complexity,Phys. Rev. Lett. 63:105 (1989).
A. G. Cairns-Smith,Genetic Takeover and the Mineral Origins of Life (Cambridge University Press, New York, 1982).
J. P. Crutchfield, Spatio-temporal complexity in nonlinear image processing,IEEE Trans. Circ. Syst. 37:770 (1988).
J. P. Crutchfield and K. Kaneko, Are attractors relevant to turbulence?,Phys. Rev. Lett. 60:2715 (1988).
J. P. Crutchfield and K. Kaneko, Transients in high dimensions, In preparation (1992).
J. P. Crutchfield and K. Kaneko, Phenomenology of spatio-temporal chaos, inDirections in Chaos, Hao Bai-lin, ed. (World Scientific, Singapore, 1987), p. 272.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hanson, J.E., Crutchfield, J.P. The attractor—basin portrait of a cellular automaton. J Stat Phys 66, 1415–1462 (1992). https://doi.org/10.1007/BF01054429
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01054429