Universality and Complexity in Cellular Automata - Stephen Wolfram

1 downloads 222 Views 16MB Size Report
[5] T. Toffoli, N. Margolus and G. Vishniac, private demon- strations. [6] P. Billingsley, Ergodic ... [15] F.S. Beckman
S. Wolfram / Universality and complexity in cellular automata

then this dependence may be arbitrarily complex, and the behaviour of the system can be found by 1,10 procedure significantly simpler than direct sim~Iation. No meaningful prediction is therefore possible for such systems.

Acknowledgements I am grateful to many people for discussions, including C. Bennett, J. Crutchfield, D. Friedan, P. Gacz, E. Jen, D. Lind, O. Martin, A. Odlyzko, N . Packard, S2. Shenker, W. Thurston, T. Toffoli and S. Willson. I am particularly grateful to J. Milnor for extensive discussions and suggestions.

References [I] S. Wolfram, 'Statistical mechanics of cellular automata", Rev . Mod. Phys. 55 (1983) 601. [2] O. Martin, A.M. Odlyzko and S. Wolfram, " Algebraic properties of cellular automata", Bell Laboratories report (January 1983); Comm. Math. Phys., to be published. [3] D. Lind, " Applications of ergodic theory and sofic systems to cellular automata", University of Washington preprint (April 1983); Physica 100 (1984) 36 (these proceedings). [4] S. Wolfram, "CA: an interactive cellular automaton simulator for the Sun Workstation and VAX", presented and demonstrated at the Interdisciplinary Workshop on Cellular Automata, Los Alamos (March 1983). [5] T. Toffoli, N. Margolus and G . Vishniac, private demonstrations. [6] P. Billingsley, Ergodic Theory and Information (Wiley, New York, 1965). [7] D . Knuth, Semi numerical Algorithms, 2nd. ed. (AddisonWesley, New York, 1981), section 3.5. [8] R.G. Gallager, Information Theory and Reliable Commu• _ nications (Wiley, New York, 1968).

..

35

[9] J.D. Farmer, "Dimension, fractal measures and the probabilistic structure of chaos", in : Evolution of Order and Chaos in Physics, Chemistry and Biology, H. Haken, ed . (Springer, Berlin, 1982). [10] J.D. Farmer, private communication. [II] B. Mandelbrot, The Fractal Geometry of nature (Freeman, San Francisco, 1982). [12] J.D. Farmer, " Information dimension and the probabilistic structure of chaos", Z. Naturforsch. 37a (1982) 1304. [13] P. Grassberger, to be published. [l4] P. Diaconis, private communication; C. Stein, unpublished notes. [15] F.S. Beckman, " Mathematical Foundations of Programming (Addison-Wesley, New York , 1980). [16] J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation (Addison-Wesley, New York, 1979). [17] Z. Manna, Mathematical Theory of Computation (McGraw-Hill, New York, 1974). [18] M. Minsky, Computation: Finite and Infinite Machines (Prentice-Hall, London, 1967). [19] B. Weiss, " Subshifts of finite type and sofic systems", Monat. Math. 17 (1973) 462. E.M. Coven and M.E. Paul, " Sofic systems", Israel J. Math. 20 (1975) 165. [20] P. Grassberger, " A new mechanism for deterministic diffusion", Wuppertal preprint WU B 82- 18 (1982). [2I] J. Milnor, unpublished notes. [22] R.W. Gosper, unpublished; R. Wainwright, "Life is universa!!", Proc. Winter Simul. Conf., Washington D .C., ACM (1974). E.R. Berlekamp, J.H . Conway and R.K. Guy, Winning Ways, for Your Mathematical Plays, vol. 2 (Academic Press, New York, 1982), chap. 25. [23] R.W. Gosper, "Exploiting regularities in large cellular spaces", Physica 100 (1984) 75 (these proceedings). [24] G. Chaitin, "Algorithmic information theory" , IBM J. Res. & Dev. , 21 (1977) 350; "Toward a mathematical theory of life", in : The Maximum Entropy Formalism, R.D. Levine and M. Tribus, ed. (MIT press, Cambridge, MA, 1979). [25] C. Bennett, "On the logical "depth" of sequences and their reducibilities to random sequences", IBM report (April 1982) (to be published in Info. & Control) .