Universality and complexity in cellular automata. (English) Zbl 0562.68040
Cellular automata, Proc. Interdisc. Workshop, Los Alamos/N.M. 1983, Physica D 10, No. 1-2, 1-35 (1984).
Summary: Cellular automata are discrete dynamical systems with simple construction but complex self-organizing behaviour. Evidence is presented that all one-dimensional cellular automata fall into four distinct universality classes. Characterizations of the structures generated in these classes are discussed. Three classes exhibit behaviour analogous to limit points, limit cycles and chaotic attractors. The fourth class is probably capable of universal computation, so that properties of its infinite time behaviour are undecidable.
[For the entire collection see Zbl 0556.00013.]
[For the entire collection see Zbl 0556.00013.]
Keywords:
discrete dynamical systems; one-dimensional cellular automata; universality classes; chaotic attractors; universal computation; infinite time behaviourCitations:
Zbl 0556.00013Online Encyclopedia of Integer Sequences:
Critical block length for legal totalistic k=2, r=2 cellular automaton with code 2n (-1 indicates the value is infinite).References:
| [1] | Wolfram, S.: Statistical mechanics of cellular automata. Rev. mod. Phys. 55, 601 (1983) · Zbl 1174.82319 |
| [2] | Martin, O.; Odlyzko, A. M.; Wolfram, S.: Algebraic properties of cellular automata. Bell laboratories report (January 1983) · Zbl 0564.68038 |
| [3] | . Physica 10D, 36 (1984) |
| [4] | Wolfram, S.: CA: an interactive cellular automation simulator for the Sun workstation and VAX. Presented and demonstrated at the interdisciplinary workshop on cellular automata (March 1983) |
| [5] | T. Toffoli, N. Margolus and G. Vishniac, private demonstrations. |
| [6] | Billingsley, P.: Ergodic theory and information. (1965) · Zbl 0141.16702 |
| [7] | Knuth, D.: Seminumerical algorithms. (1981) · Zbl 0477.65002 |
| [8] | Gallager, R. G.: Information theory and reliable communications. (1968) · Zbl 0198.52201 |
| [9] | Farmer, J. D.: Dimension, fractal measures and the probabilistic structure of chaos. Evolution of order and chaos in physics, chemistry and biology (1982) |
| [10] | J.D. Farmer, private communication. |
| [11] | Mandelbrot, B.: The fractal geometry of nature. (1982) · Zbl 0504.28001 |
| [12] | Farmer, J. D.: Information dimension and the probabilistic structure of chaos. Z. naturforsch. 37a, 1304 (1982) · Zbl 1194.37052 |
| [13] | P. Grassberger, to be published. |
| [14] | P. Diaconis, private communication; C. Stein, unpublished notes. |
| [15] | Beckman, F. S.: Mathematical foundations of programming. (1980) · Zbl 0443.68021 |
| [16] | Hopcroft, J. E.; Ullman, J. D.: Introduction to automata theory, languages, and computation. (1979) · Zbl 0426.68001 |
| [17] | Manna, Z.: Mathematical theory of computation. (1974) · Zbl 0353.68066 |
| [18] | Minsky, M.: Computation: finite and infinite machines. (1967) · Zbl 0195.02402 |
| [19] | Coven, E. M.; Paul, M. E.: Sofic systems. Israel J. Math. 20, 165 (1975) · Zbl 0307.28015 |
| [20] | Grassberger, P.: A new mechanism for deterministic diffusion. Wuppertal preprint Wu B 82-18 (1982) |
| [21] | J. Milnor, unpublished notes. |
| [22] | Berlekamp, E. R.; Conway, J. H.; Guy, R. K.: Winning ways, for your mathematical plays. 2 (1982) · Zbl 0485.00025 |
| [23] | Gosper, R. W.: Exploiting regularities in large cellular spaces. Physica 10D, 75 (1984) |
| [24] | Levine, R. D.; Tribus, M.: Toward a mathematical theory of life. The maximum entropy formalism (1979) · Zbl 0467.94001 |
| [25] | Bennett, C.: On the logical ”depth” of sequences and their reducibilities to random sequences. IBM report (April 1982) |
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.
