zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Universality and complexity in cellular automata. (English) Zbl 0562.68040
Cellular automata, Proc. Interdisc. Workshop, Los Alamos/N.M. 1983, 1-35 (1984).
Summary: [For the entire collection see Zbl 0556.00013.] 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.

68Q80Cellular automata (theory of computing)
[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)