Entropy and cellular automata

Here’s a few frames of a simple simulation of The Game of Life I wrote in MATLAB:

To me, it’s pretty unintuitive that biological processes, like DNA translation or bird flock motion, work so well given that they are often very far from “equilibrium” in the sense we learn in chemistry class. I was taught in high school to think of “equilibrium” as the most stable, least interesting, but most likely outcome of a chemical reaction—vinegar and baking soda eventually fizzle out into brown goo, and even nuclear fusion in stars eventually stops as clumps of iron form in the stellar core.

I think the supposed intuition for the idea of unavoidable equilibration comes from the second law of thermodynamics: entropy constantly increases in the universe, and so there is no spontaneous physical process that can occur on a large enough scale to reverse this tendency. The universe is like a deck of cards: it is always easier to shuffle it than to arrange it in a particular order; thus large scale processes tend to favor disordered outcomes rather than neat patterns. This idea appears throughout the sciences in various forms: one of the axioms of cosmology is that the universe at large scales is homogenous and isotropic—it has no definite structure or patterns, but rather looks like a well-mixed soup of randomly arranged galaxies and gas clouds.

Biological systems can locally violate this rule–they exist as well-ordered clockworks within a universe otherwise characterized by collision and diffusion. While the second law still holds on the large scale, the law of averages allows some leeway on the cosmically insignificant scale of the earth—for every sequoia tree or giant squid there is a much larger disordered element, such as a cloud of gas or a stellar explosion, to compensate. But it still seems surprising that systems as orderly as living beings, with their underlying ability to replicate and evolve repeatedly over millenia, can spontaneously have emerged from the noisy background to cosmos. This raises the question of whether there is some fundamental physical property that makes “living” things unique.

In 1970, the mathematician John Conway proposed “The Game of Life,” a simple mathematical model that sheds light on how “designed” systems can emerge from chaos. In Conway’s version of the game, a black grid is drawn on which some random pattern of squares or tiles is filled in with white. If these white tiles are taken to be some sort of initial colony of “living” cells against an otherwise dead (black) backdrop, then simple rules can be defined for updating the grid to represent colony growth:

1. If a black tile has two or three white tiles adjacent or immediately diagonal to it, then in the next generation it will become white (as if by reproduction).

2. If a white tile has more than three white tiles surrounding it (up to 8 total), then it will become black in the next generation as if by overcrowding; if a white tile has less than 2 white neighbors nearby, it will die in the next generation due to starvation.

3. Any white cell with exactly 2 or 3 white neighbors will persist to the next generation.

These simple rules create an extremely efficient simulation that can be run over many time steps to create life-like simulations of colony growth. What makes Conway’s game uncanny is that even the most random initial patterns can create dynamic, predictable colonies– the second law of thermodynamics does not mean that all, or even most, versions of the game will create a chaotic mass of cells. For example, here’s a pattern that one set of initial conditions will create when the game is run for many time steps (click the image to see the animation):

Click to see the gif on Wikimedia.

The animation shows several important structures that can emerge within the game: gliders are groups of cells that continuously move across the playing field, returning to their original shape (but in a different location) within a few generations. Some cells cluster together and form stable, immobile structures that persist indefinitely until they interact with a wayward glider or another structure.

Conway’s game provides a simple illustration of how life-like systems can emerge from random initial conditions, implying a decrease in entropy in the limited “universe” of the simulation. The game and its variants with different rules, tiling patterns, etc are collectively known as cellular automata, which form the basis of a lot of important research currently occurring in image processing and computational biology. Several noted scientists, including Turing, von Neumann, and Wolfram have investigated the implications of these simple models—Wolfram in particular has devoted several decades or research, thousands of textbook pages, and a particularly unusual Reddit AMA, to the theory that cellular automata provide the basis of the most fundamental physical laws of the universe.

But the Game of Life also connects to many more general mathematical concepts. Markov models, which mathematically characterize systems in which individuals undergo transitions, arrivals, or departures from several finite, well-defined states are an alternative way of representing the same information as Conway’s tiles. The defining principle of Markov models is that the next state is determined purely by the present state: a population ecologist who uses Markov models would assume that the next change in population size can be predicted purely by information about the present population (for example during exponential growth, in which the growth rate of a group of organisms correlates to the size of the group). An ecologist would keep track of all the possible state changes in the population using a transition matrix, which contains empirical estimates of the rate at which new individuals are born (arrival event), old individuals die (departure), and existing individuals survive (transition). The parallel with Conway’s three rules is clear, but Markov models can be easily represented with matrices, and so they represent a natural limiting case for any system in which a physical entity evolves based on a limited subset of its past states.

If Conway’s tiled grid is replaced with a continuous set of points, and the survival status of a given point depends on a weighted integral of the “brightness” of points within a given radius of it, then the transition matrices for many continuous cellular automata will become the solution of a differential equation in space and time. Certain types of diffusion equations, for example, use integration over neighboring points as a continuous approximations of the rules of the Game of Life. A set of differential equations that illustrate the well-defined structures that can emerge from an otherwise disordered system are the reaction-diffusion equations, which model the strange patterns that can be observed when a homogenous solution of potassium bromate and cerium sulfate is mixed with several acids:

Taken from Wikipedia

.

Thus diffusive differential equations, Markov models, and cellular automata really all describe essentially the same process, in which local interactions cause ordered structures and patterns to emerge and aggregate within an otherwise random system.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s