Unlike the previous two examples, internal diffusion-limited aggregation involves randomness. A rotor-router model was designed to be essentially a derandomized version of internal diffusion-limited aggregation, where each new particle follows a prescribed sequence of turns that is designed to distribute its motion equally in each direction. In 2005, it was shown that the shape of a crystal grown by the deterministic rotor-router model is the same as the shape of one grown by internal diffusion-limited aggregation: a circle (see Figure 15). This result may appear specialized, but the principle it illustrates is much more general: Sometimes the average behavior of a random system can be well captured by a deterministic system. In such cases the randomness may not actually be an essential feature of the process.

The theory of cellular automata remains a very lively area of research, awash in examples, with many unexplored territories and relatively few guiding or unifying principles to join them. Cellular automata have been used to study avalanches, forest fires, landslides, and earthquakes, among others. The traffic model in Figure 16 shows that a traffic jam must happen before the city streets are 100 percent occupied. Simulations suggest that the onset of traffic jams happens when the density is between 30 and 40 percent, and no one yet has been able to close the gap between the theory and the experiments to really understand the dynamics of traffic. And there seems to be an intermediate and remarkably structured regime between freely moving streets and gridlock that could be described as a moving traffic jam whose existence has not yet been confirmed.

Though much remains unknown about cellular automata, it is exactly at such wild and untamed frontiers that the mathematical sciences grow. The connections between cellular automata and more classical mathematics, such as those mentioned above, bode well for the future development of the subject. These connections are like wires bringing electricity to the frontier.

Though much remains unknown about cellular automata, it is exactly at such wild and untamed frontiers that the mathematical sciences grow.

16 / Biham-Levine-Middleton traffic model (right, reprinted with permission from Alexander Holroyd, Microsoft Research): In this idealized version of a grid of one-way streets, eastbound traffic (red) interacts with northbound traffic (blue). Jammed regions are solid, and flowing traffic forms dashed lines. /

image



The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001
Copyright © National Academy of Sciences. All rights reserved.
Terms of Use and Privacy Statement