Wolfram, Stephen 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.] Cited in 3 ReviewsCited in 45 Documents MSC: 68Q80 Cellular automata (computational aspects) 37B15 Dynamical aspects of cellular automata Keywords:discrete dynamical systems; one-dimensional cellular automata; universality classes; chaotic attractors; universal computation; infinite time behaviour Citations:Zbl 0556.00013 PDF BibTeX XML OpenURL Online 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:  Wolfram, S.: Statistical mechanics of cellular automata. Rev. mod. Phys. 55, 601 (1983) · Zbl 1174.82319  Martin, O.; Odlyzko, A. M.; Wolfram, S.: Algebraic properties of cellular automata. Bell laboratories report (January 1983) · Zbl 0564.68038  . Physica 10D, 36 (1984)  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)  T. Toffoli, N. Margolus and G. Vishniac, private demonstrations.  Billingsley, P.: Ergodic theory and information. (1965) · Zbl 0141.16702  Knuth, D.: Seminumerical algorithms. (1981) · Zbl 0477.65002  Gallager, R. G.: Information theory and reliable communications. (1968) · Zbl 0198.52201  Farmer, J. D.: Dimension, fractal measures and the probabilistic structure of chaos. Evolution of order and chaos in physics, chemistry and biology (1982)  J.D. Farmer, private communication.  Mandelbrot, B.: The fractal geometry of nature. (1982) · Zbl 0504.28001  Farmer, J. D.: Information dimension and the probabilistic structure of chaos. Z. naturforsch. 37a, 1304 (1982) · Zbl 1194.37052  P. Grassberger, to be published.  P. Diaconis, private communication; C. Stein, unpublished notes.  Beckman, F. S.: Mathematical foundations of programming. (1980) · Zbl 0443.68021  Hopcroft, J. E.; Ullman, J. D.: Introduction to automata theory, languages, and computation. (1979) · Zbl 0426.68001  Manna, Z.: Mathematical theory of computation. (1974) · Zbl 0353.68066  Minsky, M.: Computation: finite and infinite machines. (1967) · Zbl 0195.02402  Coven, E. M.; Paul, M. E.: Sofic systems. Israel J. Math. 20, 165 (1975) · Zbl 0307.28015  Grassberger, P.: A new mechanism for deterministic diffusion. Wuppertal preprint Wu B 82-18 (1982)  J. Milnor, unpublished notes.  Berlekamp, E. R.; Conway, J. H.; Guy, R. K.: Winning ways, for your mathematical plays. 2 (1982) · Zbl 0485.00025  Gosper, R. W.: Exploiting regularities in large cellular spaces. Physica 10D, 75 (1984)  Levine, R. D.; Tribus, M.: Toward a mathematical theory of life. The maximum entropy formalism (1979) · Zbl 0467.94001  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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.