Mindless Creatures.html

This is a copy of the original page. However, if you have subscribed to the electronic New York Times, or wish to register, the URL of this page is: http://www.nytimes.com/library/national/science/032399sci-cellular-automata.html

March 23, 1999

Mindless Creatures Acting 'Mindfully'

--------------------------------------------------------
Related Articles
* Computer 'Life Form' Mutates in an Evolution Experiment
(Nov. 25, 1997)
* Lively Computer Creation Blurs Definition of Life (Aug.
27, 1991)

Forum
* Join a Discussion on Artifical Life
--------------------------------------------------------

By GEORGE JOHNSON

blivious to its fellows, the single-celled creature
called the cellular slime mold slithers amoeba-like
along the ground, lapping up the nutrients in its path.
But when the food supply runs out, it has a biochemical
panic attack, frantically sending out molecular signals
to other nearby slime molds, which in turn are sending
out signals of their own. Guided by these primitive
conversations, the individual cells come together to
form a multicelled organism, sprouting a stalk and a
head of spores that become the seeds of the next
generation. When these fall to the ground, the cycle
begins anew.

Exotic as it seems, this behavior
is just a stark example of one of
the most familiar phenomena in the
living world: the way individuals,
whether cells in a body, plants
and animals in an ecosystem, or
members of a corporation or
society, congregate into complex
wholes that take on autonomous existences of their own.
There is no need for a central controller orchestrating
their movement.

Each member, simply by
exchanging information
with its nearest
neighbors, unwittingly
contributes to the
commonweal. From simple,
shortsighted, generally
selfish actions, a
transcendent global
behavior emerges.

Hoping to understand on
a very basic level how
such patterns of
cooperation arise,
scientists based at the
Santa Fe Institute in
New Mexico have stripped
the problem to its
bones: studying how the
simplest imaginable
cells -- appearing as
squares on a computer
screen -- can interact
to generate surprisingly
complex, coordinated
behavior.

"There are these
incredible pictures in
which ants are all
trying to get from one
tree to another tree,"
said Dr. Melanie
Mitchell, a member of
the project along with
her Santa Fe colleague,
Dr. James Crutchfield,
and Dr. Rajarshi Das,
who recently moved to
the I.B.M. Thomas J.
Watson Research Center
in Hawthorne, N.Y. "They
build a bridge with
their bodies and other
ants can climb across.
It's quite amazing. Our
motivation is to
understand phenomena
like that: how information processing and communication
takes places in these distributed systems with no
central control."

Viewed even more broadly, the goal is a deeper
understanding of how pattern emerges in nature and the
universe. "If I look out at the world, I see a lot of
structure and regularity there," said Dr. Crutchfield.
"Where does that order come from?"

The tool for this research is a computer program called
a cellular automaton. An automaton is a device, made of
mechanical or electronic components, or in this case
computer software, that operates autonomously, almost as
though it were alive.

The classic example of this artificial life was invented
in 1970 by the British mathematician John Horton Conway.
In the Game of Life, a grid of cells, like a luminous
piece of graph paper, is projected onto the screen of a
computer monitor. Some of the squares are randomly
colored black. These are called "live" cells; blank ones
are "dead." At every tick of the clock, each cell in the
grid examines only cells adjacent to it (including the
four diagonals). Then it refers to a list of simple
rules and responds accordingly: A live cell with one or
no neighbors dies from isolation, a live cell with four
or more neighbors dies of overpopulation, a live cell
with two or three neighbors survives. Finally, a dead
cell with three neighbors comes to life.

Tick by tick a dazzling array of lifelike patterns
unfolds, merging, dissolving, oscillating. Like the
cells of a slime mold or the ants in an anthill, the
cells of the cellular automaton trade information only
with their immediate neighbors, but they link up into
complex structures that sprawl across the screen. (There
are several places on the Web to play Life, including
www.bitstorm.org/gameoflife).

While the Game of Life is played on a two-dimensional
array, like a checkerboard, the Santa Fe Institute
scientists have made their cellular automata (called
C.A.'s for short) even simpler, each consisting of only
a single row of black and white cells. At each tick of
the clock, each cell refers to its three closest
neighbors on the left and right. Then according to a
table of rules, it turns on or off. The next generation
of cells then appears in the row underneath. Generation
after generation unscrolls from the top of the screen to
the bottom like a roll in a player piano.

Depending on the rules and the initial configuration,
different kinds of patterns unfold. Some C.A.'s quickly
freeze up into boring routine, churning out all black or
all white forever. Others cycle through the same pattern
over and over. And still others generate a seemingly
endless variety of intricate structures that seem to
hover on the brink between complexity and randomness.

In their own research, the Santa Fe scientists set out
to make a C.A. that, regardless of the initial
configuration, would always settle into a repeating
pattern with a black row alternating with a white row,
blinking on and off eternally. Starting with any
randomly chosen pattern of black and white cells, the
system would converge after several hundred ticks of the
clock, into this precise lockstep pattern, reminiscent
of the way, perhaps, the cells in a heart coordinate
their random firings into a steady rhythmic beat.

One way to accomplish this task would be for a godlike
human programmer, like the inventor of the Game of Life,
to design a clever set of rules, imposing them from the
top down.

Dr. Crutchfield, Dr. Mitchell and Dr. Das set a more
ambitious goal: to see if they could get the rules for a
blinking automaton to evolve, from the bottom up, more
as they would in nature. Through evolution, the cells in
a heart develop the ability to beat together
cooperatively; the ants in the anthill to build a
bridge. In a computer-simulated Darwinian struggle, the
cells in the cellular automaton would evolve the ability
to form synchronized blinking patterns.

By studying the crisp lines of the simple simulated
system, the researchers of the EvCA project (short for
"evolving cellular automata") hope to throw light on how
individuals in nature develop this ability to exchange
information and coordinate their behavior, carrying out
tasks in ways that never would have occurred to an
engineer.

"The research shows how sneaky nature can be in the ways
it finds to solve problems," said Dr. Andy Clark, a
philosopher at Washington University in St. Louis. The
solutions that emerge, he noted, are "quite different
from our armchair design -- often messier-looking on the
surface, yet deeply efficient underneath."

Like animal breeders, the
experimenters started with
100 untrained C.A.'s, each
governed by a set of randomly
generated rules. Each C.A.
was then seeded with a random
configuration of black and
white squares and left to
churn away. After each had
been tested on 100 of these
initial patterns, the fittest
C.A.'s -- those that came
closest, after 300 clock
ticks, to settling into the
blinking cycle -- were then
pulled from the pool, the
others allowed to die.

The survivors then were
allowed to "have sex" with
one another. Their rules,
expressed as a string of 1's
and 0's, can be thought of as
the genetic message -- the
chromosome that determines
how the C.A. behaves. By
exchanging chunks of this
code, like amoebas fusing and
swapping DNA, the winners of
the old generation gave birth
to a new one. In a further
imitation of natural
variation, the chromosomes
were also subject to random
mutation, a 1 might become a
0 or vice versa, like a
molecule zapped by a cosmic
ray.

Then, using this second
generation, the experiment
was run again. The fittest
survivors were culled out and bred and the third
generation was put to the test.

"We'd just leave the algorithm cooking on our
workstations over night," Dr. Crutchfield said. "Then
we'd come back in the morning and see what they were
doing."

After 100 generations, C.A.'s almost always emerged that
knew the blinking task.

At this point the human overseers had no idea why the
solutions that evolution had stumbled upon worked so
well. "Unraveling this problem," Dr. Das said, "was the
most fascinating aspect of this work."

For example, if a cell saw that the three cells to the
left of it were black, then it might decide to turn
black at the next tick. But what if the cells to the
right of it were all white? And it would have no way of
knowing what distant cells far down the row were doing.
What if, imitating its neighbors, a cell turned black
only to find that they, using different criteria,
decided to turn white? There was no higher intelligence
looking down and seeing the whole picture, coordinating
the flow.

In another experiment, the scientists bred C.A.'s to
perform what is called the density classification
problem. Starting with a random row of cells, the C.A.

would compute the relative number of black and white
cells. If most of the cells in the initial row were
white, then the C.A. would ideally converge to a state
where it churned out nothing but white rows. And if
there were more black than white cells, it would
eventually churn out all black rows.

Again, the problem was understanding how the fittest
survivors were performing this computation. The answer
was hidden somewhere in the long row of 1's and 0's
representing the rule table -- the digital chromosome
that had evolved. But analyzing a C.A. on that level
would be like trying to understand an animal's
psychology by scrutinizing the precise details of its
DNA sequence. Or, the scientists wrote, it would be like
trying to explain how a pocket calculator computes
square roots by examining the flow of the charges though
its silicon circuits.

To figure out why a C.A. worked the way it did, the
scientists needed to step back and take a bird's eye
view. As they studied the grids of cells churned out by
the program, they noticed that they were typically
grouped into large rectangular and triangular regions.
Some were solid black, some solid white and some
checkerboard.

The breakthrough came when they concentrated not on the
regions themselves but on the boundary lines between
them. Viewed at a higher level of abstraction, these
began to resemble tracks of colliding particles like one
sees in photographs from physics experiments.

"This is something we didn't anticipate," Dr.
Crutchfield said. "In a sense we were being artificial
particle physicists."

It was a surprising change of metaphor. Drawing on
earlier work Dr. Crutchfield had done at the University
of California at Berkeley with Dr. James Hanson, now
with the I.B.M. Watson Research Center, the scientists
classified these "artificial particles" according to
various characteristics like the nature of the regions
they separated and how fast they propagated across the
screen. The result was a mathematical language that
explained a C.A.'s behavior in terms of particles
colliding and trading information.

This new depth of understanding is the most exciting
thing about the work, said Dr. Mitchell Resnick, a
computer scientist at the Media Lab at the Massachusetts
Institute of Technology. Much research on cellular
automata and artificial evolution "borders on magic," he
said. Researchers breed programs by trial and error and,
voilà, something interesting emerges. But they are left
baffled by how their creations compute.

"The Santa Fe team has helped bring rigor and insight to
this field," he said. "They identify a set of patterns
that help explain how and why the evolutionary algorithm
works. Their approach is the classic scientific
approach: develop new representations that enable you to
see a clear picture where others had seen only noise."

Changing metaphors again, the researchers are pondering
whether the patterns that emerge in their simulation
bear something in common with those that emerge inside
the brain. Neurons exchanging electrochemical signals
with their immediate neighbors somehow give rise to
grand thoughts and mental images representing things in
the outside world.

"The brain does not have a single center to evaluate or
coordinate computations," Dr. Das said.

"Yet it is able to bind together many parallel
computations to produce coherent perception and action.
I think our approach can bring a fresh perspective to
study this problem."

Like cells in the Game of Science, the researchers
gather and trade information on the Internet, the
telephone and in face-to-face conversations, never
entirely sure of the greater pattern that might unfold.
--------------------------------------------------------
Related Sites
These sites are not part of The New York Times on the
Web, and The Times has no control over their content or
availability.

* The Game of Life.

* The EvCA Project.

* Primordial Soup Kitchen.

-----------------------------------------------------------

Help/Feedback | Classifieds | Services | New York Today