National Academies Press: OpenBook

Fueling Innovation and Discovery: The Mathematical Sciences in the 21st Century (2012)

Chapter: Cellular Automata / Sublimely Complex

« Previous: Fast Multipole Method / A Long-Term Payoff
Suggested Citation:"Cellular Automata / Sublimely Complex." National Research Council. 2012. Fueling Innovation and Discovery: The Mathematical Sciences in the 21st Century. Washington, DC: The National Academies Press. doi: 10.17226/13373.
×

Cellular Automata

Sublimely Complex

A sandpile grows in an hourglass, one grain at a time. Occasionally the impact of one sand grain will create a minicascade of grains. Even less often, a minicascade will trigger a macrocascade that changes the shape of the whole sand pile. How often do these cascades occur, and do they follow a predictable pattern?

A snowflake grows by attaching one molecule of water at a time. How does that process lead to the lacy, frilly shapes that we see in real snowflakes? What do we get if we grow the snowflake in different ways, using different attachment rules?

A city has two directions of traffic, east and north. At each intersection a car can proceed only if there is no other car already in the intersection. How many cars do you need to have in the city before gridlock ensues? Can the traffic self-organize into moving patterns?

These are three examples of a stylized mathematical model called a cellular automaton. Often inspired by real physical objects (such as sandpiles, snowflakes, and traffic), cellular automata demonstrate that amazingly complicated large-scale effects can arise from very simple local rules. They have been applied to other phenomena as diverse as avalanches and wildfires.

There is a widespread belief that highly complex systems can only be understood through computer simulation. However, mathematicians have found that simulation is far from the only way to discern patterns and phenomenology.

“Packard snowflakes,” invented by Norman Packard in 1984, begin with a hexagonal lattice, like a honeycomb, in which one cell is filled by an ice crystal. One particularly interesting snowflake grows by the following rule: If an open cell is adjacent to 1, 4, 5, or 6 cells that are already filled, then at the next time step that cell fills and freezes. However, nodes that are adjacent to 0, 2, or 3 “frozen” nodes remain unfrozen at the next step.

Suggested Citation:"Cellular Automata / Sublimely Complex." National Research Council. 2012. Fueling Innovation and Discovery: The Mathematical Sciences in the 21st Century. Washington, DC: The National Academies Press. doi: 10.17226/13373.
×

After many steps, a shape emerges that bears a striking resemblance to a real snowflake (Figure 13). What if we let the Packard snowflake grow for as long as we want? Will all of the gaps in the snowflake eventually be filled?

In computer simulations, every gap seemed to fill eventually. But in 2006, it was shown that unfillable gaps do exist. The closest unfillable gap to the center is at least a billion cells away! Because a billion billion cells have to be filled before you can even get to this gap, it’s no wonder that simulations never saw it. However, a billion billion is not an unrealistic number. It is less than the number of molecules in a milligram of ice. This example demonstrates the value of mathematical analysis and mathematical proof, which can provide insights that may be otherwise unavailable.

The cellular version of a sandpile starts with a rectangular grid and a distribution of sand grains on the grid that may be highly unstable. For instance, a thousand or a million grains could be stacked up into a tower (something quite unachievable with real sand). Like the Packard snowflake, the sandpile evolves by discrete steps. At each step in this simulation, a rule requires that any cell that is occupied by a stack of four or more grains of sand will redistribute one grain to each of its four neighbors. Of course, this may cause one of the neighbors to have four or more grains, so that the cell topples at the next time step. A cascade of toppling grains is thereby produced that can continue

image

13 / A “snowfake” grows on a hexagonal grid by using simple attachment rules that model the adhesion of water molecules to a growing ice crystal. The resulting model (left, reprinted with permission from Janko Gravner, UC Davis, and David Griffeath, University of Wisconsin) looks remarkably similar to a real snowflake (right, reprinted with permission from Ken Libbrecht, California Institute of Technology.). The final macroscopic shape depends in very subtle ways on the local attachment rules on the molecular scale. /

Suggested Citation:"Cellular Automata / Sublimely Complex." National Research Council. 2012. Fueling Innovation and Discovery: The Mathematical Sciences in the 21st Century. Washington, DC: The National Academies Press. doi: 10.17226/13373.
×

image

14 / In a cellular automaton model of a sandpile, a billion grains of sand form complex patterns whose existence and shape can be confirmed from the mathematical theory of free-boundary problems. Colors denote the number of grains of sand in each cell (0, 1, 2, or 3). Reprinted with permission from David B. Wilson, Microsoft Research. /

image

15 / The rotor-router model is a deterministic version of a random process called internal diffusion-limited aggregation. The boundary has been proven to be circular; the “puckers” are still unexplained. Reprinted with permission from Tobias Friedrich (Max Planck Institute) and Lionel Levine (Cornell University). /

for a very long time but ultimately settles down into a final configuration that looks like Figure 14. Note that in this figure, every cell contains 0, 1, 2, or 3 grains of sand and the cells are color-coded accordingly.

What is the shape of this final configuration? Does it depend on the number of grains of sand? What about the mysterious pattern of triangles that is so apparent in Figure 14?

In 2011, it was proved that at a large scale, the final shape is independent of the size. Thus a sandpile with a billion grains looks about the same as a sandpile with a million grains (only larger). Likewise, the pattern of colors stabilizes, so that every sufficiently large sandpile will look the same as the others (only larger or smaller).

The proof involves a mathematical model known as a free-boundary problem. Such problems arise, for example, in the study of combustion, glaciers, and stalactites, when a scientist is solving for not just an unknown function (say, the temperature in a moving flame) but also an unknown domain on which the function is defined. The theory of this particular free-boundary problem is less than 20 years old. Thus the sandpile problem, which might at first seem like an amusing game, is in fact intimately tied both to physics and to new developments in the mathematical sciences.

Another beautiful and conceptually important cellular automaton is called the “rotor-router.” One version was designed to mimic internal diffusion-limited aggregation, which is more or less the flip side of snowflake growth. Imagine a crystal that instead of growing by attachment of particles from outside, grows by attachment of new particles from within. Each new particle wanders around the inside of the crystal at random until it hits a cell that has not been occupied yet and stops there.

Suggested Citation:"Cellular Automata / Sublimely Complex." National Research Council. 2012. Fueling Innovation and Discovery: The Mathematical Sciences in the 21st Century. Washington, DC: The National Academies Press. doi: 10.17226/13373.
×

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

Suggested Citation:"Cellular Automata / Sublimely Complex." National Research Council. 2012. Fueling Innovation and Discovery: The Mathematical Sciences in the 21st Century. Washington, DC: The National Academies Press. doi: 10.17226/13373.
×
Page 36
Suggested Citation:"Cellular Automata / Sublimely Complex." National Research Council. 2012. Fueling Innovation and Discovery: The Mathematical Sciences in the 21st Century. Washington, DC: The National Academies Press. doi: 10.17226/13373.
×
Page 37
Suggested Citation:"Cellular Automata / Sublimely Complex." National Research Council. 2012. Fueling Innovation and Discovery: The Mathematical Sciences in the 21st Century. Washington, DC: The National Academies Press. doi: 10.17226/13373.
×
Page 38
Suggested Citation:"Cellular Automata / Sublimely Complex." National Research Council. 2012. Fueling Innovation and Discovery: The Mathematical Sciences in the 21st Century. Washington, DC: The National Academies Press. doi: 10.17226/13373.
×
Page 39
Next: Graph Spectra / Sparsest Cuts in Minimum Time »
Fueling Innovation and Discovery: The Mathematical Sciences in the 21st Century Get This Book
×
Buy Paperback | $20.00 Buy Ebook | $16.99
MyNAP members save 10% online.
Login or Register to save!
Download Free PDF

The mathematical sciences are part of everyday life. Modern communication, transportation, science, engineering, technology, medicine, manufacturing, security, and finance all depend on the mathematical sciences. Fueling Innovation and Discovery describes recent advances in the mathematical sciences and advances enabled by mathematical sciences research. It is geared toward general readers who would like to know more about ongoing advances in the mathematical sciences and how these advances are changing our understanding of the world, creating new technologies, and transforming industries.

Although the mathematical sciences are pervasive, they are often invoked without an explicit awareness of their presence. Prepared as part of the study on the Mathematical Sciences in 2025, a broad assessment of the current state of the mathematical sciences in the United States, Fueling Innovation and Discovery presents mathematical sciences advances in an engaging way. The report describes the contributions that mathematical sciences research has made to advance our understanding of the universe and the human genome. It also explores how the mathematical sciences are contributing to healthcare and national security, and the importance of mathematical knowledge and training to a range of industries, such as information technology and entertainment.

Fueling Innovation and Discovery will be of use to policy makers, researchers, business leaders, students, and others interested in learning more about the deep connections between the mathematical sciences and every other aspect of the modern world. To function well in a technologically advanced society, every educated person should be familiar with multiple aspects of the mathematical sciences.

  1. ×

    Welcome to OpenBook!

    You're looking at OpenBook, NAP.edu's online reading room since 1999. Based on feedback from you, our users, we've made some improvements that make it easier than ever to read thousands of publications on our website.

    Do you want to take a quick tour of the OpenBook's features?

    No Thanks Take a Tour »
  2. ×

    Show this book's table of contents, where you can jump to any chapter by name.

    « Back Next »
  3. ×

    ...or use these buttons to go back to the previous chapter or skip to the next one.

    « Back Next »
  4. ×

    Jump up to the previous page or down to the next one. Also, you can type in a page number and press Enter to go directly to that page in the book.

    « Back Next »
  5. ×

    Switch between the Original Pages, where you can read the report as it appeared in print, and Text Pages for the web version, where you can highlight and search the text.

    « Back Next »
  6. ×

    To search the entire text of this book, type in your search term here and press Enter.

    « Back Next »
  7. ×

    Share a link to this book page on your preferred social network or via email.

    « Back Next »
  8. ×

    View our suggested citation for this chapter.

    « Back Next »
  9. ×

    Ready to take your reading offline? Click here to buy this book in print or download it as a free PDF, if available.

    « Back Next »
Stay Connected!