Notes

[1] For example, R. Shaw, Z. Naturforsch. 36A, 80 (1981), and in Chaos and Order in Nature, edited by H. Haken (Springer, New York, 1981).

[2] An analogous cellular automaton [S. Wolfram, Nature (London) 311, 419 (1984), and references therein] has evolution rule , so that with time the value of a particular site is determined by the value of progressively more distant initial sites.

[3] For example, Order in Chaos, edited by D. Campbell and H. Rose (North-Holland, Amsterdam, 1982). Many processes analyzed in dynamical systems theory admit ``Markov partitions'' under which they are directly equivalent to the shift mapping. But in some measurements (say of with four bins) their deterministic nature may introduce simple regularities, and ``deterministic chaos'' may be said to occur. (This term would in fact probably be better reserved for the autoplectic processes to be described below.)

[4] This is probably also true of at least the lower levels of human sensory processing [for example, D. Marr, Vision (Freeman, San Francisco, 1982); B. Julesz, Nature (London) 290, 91 (1981)].

[5] The validity of Monte Carlo simulations tests the random sequences that they use. But most stochastic physical processes are in fact insensitive to all but the simplest equidistribution and statistical independence properties. (Partial exceptions occur when long-range order is present.) And in general no polynomial-time simulation can reveal patterns in effectively random sequences.

[6] For example, D. Knuth, Seminumerical Algorithms (Addison-Wesley, Reading, Mass., 1981).

[7] Some sophisticated statistical procedures, typically involving the partitioning of high-dimensional spaces, seem to take exponential time. But most take close to linear time. It is possible that those used in practice can be characterized as needing time on computers with processors (and so be in the computational complexity class NC) [cf. N. Pippenger, Proceedings of the Twentieth IEEE Symposium on Foundations of Computer Science (IEEE, New York, 1979); J. Hoover and L. Ruzzo, unpublished.]

[8] For example, R. Hamming, Coding and Information Theory (Prentice-Hall, Englewood Cliffs, 1980).

[9] G. Chaitin, J. Assoc. Comput. Mach. 13, 547 (1966), and 16, 145 (1969), and Sci. Amer. 232, No. 5, 47 (1975); A. N. Kolmogorov, Problems Inform. Transmission 1, 1 (1965); R. Solomonoff, Inform. and Control 7, 1 (1964); L. Levin, Soviet Math. Dokl. 14, 1413 (1973). Compare J. Ford, Phys. Today 33, No. 4, 40 (1983). Note that the lengths of programs needed on different universal computers differ only by a constant, since each computer can simulate any other by means of a fixed ``interpreter'' program.

[10] Quantum mechanics suggests that processes such as radioactive decay occur purely according to probabilities, and so could perhaps give absolutely random sequences. But complete quantum mechanical measurements are an idealization, in which information on a microscopic quantum event is spread through an infinite system. In finite systems, unmeasured quantum states are like unknown classical parameters, and can presumably produce no additional randomness. Suggestions of absolute randomness probably come only when classical and quantum models are mixed, as in the claim that quantum processes near black holes may lose information to space-time regions that are causally disconnected in the classical approximation.

[11] In the cases now known, recognition of any pattern seems to involve essentially complete reconstruction of the original program, but this may not always be so (L. Levin, private communication).

[12] In some cases, such as optimization or eigenvalue problems in the complexity class NP [e.g., M. Garey and D. Johnson, Computers and Interactability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979)], even each individual test may take exponential time.

[13] The sequence certainly passes the standard statistical tests of Ref. 6, and contains all possible subsequences up to length at least 12. It has also been proved that only at most one vertical sequence in the pattern of Fig. 1 can have a finite period [E. Jen, Los Alamos Report No. LA-UR-85-1218 (to be published)].

[14] For example, D. E. R. Denning, Cryptography and Data Security (Addison-Wesley, Reading, Mass., 1982). Systems like Fig. 1 can, for example, be used for ``stream ciphers'' by adding each bit in the sequences produced with a particular seed to a bit in a plain-text message.

[15] For example, O. Martin, A. Odlyzko, and S. Wolfram, Commun. Math. Phys. 93, 219 (1984).

[16] B. Jansson, Random Number Generators (Almqvist & Wiksells, Stockholm, 1966).

[17] They are one-symbol-deletion tag sequences [A. Cobham, Math. Systems Theory 6, 164 (1972)], and can be represented by generating functions algebraic over [G. Christol, T. Kamae, M. Mendes France, and G. Rauzy, Bull. Soc. Math. France 108, 401 (1980); J.-M. Deshouillers, Seminar de Theorie des Nombres, Université de Bordeaux Exposé No. 5, 1979 (unpublished); M. Dekking, M. Mendes France, and A. van der Poorten, Math. Intelligencer 4, 130, 173, 190 (1983)]. Their self-similarity is related to the pumping lemma for regular languages [e.g., J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages and Computation (Addison-Wesley, Reading, Mass., 1979)]. More complicated sequences associated with context-free formal languages can also recognized in polynomial time, but the recognition problem for context-sensitive ones is -space complete.

[18] For example, A. M. Frieze, R. Kannan, and J. C. Lagarias, in Twenty-Fifth IEEE Symposium on Foundations of Computer Science (IEEE, New York, 1984). The sequences also typically fail certain statistical randomness tests, such as multidimensional spectral tests (Ref. 6). They are nevertheless probably random with respect to all NC computations [J. Reif and J. Tygar, Harvard University Computation Laboratory Report No. TR-07-84 (to be published)].

[19] For example, G. Choquet, C. R. Acad. Sci. (Paris), Sec. A 290, 575 (1980); cf. J. Lagarias, Amer. Math. Monthly 92, 3 (1985). (Note that with appropriate boundary conditions a finite-size version of this system is equivalent to a linear congruential pseudorandom number generator.)

[20] A. Shamir, Lecture Notes in Computer Science, 62, 544 (1981); S. Goldwasser and S. Micali, J. Comput. Sys. Sci. 28, 270 (1984); M. Blum and S. Micali, SIAM J. Comput. 13, 850 (1984); A. Yao, in Twenty-Third IEEE Symposium on Foundations of Computer Science (IEEE, New York, 1982); L. Blum, M. Blum, and M. Shub, in Advances in Cryptology: Proceedings of CRYPTO-82, edited by D. Chaum, R. Rivest, and A. T. Sherman (Plenum, New York, 1983); O. Goldreich, S. Goldwasser, and S. Micali, in Twenty-Fifth IEEE Symposium on Foundations of Computer Science (IEEE, New York, 1984).

[21] For example, M. Garey and D. Johnson, Ref. 12.

[22] For example, L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences (Wiley, New York, 1974).

[23] A polynomial-time procedure is also known for recognizing solutions to more complicated algebraic or trigonometric equations (R. Kannan, A. K. Lenstra, and L. Lovasz, Carnegie-Mellon University Technical Report No. CMU-CS-84-111).

[24] Many localized structures have been found (D. Lind, private communication).

[25] S. Wolfram, Phys. Rev. Lett. 54, 735 (1985).

[26] For example, U. Frisch, Phys. Scr. T9, 137 (1985).

[27] G. Ahlers and R. W. Walden, Phys. Rev. Lett. 44, 445 (1980).

[28] For example, M. Brachet et al., J. Fluid Mech. 130, 411 (1983).

previous