|The Impact of Chaos on Science and Society (UNU, 1997, 394 p.)|
Mingzhou Ding, Celso Grebogi, and James A. Yorke
In this paper we discuss concepts and recent developments in chaotic dynamics. Our goal is to set the platform on which important questions can be raised and discussed in the future. In addition, from the history we review in this presentation it will become apparent that chaotic dynamics, before its vast implications outside of mathematics were generally appreciated over the past two decades, had endured steady progress ever since the end of the last century. This progress is forever emblematized by names such as Poincaré, Birkhoff, and Kolmogorov, whose seminal works laid the foundation for the explosive growth of research and applications of chaotic dynamics we are witnessing today.
As early as in the middle of last century it was already known to Maxwell  that physical systems could be sensitive to initial data. But systematic studies of chaotic dynamics were nonexistent until the works of Poincaré. In a series of papers written during the period 1881-1886, Poincaré  analysed and named many of the qualitative features displayed by dynamical systems, which have since become part of the standard knowledge for people working in this area. The influence of Poincaré's contribution can be further seen in the fact that many questions that intrigued him a century ago are still in the forefront of research today, although large strides of progress have been made since his time.
A typical dynamical system can exhibit a variety of temporal behaviour. To understand what delineates one type of behaviour from the other one may start by considering a simple continuous system on the plane. From the Poincaré-Bendixson theorem we know that, if a solution of such an autonomous system of differential equations is bounded and does not approach an equilibrium point, then the trajectory must spiral asymptotically to a periodic orbit (limit cycle). Hence, such autonomous systems in two dimensions cannot be chaotic. Higher dimensional autonomous differential equations and also autonomous discrete systems in the plane can exhibit much richer types of dynamics including chaos. An example of higher dimensional systems is the three-body problem in celestial mechanics, the study of which has direct implications on important questions such as whether the solar system is stable. Poincaré showed that three-body problems are in general non-integrable and phase space trajectories near some very special points, which he called homoclinic points, are necessarily very complicated. This observation may be regarded as the very first indication of chaotic behaviour in dynamical systems. The understanding of what happens near such a homoclinic point has evolved over many years. An important step was taken by Birkhoff  earlier this century whose results provided a more detailed depiction of the dynamics near homoclinic points. Cartwright and Littlewood  came across the same phenomenon of homoclinic points in their study of the Van der Pol equation. Levinson  simplified some of the work of Cartwright and Littlewood and was able to provide a more precise description of the very complicated behaviour of the simplified Van der Pol equation. Smale  explained their results by relating them to his horseshoe map (a rectangle is mapped across itself with the image folded into a horseshoe shape) which exhibits a chaotic invariant set whose dynamics can be thoroughly analysed. He showed that such horseshoes must be found near homoclinic points and furthermore embedded within such a horseshoe are infinitely many periodic points (of different periods) and infinitely many trajectories that remain in the horseshoe but oscillate irregularly without ever settling down to a periodic behaviour. Horseshoes are subsequently shown to exist in numerous nonlinear systems such as the Duffing and Van der Pol equations, and in prototypical maps, such as the Hénon map. At about the same time came the work of Peixoto  who made substantial contributions by introducing the concept of topological space into the study of differential equations and by making precise the meaning of two systems being qualitatively equivalent. Parallel to these developments are the works of the Russian school of mathematicians, notably among them Kolmogorov and his students [8-10]. We will comment further on their contributions in subsequent sections.
The existence of horseshoe per se does not imply that chaotic behaviour will be observed. The invariant set of the horseshoe itself is unstable. It is also interesting to note that while chaotic attractors seem always to contain homoclinic points, the existence of such points does not ensure that the attractor is chaotic, since there may be periodic attractors within the region. Proof of the existence of chaotic attractors for nonlinear maps which model physical systems remains an outstanding, but difficult, unresolved problem. Progress has been made for some prototypical maps. For example the one-dimensional quadratic map has been shown to have chaotic attractors for a set of parameter values with positive measure . Recently, an analogous result for the Hénon map with sufficiently small Jacobian was proved by Carleson and Benedicks .
The presence of chaotic orbits in a system has significant ramifications and can be observed indirectly even when the orbits are not attracting. When a system has multiple attractors, the boundaries between respective basins of attraction can exhibit very complicated patterns. For invertible maps of the plane, these boundaries can be fractal, making final state prediction extremely difficult for initial conditions near the boundary. Such boundaries typically contain horseshoes that, in turn, contain infinitely many unstable periodic orbits. There are still other non-attracting chaotic sets in a dynamical system that may manifest themselves as transient chaos. Such transient chaos and its characterization are important in practice to gain a proper understanding of the system. Thus, in general, studying the behaviour of chaotic sets, both attracting and not attracting, is an important problem for experimental and numerical systems.
II. Measuring chaos
When initial points of trajectories are known with finite precision, the exponential divergence of solutions means that information is lost as the trajectory is followed. The entropy is used to measure how many bits of information are lost per unit time. There are different definitions of entropy depending on how this concept is made precise and depending on which trajectories the information loss is averaged over.
In information theory the notion of (information) entropy was introduced by Shannon  in 1948. The use of entropy in dynamical systems was introduced by Kolmogorov  partially in collaboration with Sinai. In fact, Shannon's notion of entropy is essentially the same as Kolmogorov's (which is called "metric entropy"). A remarkable theorem due to Ornstein  states that the Bernoulli shifts, certain elementary dynamical systems, with the same entropy are equivalent; that is, there is a (discontinuous) change of variables that converts one into the other.
The topological entropy of a map f is a number h(f) which can be considered as a measure for the complexity of the dynamics of f averaged over all the bounded trajectories. Unlike Kolmogorov's concept, this entropy is defined for a region rather than for a probability measure. But they are closely related. Topological entropy was first introduced by Adier, Konheim, and McAndrew  in 1965. A more useful and mathematically equivalent definition was later given by Bowen . Recently the prospect of computing topological entropy has been enhanced by advances in relating it to other geometric quantities. In particular, it has been shown that for smooth maps the topological entropy is the maximum rate of volume growth of smooth disks . For an area-contracting diffeomorphism of a surface, the entropy can be determined by calculating the growth rate of the boundary length. (In this case, the boundary consists of a finite number of one-dimensional curves.) These results open the possibility of simple computational algorithms for evaluating topological entropy numerically. Such algorithms may also be of interest in applications.
B. Dimensions, measures, and Lyapunov exponents
Lebesgue's measure theory gives the notion of linear measure of sets on the real line, of plane measure of sets in the plane, of three-dimensional measure of sets in the three-dimensional space, and so on. But the ideas of linear, plane,... measures are not directly related to the number of dimensions of the space containing these sets. In the same way as the notion of length exists not only for sets on the real line, but also for lines lying in the space of arbitrary dimensions, the notion of linear measure can be extended to the sets of points in the space of any number of dimensions. This problem was noted and solved by Carathéodory  who gave a definition of the d-dimensional measure of a set in an n-dimensional space, where d and n ³ d are both arbitrary positive integers. Carathéodory's notion of dimension was later generalized by Hausdorff  to describe sets of non-integer dimensions, which is now known as the Hausdorff dimension of a set. Such sets with non-integer dimensions are called "fractal sets" (a term coined by Mandelbrot). Besicovitch made substantial contributions to the study of such fractal sets . In dynamical systems fractal sets are realized as strange attractors, which are complicated limit sets in the phase space to which typical orbits asymptote. The term "strange attractor" is invented by Ruelle and Takens  in connection with their work on the relevance of such attractors to the onset of turbulence.
Another concept of dimension is the capacity. The notion of capacity was first introduced by Kolmogorov , and it is a simplified version of the Hausdorff dimension. The advantage of the capacity dimension is that it is much easier to measure from data and so is more useful in practice. The value of the capacity dimension for a chaotic attractor indicates how much information is necessary to specify the location of points in the set within a given accuracy. For example, if one would like to know the set of points constituting the attractor within an accuracy e, then in order to specify the location of the attractor one has to specify the position of a minimal number of cubes with length e covering the attractor. For typical attractors it is believed that the Hausdorff dimension and the capacity dimension have the same value. But up to this date the validity of this conjecture is not rigorously known.
Determining the dimension of an attractor is the first level of knowledge necessary to characterize its dynamical properties. To fully understand the attributes of a strange attractor, one must also take into account the "density" or "distribution" of the points on the attractor. In computing the capacity, all the cubes needed to cover the attractor are of the same importance, although the visitation by a typical trajectory to some cubes can be much less frequent than to others. This disparity can be taken into account by introducing a probability measure on the attractor and weighing the cubes according to the measure contained in them. It is often assumed that there is such a measure, called the natural measure, which specifies the frequency with which a typical trajectory visits different regions of the attractor. The existence of a natural measure on any uniformly hyperbolic attractor is guaranteed by a result due to Bowen and Ruelle  with related results by Sinai . At the present time the existence of a natural measure for all other kinds of attractors remains an open question.
Another important concept for chaotic systems is that of Lyapunov exponents, first introduced by Oseledec . These exponents describe the asymptotic behaviour of the derivative of a map on the average, dictating the local behaviour of two nearby orbits. For each point x in the N-dimensional phase space we consider the eigenvalues of the Jacobian matrix of partial derivatives J(n) of the nth iterate of the map at x, where n is a positive integer. The Lyapunov numbers of f at x are the nth roots of the moduli of the eigenvalues of J(n) as n goes to infinity; the natural logarithms of these Lyapunov numbers at x are called the Lyapunov exponents of the map at x.
Time averages of functions are a standard measure of asymptotic behaviour in a dynamical system. They take on special relevance for chaotic systems. Ergodic theory  says that time averages can be computed as phase space averages, provided the function is weighed by the invariant natural measure. Natural measures have deep connections with other experimentally measureable quantites such as the fractal dimensions of attractors, Lyapunov exponents, and entropies.
A spectrum of dimensions characterizing probability distributions was introduced by Renyi . The simplest among them is the information dimension. It indicates how fast the information necessary to specify a point on the attractor increases as the number of digits or bits of accuracy is increased. The information dimension is more accessible for experimentalists than the capacity or Hausdoff dimension. Another related dimension is the Lyapunov dimension which is determined by the Lyapunov exponents of the system. An outstanding conjecture is that for typical dynamical systems the information dimension and the Lyapunov dimension are the same . Ledrappier and Young  proved that the information dimension of the sample measure resulting from the composition of N-dimensional random diffeomorphisms (N ³ 2) is given by the Lyapunov dimension as conjectured by Kaplan and Yorke. A proof of this for the non-random case does not exist except for N = 2.
The dimension that is most accessible from experimental data and has been most widely used is the correlation dimension introduced by Grassberger and Procaccia . But caution must be exercised in interpreting the results of such a calculation. In the past some claims based on this algorithm have generated controversies. Thus further analysis is needed to understand fully the limitations and remedies for such limitations associated with applying the Grassberger-Procaccia algorithm to real data.
An interesting aspect concerning dimension arises from the fact that the probability distribution of points on a chaotic attractor can be non-uniform in a very singular way. In particular, there can be an arbitrarily fine-scaled interwoven structure of regions where points of a typical trajectory are dense and regions where they are sparse. Such attractors have been called multifractals and can be characterized by the spectrum of Rényi dimensions. Loosely speaking this spectrum of dimensions consists of the dimensions of the dense and sparse regions of the attractor. The study of multifractals is an active area of research: new techniques and procedures computing and analysing the multifractal properties in conjunction with experiments are expected to be further developed in the future.
III. Routes to chaos
One of the central problems of chaos research for both theorists and experimentalists in science and engineering is the study of the onset of chaos in dissipative systems. This problem addresses the question, how does a system pass from being nonchaotic to being chaotic as some parameter of the system is varied continuously. Some of the routes by which a system moves from regular motion to chaotic motion are known. For example, for any constant vector field on the three-dimensional torus, we can choose a small perturbation which results in a chaotic attractor . More specifically, this means that after three successive Hopf bifurcations, the system is arbitrarily close to having a chaotic attractor.
There are four other important routes to chaos that have been identified and confirmed by numerical and physical experiments. They are period-doubling cascade, intermittency, crisis, and quasi-periodic routes. All of them can occur in one-dimensional discrete systems. The most prominent among them is the period-doubling cascade to chaos which was first observed in the quadratic maps by Myrberg .
The period-doubling onset of chaos exhibits universal behaviour. The geometric self-similarity in the bifurcation diagram has led the researchers, beginning with Feigenbaum , to employ the renormalization group techniques (originally developed for elementary particle theory and later for the study of phase transition in matter) to treat the phenomenon that ultimately explained the universal regularity in the bifurcation.
Another type of evolution from simple to chaotic dynamics is characterized by intermittency . In this scenario, stable regular behaviour changes at certain parameter values into what appears to be regular motion interrupted by sporadic bursts of chaotic behaviour. The route to chaos by intermittency is considered discontinuous because the phase space extent of the attracting set changes abruptly at the transition point. In this sense intermittency route is quite different from that of period doubling. On the other hand, the two are similar in the sense that they are both induced by local bifurcations.
Chaos can also be created through an event called crisis . The crisis route, like intermittency, is discontinuous but is caused by global developments such as crossing of stable and unstable manifolds. For parameter values before the crisis the attracting motion is nonchaotic, but there is typically a transient phase in which trajectories appear to be chaotic before settling into their time asymptotic regular motion. As the parameter value approaches the crisis value, the duration of the chaotic transient phase approaches infinity and, after the crisis, sustained chaotic motion ensues.
In the case of quasiperiodic onset of chaos, one can increase a non-linearity parameter, at the same time adjusting a second parameter to maintain quasiperiodicity of a certain type (e.g., keep the rotation number fixed). With the increment of the parameter in this fashion, the toroidal surface on which the quasiperiodic orbits are confined crumbles as a critical parameter value is reached. Again, renormalization group technique has been used to investigate the breakup of the torus .
Evidently renormalization group techniques are quite successful in treating the transition to chaos. Whether they can be extended to situations beyond the onset of chaos thus rendering a more complete understanding of the structure of fully chaotic multifractal strange attractors remains an open question.
All of the routes to chaos described thus far have been observed in physical experiments. For example, period-doubling cascades have been observed in fluid convection, in nonlinear circuits, and in lasers. Intermittency has been seen in Rayleigh-Bénard convection and in stirred chemical reactions. Crises have been seen in nonlinear circuits, in Josephson junctions, and in lasers. Quasiperiodic transitions to chaos have been seen in convection and solid state experiments. Computer simulations of the Lorenz system exhibit both intermittency and crisis. We remark that while the period doubling, intermittency, crisis, and quasiperiodicity routes to chaos have been documented in many systems, there undoubtedly remain other, as yet unknown, routes to chaos particularly in higher dimensional systems.
IV. Chaos in physical systems
Since the time of Poincaré, people have become aware of the complexity of chaotic dynamics and its relation to homoclinic points. This leads to the realization that chaotic behaviour should be rather common among dynamical processes. Yet the existence of a homoclinic point for a dissipative process does not imply the existence of a chaotic attractor. The chaotic behaviour might be transient in nature; the trajectories starting from some initial data might oscillate irregularly forever, but such initial conditions might lie on sets of vanishing probability measure. In that case, if the experimenter discards the beginning portion of the time evolution of a typical orbit, the asymptotic behaviour he observes would be very simple, perhaps a steady state.
By the 1960s a group of mathematicians had developed a wide variety of examples of chaotic systems, known as the Anosov systems , which had chaotic attractors. One important character of such systems is that they are structurally stable, meaning that small perturbations would leave the system unchanged (except for minor changes that were equivalent to changes in coordinates). The notion of structural stability was introduced by Andronov and Pontryagin . The work of Lefschetz  helped establish this theory in the West. Subsequently Smale  laid out a programme based on describing all structurally stable processes. It was believed at that time that every dynamical system would be perturbed slightly to yield some structurally stable systems, and it was clear that many of these structurally stable systems had chaotic attractors. These ideas and developments had relatively little impact on engineering and physical sciences at the time, however.
The state of awareness of chaotic behaviour changed dramatically in the 1970s. A number of events captured the imaginations of mathematicians and scientists alike:
1. An overlooked paper by Lorenz  was found that describes with remarkable clarity a computer study of a system with chaotic behaviour. Incidentally, this system, like most systems encountered in practice, turned out not to be structurally stable.
2. Hénon  and others both in the West and in the Soviet Union found examples of dynamical systems which exhibit in numerical experiments chaotic attractors.
3. Ruelle and Takens  explained how fluid turbulence might arise as a result of chaotic attractors.
4. Li and Yorke  gave simple one-dimensional examples that had erratic behaviour and they coined the term "chaos" to describe such behaviour which came to be the defining attribute of chaotic dynamics.
5. The papers of May  reported the period-doubling cascade route to chaos. (The papers of Myrberg published in the 1950s and 1960s were discovered only later.)
In the later 1970s, computer technology had evolved to the point where many scientists had available interactive computers with improved graphics. The examples of chaos mushroomed in practically every field of science. This advent of computer technology also led to a great disparity. The theorists made large strides of progress in their studies of differential equations and maps using computers: displaying the attractors, computing Lyapunov exponents and fractal dimensions. Even non-attracting chaotic sets such as fractal basin boundaries and strange saddles could be investigated in great detail. The experimentalists, on the other hand, have only limited techniques such as phase plots and power spectra. Even with this limited bag of tricks they have achieved great success in directly analysing their time series data. For example, using innovative experimental techniques, transitions from quasiperiodicity to chaos have been carefully studied in a variety of fluid flows . In addition experimentalists have studied in detail bifurcation sequences occurring as physical parameters are varied, alternating between chaos and periodicity. Such experimental findings provided concrete foundations for some theoretical predictions such as the Feigenbaum universal constants in the period-doubling cascade.
Many real systems that experimentalists deal with are infinite dimensional (e.g. fluids), and one might question whether theoretical results obtained for systems with low dimensionality are still applicable. Very recently, a set of theoretical techniques for addressing this question has been developed. An example is the method for finding the dimensionality of so-called inertial manifolds . Various examples that have been worked out show that low-dimensional systems often describe dynamics in infinite dimensional systems, and furthermore bounds on the required dimensionality have been obtained. While the confidence in the applicability of the broad body of knowledge of chaotic dynamics theory to real physical systems is growing, it still remains a problem as to how the existence of low-dimensional dynamics in a high or infinite dimensional system can be exploited to simplify numerical computations.
In 1980 Packard et al.  made a partial step towards parity between the experimentalists and theorists. They claimed that if a scalar time series is converted into an n-dimensional space by using a delay time T, then the evolution of these n-dimensional points is equivalent to the dynamics of the original system giving rise to the time series, provided that n is large enough. Theoretical justifications are given by Takens  who showed that such claims are consequences of the Whitney Embedding Theorem. These results made the computation of Lyapunov exponents, dimensions, and a host of other dynamical quantities from experimental data a reality. Thus soon after these progresses an upsurge of activities characterizing time series looking for evidence of deterministic dynamics followed. The systems examined range from simple nonlinear circuits to the human brain. The search for meanings of such dynamical quantities and related work on prediction is an active area of research today.
V. Noise and computer round-off errors
Because of the exponential divergence of the trajectories of nearby points on chaotic attractors, there are questions as to how closely experimentally generated or computer generated trajectories (with chaos-amplified experimental noise or computer roundoff errors) resemble "true" trajectories of the chaotic systems. More precisely, when one can choose a nearby initial condition yielding a true trajectory that stays near the noisy one, the system is said to have the shadowing property. Structurally stable systems have this property. In fact, Bowen  regards this property as the most important aspect of the "Axiom A Systems" (which are structually stable).
The problem is however that chaotic attractors found in applications are virtually never structurally stable. Thus a natural question is whether the shadowing property holds in these situations. Recent results [49, 50] show that even though a numerical trajectory will diverge from the true orbit with the same initial condition, there exists another true trajectory that stays near the numerical trajectory for a long period of time. In the Hénon map (a nonstructurally stable system), a typical numerically tested orbit computed with 14-digit precision is shadowed by a true orbit that stays within one millionth of the numerical one for one million iterates. Thus the answer to the above question for low (one- and two-) dimensional systems is affirmative, but for higher dimensional systems the situation remains much less clear. This is an important problem to be pursued in the future.
VI. Hamiltonian systems
A major direction of research in Hamiltonian systems has been the study of how the stability of an integrable system is lost as the system is perturbed from the non-integrable case. Phase space for an autonomous Hamiltonian with n degrees of freedom is 2n dimensional. With energy conservation trajectories are confined to move on the energy surface which is 2n - 1 dimensional. In the integrable case, each trajectory is further confined to an n-dimensional torus, and the nested tori taken together fill the energy surface. As the system is perturbed from the integrable case, the celebrated KAM theory guarantees that, for sufficiently small perturbations, many of the invariant tori remain.
The simplest nontrivial case is n = 2. This case is also of interest in many applications. The tori in this case are closed curves which bound regions of chaotic motion in the energy surface. Trajectories of the system are either moving on the tori or between them. As the perturbation is increased, more of the tori break up, giving rise to more chaotic motion. Such systems are conveniently studied by the method of Poincaré surface of section. The result is a two-dimensional area-preserving map. If the Hamiltonian system is integrable, the corresponding Poincaré map has orbits lying on invariant tori which converge to a fixed point. The rotation number of each tori under the map is a continuous function of the coordinates. To study the breakup of the invariant tori as the system is moved away from integrability we use area-preserving twisted maps of the annulus. Recently, it has been shown that given a number r between the rotation numbers of the map on the inside and outside boundaries of the annulus, there is an invariant set (called the Aubry-Mather set) with r as its rotation number . For rational rotation numbers, the invariant sets are periodic; for irrational numbers, the invariant sets are either dense on an invariant curve (called KAM curves after Kolmogorov , Arnold , and Moser ) or are Cantor sets. As a parameter of the system varies, driving it away from integrability, the KAM curves with irrational rotation numbers on the annulus may lose smoothness and disintegrate into Cantor sets called cantori. Other works on the break up of KAM curves in two-dimensional maps include the heuristic criterion of Chirikov  for the non-existence of a KAM curve of a rotation number, work of Greene  on the rotation number of isolated KAM curves, and the application by Kadanoff  and by Mackay  of renormalization group techniques to obtain characteristics of isolated KAM curves at criticality. Properties of the diffusive behaviour of orbits of strongly chaotic two-dimensional area-preserving maps have also been studied. In particular, chaotic orbits can be trapped in regions containing KAM surfaces for a long period of time before escaping. This "stickiness" effect has important implications for particle transport in Hamiltonian systems.
For systems with more than two degrees of freedom, our lack of understanding is particularly acute. In such systems, an n-dimensional torus does not divide the 2n - 1 dimensional energy surface. In fact, Arnold  has shown in a specific example that a small perturbation away from the integrable case can create a fine connected "web" of chaos permeating arbitrarily close to any point on the energy surface. Orbits initiated in this web will eventually visit every neighbourhood of the energy surface, even though this may take a long time. The study of the statistical properties of chaotic particle motion in such higher dimensional systems remains an underexplored and intriguing area of chaotic dynamics.
In contrast to integrable systems there is another extreme situation consisting of completely chaotic systems. A number of interesting systems are shown to belong to this class. In particular, Sinai  has obtained results that show that a system of elastically colliding hard spheres falls into this class. The significance of this result is that it gives a firm foundation to the hypothesis of statistical mechanics to a system that appears to be a reasonable, though idealized, model of reality. Hamiltonian systems encountered in applications are most likely to be neither integrable nor completely chaotic. The understanding of such systems is, for most purposes, still seriously lacking.
VII. Symbolic dynamics
One of the oldest techniques for the study of chaos is symbolic dynamics. The earliest examples of symbolic dynamics were constructed by Hadamard  and by Morse  for the geodesic flows on surfaces of negative curvature.
Symbolic dynamical systems are systems whose phase space consists of two-sided infinite sequences of symbols
x = ... x-2x-1x0x1x2 ...
where xn is chosen from a finite alphabet. In the simplest case, the sequence tells us whether a trajectory at time n is in a set A. Given a map and a set A in phase space, a sequence is associated with each trajectory so that xn is 1 if the trajectory is in A at time n, and otherwise xn is zero. If the phase space is partitioned into several sets, we need more than two symbols in our alphabet. Symbolic dynamics arises in a variety of situations. For example, in horseshoe maps, we write xn = 0 if the point is in the left half of the rectangle and xn = 1 if it is in the right. Then it is shown that, given any sequence 0s and 1s, there is a trajectory that visits the respective halves in that order. In this case we say that the symbolic dynamics is a full shift of two symbols.
The set of allowed sequences is invariant under the shift transformation. This means that, if a particular sequence is in a space of sequences, so is the sequence with all symbols shifted one place to the left (or to the right). In many cases, the symbolic dynamics is not a full shift, that is, certain lists of blocks of symbols are forbidden. For example, the space of sequences of 0s and 1s might have the rule that no blocks of five consecutive is can take place. As another example, certain symbols may be specified as never occurring immediately after certain other symbols. Such symbolic dynamics are called shifts of finite type. Mathematically, there are two types of important problems. (1) Determine the existence and properties of maps between two spaces of symbol sequences that commute with each other. (2) Describe the properties displayed under iteration by such maps mapping the space of sequences to itself. In accordance with the nature of abstract mathematics most of the basic theoretical work on problem (1) predated the realization of its relevance to physical problems.
Cellular automata give a large class of examples of the second type of problems. Their relevance to physics has been suggested, particularly in the context of using cellular automata to model various physical situations (dynamics of excitable media, fluids, phase transitions, etc.). One basic problem here is that there is an insufficient mathematical foundation for cellular automata: the model systems themselves are very poorly understood. However, there have been some nontrivial rigorous results. Further developments of the theory of symbol sequences are likely to be very useful in many different types of applications.
VIII. Concluding remarks
The intellectual heritage of chaotic dynamics can be traced all the way back to Maxwell and Poincaré. Numerous other people have contributed to thrust the field into an exciting enterprise of scientific research with impact felt far beyond mathematics and physics.
To a certain extent, the recent explosive growth in chaotic dynamics and its applications is underscored by the interdisciplinary character of the field. One essential ingredient has been the interaction between mathematicians, on the one hand, and scientists and engineers, on the other. Although mathematics can and indeed does generate its own problems, the focusing influence offered to mathematics by specific examples from physics, chemistry, engineering, and other fields directs attention to the issues that are most significant for science and technology. In turn, the insights afforded by basic theory provide a framework of ideas to scientists and engineers for organizing their thoughts and observations. This framework of ideas has cultivated fruitful results in explaining and understanding nonlinear phenomena in their respective fields of investigation.
In passing we remark that concepts and techniques developed in chaotic dynamics have greatly enhanced our ability to deal with complicated nonlinear processes in nature. The scope of the wide applications of chaotic dynamics is clearly conveyed by the contributions presented in this volume.
 L. Campbell and W. Garnett, The Life of James Clerk Maxwell, ch. 14 (Johnson Reprint Corporation, New York, 1969).
 H. Poincaré, Oeuvres, vol. 1 (Gauthier-Villars, Paris, 1950).
 G. D. Birkhoff, Collected Works, vols. 1 and 2 (American Mathematical Society, 1950).
 M. L. Cartwright and J. E. Littlewood, London Math. Soc. 20: 180 (1945).
 N. Levinson, Ann. Math. 50: 127 (1949).
 S. Smale, Bull. Amer. Math. Soc. 73: 747 (1967).
 M. M. Peixoto, Ann. Math. 69: 199 (1959).
 A. N. Kolmogorov, Dokl. Akad. Nauk. SSSR 98: 525 (1954).
 V. I. Arnold, Russ. Math. Surveys 18: 5 (1963).
 Ia. G. Sinai, Russ. Math. Surveys 25: 137 (1970).
 M. V. Jakobson, Comm. Math. Phys. 81: 30 (1981).
 L. Carleson and M. Benedicks, Ann. Math. 133: 73 (1991).
 C. E. Shannon, Bell Syst. Tech. J. 27: 379 (1948).
 A. N. Kolmogorov, Dokl. Akad. Nauk. SSSR 119: 861 (1958).
 D. S. Ornstein, Advances in Math. 4: 337 (1970).
 R. L. Adler, A. G. Konheim, and M. H. McAndrew, Trans. Amer. Math. Soc. 114: 309 (1965).
 R. Bowen, Equilibrium States and the Ergodic Theory of Anosov Diffeomorphisms. Lecture Notes in Mathematics, vol. 470 (Springer-Verlag, Berlin, 1975).
 S. Newhouse, in The Physics of Phase Space, Lecture Notes in Physics, vol. 278 (Springer-Verlag, Berlin, 1986).
 C. Carathéodory, Nach. Ges. Wiss. Göttinger, 406 (1914).
 F. Hausdorf, Math. Ann. 79: 157 (1919).
 A. Besicovitch, Math. Ann. 110: 321 (1934).
 D. Ruelle and F. Takens, Comm. Math. Phys. 20: 167 (1971).
 R. Bowen and D. Ruelle, Invent. Math. 79: 181 (1975).
 Ia. G. Sinai, Russ. Math. Surveys 27: 21 (1972).
 V. I. Oseledec, Trans. Moscow Math. Soc. 19: 197 (1968).
 G. D. Birkhoff, Proc. Nat. Acad. USA 17: 656 (1931).
 A. Rényi, Acta Mathematics (Hungary) 10: 93 (1959).
 J. L. Kaplan and J. A. Yorke, in Functional Differential Equations and Approximations of Fixed Points, Lecture Notes in Mathematics, vol. 730, edited by H. O. Peitgen and H. O. Walter (Springer-Verlag, Berlin, 1979).
 F. Ledrappier and L.-S. Young, Commun. Math. Phys. 117: 529 (1988).
 P. Grassberger and I. Procaccia, Phys. Rev. Lett. 50: 346 (1983); Physica 9D: 189 (1983).
 P. J. Myrberg, Ann. Acad. Sci. Fenn. Ser. A. L Math. 256: 1 (1958); ibid. 268: 1 (1959); ibid. 366: 1 (1963).
 M. J. Feigenbaum, J. Stat. Phys. 19: 25 (1978).
 Y. Pomeau and P. Manneville, Comm. Math. Phys. 74:189 (1980).
 C. Grebogi, E. Ott, and J. A. Yorke, Phys. Rev. Lett. 48: 1507 (1982).
 S. Oslund, D. Rand, J. Sethna, and E. D. Siggia, Physica 8D: 303 (1983); M. J. Feigenbaum, L. P. Kadanoff, and S. J. Shenker, Physica 5D: 370 (1982).
 D. Anosov, Proc. Steklov Inst. Math. 86: 61 (1968).
 A. Andronov and L. Pontryagin, Dokl. Akad. Nauk. SSSR 14: 247 (1937).
 S. Lefschetz, "Geometrical Differential Equations: Recent, Past and Proximate Future," in Proc. Symp. Diff. Eq. and Dyn. Syst, edited by J. Hale (Academic Press, New York, 1967).
 S. Smale, The Mathematics of Time: Essays on Dynamical Systems, Economic Processes, and Related Topics (Springer-Verlag, New York, 1980).
 E. N. Lorenz, J. Atmos. Sci. 20: 130 (1963).
 M. Hénon, Comm. Math. Phys. 50: 69 (1976).
 T. Y. Li and J. A. Yorke, Am. Math. Monthly 82: 985 (1975).
 R. M. May, Nature 261, 459 (1976).
 J. A. Glazier and A. Libchaber, IEEE Trans. Circuits and Systems 35: 790 (1989).
 P. Constantine, C. Foias, and R. Temam, Memoirs of AMS, vol. 53, no. 314 (1985).
 N. H. Packard, J. P. Crutchfield, J. D. Farmer, and R. S. Shaw, Phys. Rev. Lett. 45: 712 (1980).
 F. Takens, in Dynamical Systems and Turbulence, Lecture Notes in Mathematics, vol. 898, edited by D. Rand and L. S. Young (Springer-Verlag, Berlin, 1981).
 R. Bowen, J. Diff. Eq. 18: 333 (1975).
 S. M. Hammel, J. A. Yorke, and C. Grebogi, Bull. Amer. Soc. 19: 465 (1988); J. Complexity 3: 136 (1987).
 C. Grebogi, S. M. Hammel, J. A. Yorke, and T. Sauer, Phys. Rev. Lett. 65: 1527 (1990).
 R. S. Mackay and J. D. Meiss, eds., Hamiltonian Dynamical Systems (Adam Hilger, Bristol, 1987).
 J. Moser, "Stable and Random Motion in Dynamical Systems," Annals Math. Studies 77 (Princeton University Press, New Jersey, 1973).
 B. V. Chirikov, Phys. Rep. 52: 265 (1979).
 J. M. Greene, J. Math. Phys. 20: 1183 (1979).
 D. Bensimon and L. P. Kadanoff, Physica 13D: 82 (1984).
 R. S. Mackay, Renormalisation in Area-Preserving Maps, Ph.D. Thesis, Prince-ton University (1982).
 V. I. Arnold, Russ. Math. Surveys 18: 85 (1964).
 la. G. Sinai, Russ. Math. Surveys 25: 149 (1970).
 J. Hadamard, J. Math. Pures et Appl. 4: 271 (1898).
 M. Morse and G. A. Hedlund, Am. J. Math. 60: 815 (1938); ibid. 61: 1 (1939).