References

[1] D. Knuth, ``Seminumerical Algorithms,'' Addison-Wesley, Reading, Mass., 1981.

[2] A. Shamir, ``On the generation of cryptographically strong pseudorandom sequences,'' Lecture Notes in Computer Science Vol. 62, p. 544, Springer-Verlag, New York/Berlin, 1981; S. Goldwasser and S. Micali, Probabilistic encryption, J. Comput. System Sci. 28 (1984), 270; M. Blum and S. Micali, How to generate cryptographically strong sequences of pseudorandom bits, SIAM J. Comput. 13 (1984), 850; A. Yao, Theory and applications of trapdoor functions, in ``Proc. 23rd IEEE Symp. on Foundations of Computer Science,'' 1982.

[3] G. Chaitin, On the length of programs for computing finite binary sequences, I, II, J. Assoc. Comput. Mach. 13 (1966), 547; 16 (1969), 145, Randomness and mathematical proof, Sci. Amer. 232, No. 5 (1975), 47; A. N. Kolmogorov, Three approaches to the concept of ``the amount of information,'' Problems Inform. Transmission 1, 1 (1965); R. Solomonoff, A formal theory of inductive inference, Inform. Control 7 (1964), 1; P. Martin-Lof, The definition of random sequences, Inform. Control 9 (1966), 602; L. Levin, On the notion of a random sequence, Soviet Math. Dokl. 14 (1973), 1413.

[4] S. W. Golomb, ``Shift Register Sequences,'' Holden-Day, San Francisco, 1967.

[5] M. Garey and D. Johnson, ``Computers and Intractability: A Guide to the Theory of NP-Completeness,'' W. H. Freeman, San Francisco, 1979.

[6] L. Blum, M. Blum, and M. Shub, Comparison of two pseudorandom number generators, in ``Advances in Cryptology: Proc. of CRYPTO-82'' (D. Chaum, R. Rivest, and A. T. Sherman, Eds.), Plenum, New York, 1983.

[7] W. Alexi, B. Chor, O. Goldreich, and C. Schnorr, RSA/Rabin bits are secure, in ``Proc. Found. Comput. Sci.,'' (1984); U. Vazirani and V. Vazirani, Efficient and secure pseudorandom number generation, in ``Proc. Found. Comput. Sci.,'' (1984).

[8] L. Kuipers and H. Niederreiter, ``Uniform Distribution of Sequences,'' Wiley, New York, 1974.

[9] J. Lagarias, The problem and its generalizations, Amer. Math. Monthly 92 (1985), 3.

[10] K. Mahler, An unsolved problem on the powers of , Proc. Austral. Math. Soc. 8 (1968), 313; G. Choquet, Repartition des nombres ; mesures et ensembles associes, C. R. Acad. Sci. Paris A 290 (1980), 575.

[11] S. Wolfram, Origins of randomness in physical systems, Phys. Rev. Lett. 55 (1985), 449.

[12] S. Wolfram, Cellular automata as models of complexity, Nature 311 (1984), 419.

[13] D. Farmer, T. Toffoli, and S. Wolfram, (Eds.), Cellular automata, Physica D 10 Nos. 1, 2, (1984).

[14] S. Wolfram, Cellular automata and condensed matter physics, in Proc. NATO Advanced Study Institute on Scaling phenomena in disordered systems, April 1985.

[15] S. Wolfram, Universality and complexity in cellular automata, Physica D 10 (1984), 1.

[16] S. Wolfram, Computation theory of cellular automata, Commun. Math. Phys. 96 (1984), 15.

[17] S. Wolfram, Statistical mechanics of cellular automata, Rev. Modern Phys. 55 (1983), 601.

[18] S. Wolfram, Undecidability and intractability in theoretical physics, Phys. Rev. Lett. 54 (1985), 735.

[19] S. Wolfram, Computer software in science and mathematics, Sci. Amer. 251 September 1984.

[20] O. Martin, A. Odlyzko, and S. Wolfram, Algebraic properties of cellular automata, Comm. Math. Phys. 93 (1984), 219.

[21] J. Milnor, Notes on surjective cellular automaton-maps, Institute for Advanced Study preprint, June 1984.

[22] E. Jen, ``Global Properties of Cellular Automata,'' Los Alamos report LA-UR-85-1218, 1985; J. Stat. Phys., in press.

[23] J. Guckenheimer and P. Holmes, ``Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields,'' Springer-Verlag, New York/Berlin, 1983.

[24] J. Milnor, Entropy of cellular automaton-maps, Institute for Advanced Study preprint, May 1984; Directional entropies of cellular automaton maps, Institute for Advanced Study preprint, October 1984.

[25] Ya. Sinai, An answer to a question by J. Milnor, Comment. Math. Helv. 60 (1985), 173.

[26] N. Packard, Complexity of growing patterns in cellular automata, in ``Dynamical systems and cellular automata,'' (J. Demongeot, E. Goles, and M. Tchuente, Eds.), Academic Press, New York, 1985.

[27] R. Feynman, private communication.

[28] R. Brayton, G. Hachtel, C. McMullen, and A. Sangiovanni-Vincentelli, ``Logic Minimization Algorithms for VLSI Synthesis,'' Kluwer, Boston, 1984.

[29] R. Rudell, ``Espresso software program,'' Computer Science Dept., University of California, Berkeley, 1985.

[30] S. Wolfram, Geometry of binomial coefficients, Amer. Math. Monthly 91 (1984), 566.

[31] M. Furst, J. Saxe, and M. Sipser, Parity, circuits, and the polynomial-time hierarchy, Math Systems Theory 17 (1984), 13.

[32] C. Feynman and R. Feynman, private communication.

[33] M. Minsky, ``Computation: Finite and Infinite Machines,'' Prentice-Hall, Englewood Cliffs, N.J., 1967.

[34] B. Harris, Probability distributions related to random mappings, Ann. Math. Statist. 31 (1960), 1045.

[35] G. Marsaglia, A current view of random number generators, in ``Proc. Computer Sci. and Statistics, 16th Sympos. on the Interface,'' Atlanta, March 1984.

[36] G. W. Snedecor and W. G. Cochran, ``Statistical Methods,'' Iowa State Univ. Press, Ames, 1967.

[37] W. Beyer, N. Metropolis and J. R. Neergaard, Statistical study of digits of some square roots of integers in various bases, Math. Comput. 24 (1970), 455.

[38] S. Wagon, Is normal?, Math. Intelligencer 7 (1985), 65.

[39] T. Toffoli, CAM: A high-performance cellular-automaton machine, Physica D 10 (1984), 195; K. Steiglitz and R. Morita, A multi-processor cellular automaton chip, in ``Proc. 1985 IEEE International Conf. on Acoustics, Speech, and Signal Processing,'' March 1985.

[40] J. Salem, Thinking Machines Corporation report, to be published.

[41] G. Hedlund, Endomorphisms and automorphisms of the shift dynamical system, Math. Systems Theory 3 (1969), 320; G. Hedlund, private communication.

[42] N. Margolus, Physics-like models of computation, Physica D 10 (1984), 81.

[43] S. Wolfram, ``SMP Reference Manual,'' Computer Mathematics Group, Inference Corporation, Los Angeles, 1983.

[44] D. Hillis, ``The Connection Machine,'' MIT Press, Cambridge, Mass., 1985.

[45] P. Grassberger, ``Towards a quantitative theory of self-generated complexity,'' Wuppertal preprint (1986).

[46] S. Wolfram, Cryptography with cellular automata, in ``Proc. CRYPTO 85,'' August 1985.

previous  l  next