Are chaotic systems dynamically random ?

Karl Svozil¹
Institute for Theoretical Physics,
Technical University Vienna,
Karlsplatz 13, A-1040 Vienna, Austria.

Abstract

1. The classical deterministic continuum physics induces an indeterminism which is at least as strong as the probabilistic interpretation of the Schrödinger wave function-``Almost all'' (with respect to an arbitrary measure) elements of the continuum are uncomputable, i.e., they cannot be calculated by an algorithm on a universal computational device [1]. Therefore, if one assumes equidistribution, the initial configuration of a classical system must be represented by an uncomputable number with probability one. Since present-day definitions of uncomputability are essentially equivalent to (normalized) randomness [2,3], this renders chaotic motion for deterministic evolution functions capable of ``unfolding'' the randomness of the initial values. A sufficient criterion for such an evolution function is the instability of trajectories towards variations of the initial configuration dX₀, such that at later times t and for positive Lyapunov exponent l⁺, dX_t » dX₀ exp(l⁺ t). In this sense the ``deterministic chaos'' of classical physics originates in the assumption of the continuum (see also refs. [4,3]).

Quantum theory partially circumvents these uncomputabilities by postulating a discrete phase space. Nevertheless, despite a discrete state space for bounded systems, the Schrödinger wave function is represented as element of a continuum. Moreover, the probabilistic interpretation of the Schrödinger wave function, which undergoes a deterministic evolution between state preparation and measurement, is generally perceived as an expression of indeterminism.

2. Rather than attempting a deeper investigation of the differences between classical and quantum physics with respect to the random evolution of the Schrödinger wave function (see for instance refs. [5,6,7,8,9,3]), this Letter deals with a specification of the appropriateness of formal notions of randomness for physical chaotic motion. Thereby, techniques from algorithmic complexity theory and the theory of recursive functions provide a powerful basis.

Heuristically speaking, complexity is a measure of the resources necessary to perform a computation. These resources can be grouped into the following two categories. (i) Dynamic or computational complexity measures characterize the minimal amount of time (and storage capacity), whereas (ii) static or algorithmic complexity measures specify the minimal program size (and loop depth) necessary to perform a computational task. The associated definitions of randomness are based upon intuitive notions of incompressibility-either in time resources, such that no computational ``shortcut'' exists [10], or in program size, such that no shorter description interpretable as generating law [11] may reproduce a random timeflow. The formal definitions will be given next. They rest upon the representation of an experimental sequence in a symbolic string x [2].

The static complexity H(x) of a string x is defined to be the length of the shortest program p which runs on a computer C and generates the output x, i.e., H(x) = inf_{C(p) = x} length(p). If no program makes a computer output x, then H(x) = ¥.

A sequence x is absolutely Chaitin random (ACR) [11,12,13] if the static complexity of the initial segment x(n) = x₁¼x_n of length n does not drop arbitrarily far below n, i.e., lim_{n® ¥} H[x(n)]-n > -¥.

It has been proved [13] that an ACR sequence passes all statistical tests of randomness, such as frequency tests and that like. Therefore, ACR is equivalent to previous notions of randomness proposed by Martin-Löf, Solovay and others, based upon statistical criteria [13,3].

For physical applications, normalized ACR, henceforth called CR randomness, is very important [2]. An infinite sequence x is CR random, if K(x) = lim_{n® ¥} H(x(n))/n > 0. This notion of randomness is equivalent to uncomputability.

The normalized dynamical (computational) complexity K_D(x(n)) of a sequence x(n) = x₁¼x_n is the number of computing steps it takes for the fastest program p running on machine M to calculate an arbitrary i'th position x_i of x(n), devided by n, i.e.,
K_D(x(n)) = sup_{i = 1,¼,n}inf_{M(p) = xi} [computing  steps(M (p))]/ n.

An infinite sequence x is T-random (TR) iff for the fastest program running on M the number of computing steps t for calculating an arbitrary n-th position x_n of x is of the order of or greater then n; that is t(n) ³ O (n), or

K_D(x) = lim_{n® ¥}K_D(x(n)) = limsup_n®¥ t(n)/ n > 0.

Both K and K_D are intractable, i.e., there exists no ``systematic'' way to derive them. This is ultimately a consequence of Gödel's celebrated incompleteness theorem [14,1,15]. Moreover, TR is a machine dependent concept (for more details, see ref. [3]). Table 1 schematically shows the various forms of complexity and the

associated types of randomness.

complexity	static	algorithmic/	Chaitin/Martin-Löf/Solovay
		program size	randomness
		loop depth	-
	dynamic	computational/	T-randomness
		time
		storage size	-

Several attempts have been made in the literature to propose complexity measures which grasp the intuitive notion of ``organization''. These measures shall not be critically discussed here, but their enumeration seem in order. The notion of ``logical depth'' was introduced by Bennett, ref. [16]. It comes close to time complexity. A notion of ``self-generating'' complexity was proposed by Grassberger in ref. [17]. A criterion called ``thermodynamic depth'' has been introduced by Lloyd and Pagels, ref. [20] and is critically reviewed in [3].

3. In what follows, a classification of chaotic motion with respect to the computability of the initial values and the evolution functions, together with the type of randomness, will be given.

(i) Chaos I is generated by a computable evolution of a system with uncomputable (CR) initial values. If the initial value is element of the continuum, the probability that it is random is one, for ``almost all'' initial values are random reals. The randomness of the initial value ``unfolds'' in the deterministic time evolution [18]. This is precisely the signature for chaos in classical, deterministic continuum mechanics-the evolution of suitable (positive Lyapunov exponents) deterministic ( = computable) functions with initial values from a continuous spectrum, which serves as a kind of ``pool of random reals''. Therefore, the randomness of a classical deterministic chaos resides in its initial configuration.

(ii) Chaos II is generated by the uncomputable evolution of a system with computable initial values. It operates with computable initial values and uncomputable evolution laws.

(iii) Chaos III is generated by the uncomputable evolution of a system with uncomputable initial values.

Whereas chaos of class I, II and III supports CR, it assumes unconceivably complex physical systems. The following chaos class can, for finite times, only support TR. It has the advantage of requireing merely computability, in some cases only finite resources.

(iv) Chaos IV is generated by the computable evolution of a system with computable initial values. The (incompressible) dynamic complexity of TR sequences is generated by the unfolding of a computable, but TR initial value (the associated evolution law must have positive Lyapunov exponent(s)), or by a dynamically incompressible algorithm and arbitrary initial values. One relevant result of the theory of computability is that computable algorithms may have uncomputable limits [1]. Therefore, with ``suitable'' evolution functions and in the limit of infinite time, chaos IV is capable of becoming CR random. In Table 2 the various aspects of the four classes of chaos are represented schematically.

	deterministic	indeterministic
computable	chaos IV	chaos II
initial	T-random	Chaitin random
values	(Chaitin random)	nonrecursive
	recursive resources	resources
	Cellular	single quantum
	Automata	events ?
uncomputable	chaos I	chaos III
initial	Chaitin random	Chaitin random
values	nonrecursive	nonrecursive
	resources	resources
	deterministic	single quantum
	continuum theory	events ?

4. One central result of symbolic dynamics [2] can be formulated as follows. For chaos I and with probability one (i.e., for random initial values), the normalized static complexity K(x) of single trajectories (representable as symbolic string x = x₀x₁x₂¼) is equal to the overall metric entropy measure h_m (f) of a dynamic system with evolution function [19] f, and to the sum of all positive Lyapunov exponents, K(x) = h_m (f) = å_{l⁺ > 0}l⁺. This connection between entropy measure and the algorithmic complexity measure of single trajectories provide a powerful link of algorithmic information theory and the theory of computability on the one hand and statistical physics and thermodynamics on the other hand.

In what follows, I shall concentrate on speculations concerning these connections for the constructive chaos IV. The capability of computable functions to ``produce'' uncomputable output on computable initial values may have some far-reaching consequences in the physical perception of reversibility. Heuristically speaking, algorithmic complexity may be ``created'' by an investment of dynamic complexity, for instance by an (infinite) amount of time. One may therefore define the ratio R = dK/dK_D and call a system for which on the average R > 0, ``creative'', expressing the fact that algorithmic complexity is created. In this sense, the above equivalence between K of single trajectories and the overall entropy measure h<sub>m</sub> may also hold for a suitable, i.e., ``creative'', chaos IV. It may not be unjustified to speculate that creativity induces a unique time direction, and that the creation of algorithmic complexity is a formal aspect of irreversibility.

Since both K and K_D are uncomputable, R is uncomputable. One may, nevertheless, employ heuristic measures such as standard type of compression algorithms for a bound from above on K and K_D, and hence approximate R-such a method is not unfamiliar in physics, when one is forced to apply operational entropy measures which need not coincide with the exact ones. This is demonstrated by the following example. Fig. 1 shows Pascal's triangle, mod 2, representing even and odd binomial coefficients, which may be locally generated by an asymmetric Cellular Automaton with the following nontrivial rules (all others zero) 1/0/0® 1,    0/1/0® 1,    1/0/1® 1,    0/1/1® 1. Fig. 2 shows a heuristic study of K and R on this structure. On the average, there is an increase of K, corresponding to a positive R. Hence, the heuristic compression algorithm for the determination of K and R induces a time arrow. From this point of view, one may expect that further investigations will, for deterministic reversible systems with computable initial values, yield new insight into the second law of thermodynamics.

5. Besides a classification of chaos, a constructive, i.e., computable approach to random physical motion has been attempted. All chaos classes may yield identical forms of random physical motion. Chaos IV has the advantage that it is conceivable and that it is capable of rendering a limit which can be directly linked to entropy measures.

This work was supported in part by the Erwin-Schrödinger-Gesellschaft.

Figure captions

Fig.1 Pascal's triangle (mod 2) is equivalent to the evolution of a one dimensional state-2 Cellular Automaton. Dots and blanks indicate the digits 0 and 1, respectively.

Fig.2 Heuristic toy model study of R = dK/dK_D on Pascal's triangle (mod 2), drawn in Fig. 1. A standard (Huffman) compression algorithm for the calculation of the algorithmic complexity was used. This can however yield only a bound from above on H.

References

[1]

H. Rogers, Theory of Recursive Functions and Effective Computability (MacGraw-Hill, New York 1967)

[2]

V. M. Alekseev and M. V. Yakobson, Physics Reports 75, 287 (1981)

[3]

K. Svozil, Logical Physics I: Foundations of Chaos, Technical University Vienna preprint, Feruary 1989

[4]

J. Ford, Chaos: solving the unsolvable, predicting the unpredictable, in Chaotic Dynamics and Fractals, ed. by M. F. Barnsley and S. G. Demko (Akademic Press, New York 1986)

[5]

N. S. Krylov, Works in the Foundations of Statistical Mechanics (Princeton University Press, Princeton 1979)

[6]

B. V. Chirikov, F. M. Izrailev and D. L. Shepelyansky, Soviet Scientific Review 2C, 209 (1981);

[7]

G. Casati, B. V. Chirikov and D. L. Shepelyanski, Phys. Rev. Lett. 53, 2525 (1984)

[8]

G. Casati, B. V. Chirikov, I. Guarneri and D. L. Shepelyanski, Phys. Rev. Lett. 57, 823 (1986)

[9]

G. Casati, B. V. Chirikov, I. Guarneri and D. L. Shepelyanski, Milano university preprint, 1986; Novosibirsk preprint 87-30

[10]

St. Wolfram, Physical Review Letters 54, 735 (1985)

[11]

G. J. Chaitin, J. Assoc. Comput. Mach. 22, 329 (1975); Advances in Applied Mathematics 8, 119 (1987) and references cited

[12]

G. J. Chaitin, Information, Randomness and Incompleteness (World Scientific, Singapore 1987)

[13]

G. J. Chaitin, Algorithmic Information Theory (Cambridge University press, Cambridge 1987)

[14]

K. Gödel, Monatshefte für Mathematik und Physik 38, 173 (1931).

[15]

C. Calude, Theories of Computational Complexity (North-Holland, Amsterdam 1988)

[16]

Ch. H. Bennett, in Emerging Synthesis in Science, ed. by D. Pines (Academic Press, New York 1985).

[17]

P. Grassberger, International Journal of Theoretical Physics 25, 907 (1986)

[18]

This can be seen by considering a specific form of the logistic equation x_n+1 = ax_n (1-x_n); for a = 4 and after the variable transformation x_n = sin²(pX_n) one obtains a map f:X_n® X_n+1 = 2X_n (mod 1), where (mod 1) means that one has to drop the integer part of 2X_n. By assuming a starting value X₀, the formal solutions to n iterations is f⁽ⁿ⁾(X₀) = X_n = 2ⁿX₀ (mod 1). Notice that f is computable and linear. If X₀ is in binary representation, this is just n times a left shift of the digits of X₀, followed by a left truncation before the decimal point. Now assume X₀ Î (0,1) is CR. Then the computable function f⁽ⁿ⁾(X₀) yields a random map onto itself. The point is that although the evolution function f itself is recursive and linear, X₀ is random, and f ``unfolds'' the ``information'' contained in X₀.

[19]

f has to be a C²-diffeomorphism preserving an ergodic Borel measure m.

[20]

S. Lloyd and H. Pagels, Annals of Physics (N.Y.) 188, 186 (1988)

Footnotes:

¹ Computer address: Bitnet (EARN): E1360DAB at AWIUNI11.