Monday, December 26, 2011

9: The World As A Computer

   I don't know about you, but sometimes I can find the huge number
of equations, relationships, and rules in modern physics and chemistry
to be somewhat daunting.  Wouldn't it be nice if the world just had a
few simple rules, and they explained how everything works?  Some
researchers have attempted to put together systems like this, by
explaining the world in terms of mathematical constructs known as
cellular automata.

    The basic idea behind cellular automata is that rather than a big,
complex system with lots of functions and equations, you have a gigantic
array of small, simple computing elements with really basic rules.  One
example is John Conway's famous "game of life", not to be confused
with the children's board game of the same name.  Think of this as a
giant sheet of graph paper, where every square can be either 'alive' or
'dead'.  Each turn, or "generation", every square independently
determines what its status will be for the next turn, based on the
number of its neighbors that are alive.  A live square stays alive if
it has exactly two or three live neighbors, otherwise it dies of
either loneliness or overcrowding.  And a dead square comes to life if
it has exactly three live neighbors.   That's it-- just those few
simple rules.   It's only a "game" in that you can choose the starting
pattern of live squares-- after that, it's all automatic.

    According to these rules, the pattern of live and dead squares
changes every turn.  Usually this game is "played" in a computer
simulation--  a giant grid appears on the screen, with dead squares
empty and live squares filled in in black.

    Why is this "game" interesting?  Well, the set of patterns that
can arise, with the proper starting set of live and dead squares, is
amazingly rich.  It's pretty easy to create patterns like "gliders",
sets of live squares that seem to move across the board, and
"blinkers", small patterns that constantly switch between a few
shapes.  But it gets a lot more complex than that-- there are many
examples where you might start with just a dozen or so live squares,
and when you run the game, you will see thousands of cycles of
unpredictable, lifelike activity. 

    It has also been shown that the Game of Life is Turing-complete.
This is a mathematical property which means, among other things, that
with the proper configuration of starting live and dead squares, the
"Game of Life" can emulate any modern digital computer!   So any form
of artificial intelligence or computer simulation of a physical system
can, in principle, be replicated on a Game of Life grid, with the
proper set of starting cells turned on.

    This has led some researchers to think that *everything* in
existence is, essentially, a cellular automaton.  The idea is kind of
appealing-- after all, if matter is made of tiny particles, shouldn't
they follow a set of simple rules if viewed locally?  Some initial
support for this is the fact that in some cases, cellular automata
have been shown to be able to emulate basic patterns found in fluid
dynamics and biology. 

    Have people managed to take this idea further?  Probably the most
famous researcher in cellular automata is Stephen Wolfram, a true
scientific genius best known for creating the "Mathematica" software
package.  In 2002 he published a book with the audacious title "A New
Kind of Science."  The academic community largely yawned.   While it
had lots of interesting examples of cellular automata with nice-looking
patterns, the book did not really fulfill the title's promise to
redefine science. Its basic claim was that studying the behavior of
simple computational systems like cellular automata was so important
and useful that it should be considered another branch of science for
its own sake, and would lead to many real-world breakthroughs in
physics, chemistry, and biology.  We're still waiting.  

    So, what does all this mean?  Cellular automata are pretty fun to
play with, and it is amazing how a few simple rules can result in such
rich, complex patterns.  In the show notes I have a pointer to a Java
'Game of Life' simulator at ibiblio.org, which I would encourage you
to try out.  Currently, it doesn't look like simple cellular automata
really explain a whole lot about the real world.  But hey, who needs
the real world, when you have mathematics to play with instead?

    This has been your math mutation for today.

  • Cellular Automata on Wikipedia
  • Conway's Game of Life on Wikipedia
  • Wolfram's New Kind of Science on Wikipedia
  • Life simulator on ibiblio.org
  • No comments:

    Post a Comment