Computation theory of cellular automata. (English) Zbl 0587.68050

Wolfram, Stephen

Commun. Math. Phys. 96, 15-57 (1984).

Self-organizing behaviour in cellular automata is discussed as a computational process. Formal language theory is used to extend dynamical systems theory descriptions of cellular automata. The sets of configurations generated after a finite number of time steps of cellular automaton evolution are shown to form regular languages. Many examples are given. The sizes of the minimal grammars for these languages provide measures of the complexities of the sets. This complexity is usually found to be non-decreasing with time. the limit sets generated by some classes of cellular automata correspond to regular languages. For other automata they appear to correspond to more complicated languages. Many properties of these sets are then formally non-computable. It is suggested that such undecidability is common in these and other dynamical systems.

MSC:

68Q80	Cellular automata (computational aspects)
68Q45	Formal languages and automata

Keywords:

Self-organizing behaviour; regular languages; limit sets

References:

[1]	Wolfram, S.: Statistical mechanics of cellular automata. Rev. Mod. Phys.55, 601 (1983) · Zbl 1174.82319
[2]	Wolfram, S.: Universality and complexity in cellular automata. Physica10D, 1 (1984) · Zbl 0562.68040
[3]	Packard, N.H.: Complexity of growing patterns in cellular automata, Institute for Advanced Study preprint (October 1983), and to be published in Dynamical behaviour of automata. Demongeot, J., Goles, E., Tchuente, M., (eds.). Academic Press (proceedings of a workshop held in Marseilles, September 1983)
[4]	Wolfram, S.: Cellular automata as models for complexity. Nature (to be published)
[5]	Wofram, S.: Cellular automata. Los Alamos Science, Fall 1983 issue
[6]	Beckman, F.S.: Mathematical foundations of programming. Reading, MA: Addison-Wesley 1980 · Zbl 0443.68021
[7]	Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Reading, MA: Addison-Wesley 1979 · Zbl 0426.68001
[8]	Minsky, M.: Computation: finite and infinite machines Englewood Cliffs, NJ: Prentice-Hall 1967 · Zbl 0195.02402
[9]	Rozenberg, G., Salomaa, A. (eds.): L systems. In: Lecture Notes in Computer Science, Vol. 15 · Zbl 0508.68031
[10]	Rozenberg, G., Salomaa, A.: The mathematical theory of L systems. New York: Academic Press 1980 · Zbl 0508.68031
[11]	Guckenheimer, J., Holmes, P.: Nonlinear oscillations, dynamical systems, and bifurcations of vector fields. Berlin, Heidelberg, New York: Springer 1983 · Zbl 0515.34001
[12]	Walters, P.: An introduction to ergodic theory. Berlin, Heidelberg, New York: Springer 1982 · Zbl 0475.28009
[13]	Weiss, B.: Subshifts of finite type and sofic systems. Monat. Math.17, 462 (1973); Coven, E.M., Paul, M.E.: Sofic systems. Israel J. Math.20 165 (1975) · Zbl 0285.28021
[14]	Field, R.D., Wolfram, S.: A QCD model fore + e ? annihilation. Nucl. Phys. B213, 65 (1983)
[15]	Smith, A.R.: Simple computation-universal cellular spaces. J. ACM18, 331 (1971) · Zbl 0221.94071
[16]	Berlekamp, E.R., Conway, J.H., Guy, R.K.: Winning ways for your mathematical plays. New York: Academic Press, Vol. 2, Chap. 25 · Zbl 0584.00009
[17]	Lind, D.: Applications of ergodic theory and sofic systems to cellular automata. Physica10D, 36 (1984) · Zbl 0562.68038
[18]	de Bruijn, N.G.: A combinatorial problem. Ned. Akad. Weten. Proc.49, 758 (1946); · Zbl 0060.02701
[19]	Good, I.J.; Normal recurring decimals. J. Lond. Math. Soc.21, 167 (1946) · Zbl 0060.02702
[20]	Nerode, A.: Linear automaton transformations. Proc. Am. Math. Soc.9, 541 (1958) · Zbl 0089.33403
[21]	Cvetkovic, D., Doob, M., Sachs, H.: Spectra of graphs. New York: Academic Press 1980 · Zbl 0458.05042
[22]	Billingsley, P.: Ergodic theory and information. New York: Wiley 1965 · Zbl 0141.16702
[23]	Chomsky, N., Miller, G.A.: Finite state languages. Inform. Control1, 91 (1958) · Zbl 0081.14503
[24]	Stewart, I.N., Tall, D.O.: Algebraic number theory. London: Chapman & Hall 1979 · Zbl 0413.12001
[25]	Lind, D.A.: The entropies of topological Markow shifts and a related class of algebraic integers. Ergodic Theory and Dynamical Systems (to be published) · Zbl 0534.58030
[26]	Milnor, J.: Unpublished notes (cited in [2])
[27]	Hedlund, G.A.: Endomorphisms and automorphisms of the shift dynamical system. Math. Syst. Theor.3, 320 (1969); · Zbl 0182.56901
[28]	Hedlund, G.A.: Transformations commuting with the shift. In: Topological dynamics. Auslander, J., Gottschalk, W.H. (eds.). New York: Benjamin 1968 · Zbl 0195.52702
[29]	Amoroso, S., Patt, Y.N.: Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. J. Comp. Syst. Sci.6, 448 (1972) · Zbl 0263.94019
[30]	Nasu, M.: Local maps inducing surjective global maps of one-dimensional tessellation automata. Math. Syst. Theor.11, 327 (1978) · Zbl 0389.68024
[31]	Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. San Francisco: Freeman 1979, Sect. A10 · Zbl 0411.68039
[32]	Martin, O., Odlyzko, A.M., Wolfram, S.: Algebraic properties of cellular automata. Commun. Math. Phys.93, 219 (1984) · Zbl 0564.68038
[33]	Hedlund, G.: Private communication · Zbl 1356.91023
[34]	Manning, A.: Axiom A diffeomorphisms have rational zeta functions. Bull. Lond. Math. Soc.3, 215 (1971); · Zbl 0219.58007
[35]	Coven, E., Paul, M.: Finite procedures for sofic systems. Monat. Math.83, 265 (1977) · Zbl 0368.28022
[36]	Franks, J.: Private communication
[37]	Coven, E.: Private communication
[38]	Hurd, L.: Formal language characterizations of cellular automata limit sets (to be published)
[39]	Rosenfeld, A.: Picture languages. New York: Academic Press (1979) · Zbl 0471.68074
[40]	Golze, U.: Differences between 1- and 2-dimensional cell spaces. In: Automata, Languages and Development, Lindenmayer, A., Rozenberg, G. (eds.). Amsterdam: North-Holland 1976
[41]	Yaku, T.: The constructibility of a configuration in a cellular automaton. J. Comput. System Sci.7, 481 (1983) · Zbl 0271.94037
[42]	Grassberger, P.: Private communication
[43]	Grassberger, P.: A new mechanism for deterministic diffusion. Phys. Rev. A (to be published) · Zbl 0562.68039
[44]	Chaos and diffusion in deterministic cellular automata. Physica10 D, 52 (1984) · Zbl 0562.68039
[45]	Hillis, D., Hurd, L.: Private communications
[46]	Salomaa, A., Soittola, M.: Automata-theoretic aspects of formal power series. Berlin, Heidelberg, New York: Springer 1978 · Zbl 0377.68039
[47]	Kuich, W.: On the entropy of context-free languages. Inform. Cont.16, 173 (1970) · Zbl 0193.32603
[48]	Chaitin, G.: Algorithmic information theory. IBM J. Res. Dev.21, 350 (1977) · Zbl 0362.94035
[49]	Kaminger, F.P.: The non-computability of the channel capacity of context-sensitive languages. Inform. Cont.17, 175 (1970) · Zbl 0196.01802
[50]	Smith, A.R.: Real-time language recognition by one-dimensional cellular automata. J. Comput. Syst. Sci.6, 233 (1972) · Zbl 0268.68044
[51]	Sommerhalder, R., van Westrhenen, S.C.: Parallel language recognition in constant time by cellular automata. Acta Inform.19, 397 (1983) · Zbl 0509.68075
[52]	Rogers, H.: Theory of recursive functions and effective computability. New York: McGraw-Hill 1967 · Zbl 0183.01401
[53]	Bennett, C.H.: On the logical ?depth? of sequences and their reducibilities to random sequences. Inform. Control (to be published)
[54]	Conway, J.H.: Regular algebra and finite machines. London: Chapman & Hall 1971 · Zbl 0231.94041
[55]	Shannon, C.E.: Prediction and entropy of printed English. Bell Syst. Tech. J.30, 50 (1951) · Zbl 1165.94313
[56]	Wolfram, S.: SMP reference manual. Computer Mathematics Group. Los Angeles: Inference Corporation 1983
[57]	Packard, N.H., Wolfram, S.: Two dimensional cellular automata. Institute for Advanced Study preprint, May 1984
[58]	Hopcroft, H.: Ann logn algorithm for minimizing states in a finite automaton. In: Proceedings of the International Symposium on the Theory of Machines and Computations. New York: Academic Press 1971
[59]	Hurd, L.: Private communication