Keeping Up With the MerklesCellular automata can help you model complex systemsby Joe Celko Over the years, I've had chances to meet smart people that I didn't take. Now, I have another name to add to that list: Stephen Wolfram. He created the Mathematica programming language and software company. Although being a multimillionaire is nice, that isn't what makes him smart. He just wrote a book entitled A New Kind of Science (Wolfram Media Inc., 2002) in which he argues that you can model complex systems with cellular automata. The idea of cellular automata is that you have a grid, and each cell of the grid has a simple automaton. I've always liked to call them "Merkles" and imagine that they're really small cartoon animals. Every Merkle has a state and the ability to detect the state of its neighbors. The Merkle's state changes according to some rules that are strictly local to that Merkle, so the system doesn't have any overall "central planning." The Merkles usually have a common clock, so that the changes all come at once. A Merkle NeighborhoodWhat makes cellular automata really interesting is that some of them exhibit behavior at an aggregate level that you wouldn't expect from their simple rules. Although not exactly a "geek magazine," The Atlantic Monthly has an interesting example of this behavior in a series of online articles by Jonathan Rauch that appeared in April 2002. He details the work of Thomas C. Schelling, an 80-year-old economist at the University of Maryland, who created a very simple "artificial neighborhood" in the early 1960s. Schelling observed that most American neighborhoods were racially segregated. Finding one in which neither African-Americans nor Caucasians occupied more than 75 percent of the households was difficult. His observation was that "the distribution is so U-shaped that it is virtually a choice of two extremes." But rather than dismiss this phenomenon as simple racism, Schelling had an intuition that segregation would occur anyway. He built a pencil-and-paper cellular automata model on an airplane flight from Chicago to Boston. Each color of Merkles — red and blue — wanted at least n of its neighbors to be of its color (you can view simulations online at www.theatlantic.com/issues/2002/04/rauch.htm). Start with a grid filled with a random distribution of reds and blues, set the rules, and let things run. The randomness goes away and the blues and reds segregate. Obviously, you have many unhappy Merkles at the start of the simulation. The rule is that two Merkle households can swap if the switch will make them both happier. The system gets stable fairly soon with small changes at the borders of the districts. It doesn't matter what the individual community preferences were; Schelling concluded they all led to the segregation of blues and reds. Merkle PotentialThese patterns may be useful for making predictions about large group behavior, the growth of cities, crime rates, and the spread of disease. Scientific American ran a short piece about a study that suggests tracking the sales of over-the-counter medications might be more effective than traditional statistical methods to find outbreaks of diseases such as anthrax earlier. The traditional way is to look at hospitals and medical reports, which means that the disease has become more serious ("Grocery Data Could Warn of Anthrax Outbreaks," April 16, 2002; www.scientificamerican.com). This early warning approach would mean tapping into retail databases and looking for changes in neighbors' purchase patterns. I'm not quite sure how well people will take to turning over their cash register receipts and finding a message that says "Hi! Maybe you ought to stop by the pharmacy and buy some Cipro today," but it would be more useful than the coupons that I keep getting for discounts on haircuts. Maybe Wolfram is onto something here... Joe Celko [71062.1056@compuserve.com] is an independent consultant in Austin, Texas and the author of Joe Celko's SQL for Smarties: Advanced SQL Programming (Morgan Kaufmann Publishers, 1999).
|
 |
Most Popular This Week
IE Weekly Newsletter
Subscribe to the newsletter
| |
|
|