|
Origins of Randomness in Physical Systems (1985) |
|
There are many physical processes that seem random or chaotic. They appear to follow no definite rules, and to be governed merely by probabilities. But all fundamental physical laws, at least outside of quantum mechanics, are thought to be deterministic. So how, then, is apparent randomness produced?
One possibility is that its ultimate source is external noise, often from a heat bath. When the evolution of a system is unstable, so that perturbations grow, any randomness introduced through initial and boundary conditions is transmitted or amplified with time, and eventually affects many components of the system [1]. A simple example of this ``homoplectic'' behavior occurs in the shift mapping 
. The time sequence of bins, say, above and below 
visited by 
is a direct transcription of the binary-digit sequence of the initial real number 
[2]. So if this digit sequence is random (as for most uniformly sampled in the unit interval) then so will the time sequence be; unpredictable behavior arises from a sensitive dependence on unknown features of initial conditions [3]. But if the initial condition is ``simple,'' say a rational number with a periodic digit sequence, then no randomness appears.
There are, however, systems which can also generate apparent randomness internally, without external random input. Figure 1 shows an example, in which a cellular automaton evolving from a simple initial state produces a pattern so complicated that many features of it seem random. Like the shift map, this cellular automaton is homoplectic, and would yield random behavior given random input. But unlike the shift map, it can still produce random behavior even with simple input. Systems which generate randomness in this way will be called ``autoplectic.''
(
denotes addition modulo two, and 
Boolean disjunction). Despite the simplicity of its specification, many features of the pattern (such as the sequence of site values down the center column) appear random.
In developing a mathematical definition of autoplectic behavior, one must first discuss in what sense it is ``random.'' Sequences are commonly considered random if no patterns can be discerned in them. But whether a pattern is found depends on how it is looked for. Different degrees of randomness can be defined in terms of the computational complexity of the procedures used.
The methods usually embodied in practical physics experiments are computationally quite simple [4,5]. They correspond to standard statistical tests for randomness [6], such as relative frequencies of blocks of elements (dimensions and entropies), correlations, and power spectra. (The mathematical properties of ergodicity and mixing are related to tests of this kind.) One characteristic of these tests is that the computation time they require increases asymptotically at most like a polynomial in the sequence length [7]. So if in fact no polynomial-time procedure can detect patterns in a sequence, then the sequence can be considered ``effectively random'' for practical purposes.
Any patterns that are identified in a sequence can be used to give a compressed specification for it. (Thus, for example, Morse coding compresses English text by exploiting the unequal frequencies of letters of the alphabet.) The length of the shortest specification measures the ``information content'' of a sequence with respect to a particular class of computations. (Standard Shannon information content for a stationary process [8] is associated with simple statistical computations of block frequencies.) Sequences are predictable only to the extent that they are longer than their shortest specification, and so contain information that can be recognized as ``redundant'' or ``over-determined.''
Sequences generated by chaotic physical systems often show some redundancy or determinism under simple statistical procedures. (This happens whenever measurements extract information faster than it can be transferred from other parts of the system [1].) But typically there remain compressed sequences in which no patterns are seen.
A sequence can, in general, be specified by giving an algorithm or computer program for constructing it. The length of the smallest possible program measures the ``absolute'' information content of the sequence [9]. For an ``absolutely random'' sequence the program must essentially give each element explicitly, and so be close in length to the sequence itself. But since no computation can increase the absolute information content of a closed system [except for 
from input of ``clock pulses''], physical processes presumably cannot generate absolute randomness [10]. However, the numbers of possible sequences and programs both increase exponentially with length, so that all but an exponentially small fraction of arbitrarily chosen sequences must be absolutely random. Nevertheless, it is usually undecidable what the smallest program for any particular sequence is, and thus whether the sequence is absolutely random. In general, each program of progressively greater length must be tried, and any one of them may run for an arbitrarily long time, so that the question of whether it ever generates the sequence may be formally undecidable.
Even if a sequence can ultimately be obtained from a small specification or program, and so is not absolutely random, it may nevertheless be effectively random if no feasible computation can recover the program [11]. The program can always be found by explicitly trying each possible one in turn [12]. But the total number of possible programs increases exponentially with length, and so such an exhaustive search would soon become infeasible. And if there is no better method the sequence must be effectively random.
In general, one may define the ``effective information content'' 
of a sequence to be the length of the shortest specification for it that can be found by a feasible (say polynomial time) computation. A sequence can be considered ``simple'' if it has small . (often normalized by sequence length) provides a measure of ``complexity,'' ``effective randomness,'' or ``computational unpredictability.''
Increasing can be considered the defining characteristic of autoplectic behavior. Examples such as Fig. 1 suggest that can increase through polynomial-time processes. The rule and initial seed have a short specification, with small . But one suspects that no polynomial time computation can recover this specification from the center vertical sequence produced, or can in fact detect any pattern in it [13]. The polynomial-time process of cellular automaton evolution thus increases , and generates effective randomness. It is phenomena of this kind that are the basis for cryptography, in which one strives to produce effectively random sequences whose short ``keys'' cannot be found by any practical cryptanalysis [14].
The simplest mathematical and physical systems (such as the shift mapping) can be decomposed into essentially uncoupled components, and cannot increase . Such systems are nevertheless often homoplectic, so that they transfer information, and with random input show random behavior. But when their input is simple (low ), their behavior is correspondingly simple, and is typically periodic. Of course, any system with a fixed finite total number of degrees of freedom (such as a finite cellular automaton) must eventually become periodic. But the phenomena considered here occur on time scales much shorter than such exponentially long recurrences.
Another class of systems widely investigated consists of those with linear couplings between components [such as a cellular automaton in which 
]. Given random input, such systems can again yield random output, and are thus homoplectic. But even with simple input, they can produce sequences which pass some statistical tests of randomness. Examples are the standard linear congruence and linear-feedback shift-register (or finite additive cellular automaton [15]) systems used for pseudorandom number generation in practical computer programs [6,16].
Characteristic of such systems is the generation of self-similar patterns, containing sequences that are invariant under blocking or scaling transformations. These sequences are almost periodic, but may contain all possible blocks of elements with equal frequencies. They can be considered as the outputs of finite-state machines (generalized Markov processes) given the digits of the numerical positions of each element as input [17]. And although the sequences have certain statistical properties of randomness, their seeds can be found by comparatively simple polynomial-time procedures [18]. Such systems are thus not autoplectic (with respect to polynomial-time computations).
Many nonlinear mathematical systems seem, however, to be autoplectic, since they generate sequences in which no patterns have ever been found. An example is the sequence of leading digits in the fractional part of successive powers of 
[19] (which corresponds to a vertical column in a particular 
, 
cellular automaton with a single site seed).
Despite extensive empirical evidence, almost nothing has, however, been proved about the randomness of such sequences. It is nevertheless possible to construct sequences that are strongly expected to be effectively random [20]. An example is the lowest-order bits of 
, where 
and 
are large primes [20]. The problem of deducing the initial seed , or of substantially compressing this sequence, is equivalent to the problem of factoring large integers, which is widely conjectured to require more than polynomial time [21].
Standard statistical tests have also revealed no patterns in the digit sequences of transcendental numbers such as 
, 
, and 
[22] (or continued-fraction expansions of or of most cubic irrational numbers). But the polynomial-time procedure of squaring and comparing with an integer does reveal the digits of, say, as non-random [23]. Without knowing how the sequence was generated, however, such a very special ``statistical test'' (or program) can probably only be found by explicit enumeration of all exponentially many possible ones. And if a sequence passes all but perhaps exponentially few polynomial-time batteries of statistical tests, it should probably be considered effectively random in practice.
Within a set of homoplectic dynamical systems (such as class 3 or 4 cellular automata) capable of transmitting information, all but the simplest seem to support sophisticated information processing, and are thus expected to be autoplectic. In some cases (quite probably including Fig. 1 [24]) the evolution of the system represents a ``complete'' or ``universal'' computation, which, with appropriate initial conditions, can mimic any other (polynomial-time) computation [21]. If short specifications for sequences generated by any one such computation could in general be found in polynomial time, it would imply that all could, which is widely conjectured to be impossible. (Such problems are NP-complete [21].)
Many systems are expected to be computationally irreducible, so that the outcome of their evolution can be found essentially only by direct simulation, and no computational short cuts are possible [25]. To predict the future of these systems requires an almost complete knowledge of their current state. And it seems likely that this can be deduced from partial measurements only by essentially testing all exponentially many possibilities. The evolution of computationally irreducible systems should thus generically be autoplectic.
Autoplectic behavior is most clearly identified in discrete systems such as cellular automata. Continuous dynamical systems involve the idealization of real numbers on which infinite-precision arithmetic operations are performed. For systems such as iterated mappings of the interval there seems to be no robust notion of ``simple'' initial conditions. (The number of binary digits in images of, say, a dyadic rational grows like 
, where is the highest power of 
in the map.) But in systems with many degrees of freedom, described for example by partial differential equations, autoplectism may be identified through discrete approximations.
Autoplectism is expected to be responsible for apparent randomness in many physical systems. Some features of turbulent fluid flow [26], say in a jet ejected from a nozzle, are undoubtedly determined by details of initial or boundary conditions. But when the flow continues to appear random far from the nozzle, one suspects that other sources of effective information are present. One possibility might be thermal fluctuations or external noise, amplified by homoplectic processes [1]. But viscous damping probably allows only sufficiently large-scale perturbations to affect large-scale features of the flow. (Apparently random behavior is found to be almost exactly repeatable in some carefully controlled experiments [27].) Thus, it seems more likely that the true origin of turbulence is an internal autoplectic process, somewhat like Fig. 1, operating on large-scale features of the flow. Numerical experiments certainly suggest that the Navier-Stokes equations can yield complicated behavior even with simple initial conditions [28]. Autoplectic processes may also be responsible for the widespread applicability of the second law of thermodynamics.
Many discussions have contributed to the material presented here; particularly those with C. Bennett, L. Blum, M. Blum, J. Crutchfield, P. Diaconis, D. Farmer, R. Feynman, U. Frisch, S. Goldwasser, D. Hillis, P. Hohenberg, E. Jen, R. Kraichnan, L. Levin, D. Lind, A. Meyer, S. Micali, J. Milnor, D. Mitchell, A. Odlyzko, N. Packard, I. Procaccia, H. Rose, and R. Shaw.
