=======================================================================
Cybernetics in the 3rd Millennium (C3M) -- Volume 1 Number 2, Oct. 2002
Alan B. Scrivener --- http://www.well.com/~abs --- mailto:abs@well.com
=======================================================================
"What Hath Wolfram Wrought?"
Part One of my review of Stephen Wolfram's magnum opus,
"A New Kind of Science."
( http://www.amazon.com/exec/obidos/ASIN/1579550088/hip-20 )
Well. Stephen Wolfram, mathematician-turned-entrepreneur,
creator of the great symbolic math software package Mathematica,
spent a decade preparing and almost another decade reclusively
researching and writing this book, which he has self-published
through his software company.
It's huge -- 846 pages of main exposition, followed by 351 pages
of notes, and an index; 1280 pages in all. Lugging it around while
reading it, I had people keep asking me about it. A few had heard of
it; most just commented on the size. Inevitably they'd ask, "What's
it about?" The best answer I was able to come up with, short version,
is: "This guy is interested in exploring the set of all possible
computer programs."
But while he's at it, he's providing a new all-encompassing
theoretical framework for information theory, especially the
theory of computability (Turing and Church 1936), Boolean logic
(George Boole 1847), Godel's Incompleteness Theorem (Kurt Godel,
1931), the idea of randomness, cybernetics and systems theory,
chaos theory, fractals, complexity studies, fundamental physics,
the nature of space, biology, especially genomics, perceptual
psychology, the limits of science and of mathematics, the nature
of proof, the limits of engineering, nanotechnology, and even the
possibilities of communication with extraterrestrials.
All of this is done with some very simple conceptual tools and a
computer. Mostly he works with CELLULAR AUTOMATA, the generalized
case of the old ever-popular Conway's "Life." The "Game of Life"
was first publicized by Martin Gardner in his "Mathematical
Recreations" column in Scientific American, 1970; see
"Wheels, Life, and Other Mathematical Amusements" by Martin
Gardner.
( http://www.amazon.com/exec/obidos/ASIN/0716715899/hip-20 )
Some other useful "Life" links:
Explanation and Java demos:
http://www.math.com/students/wonders/life/life.html
Comprehensive guide to "Life" on the web:
http://www.radicaleye.com/lifepage/
Archives of a paper newsletter on "Life" from the 1970s:
http://members.aol.com/life1ine/life/
By way of prior art, a less exhaustive and all-encompassing
analysis of the lessons of "Life" is found in William Poundstone's
"The Recursive Universe: Cosmic Complexity and the Limits of
Scientific Knowledge," 1986.
( http://www.amazon.com/exec/obidos/ASIN/0688039758/hip-20 )
So what has Wolfram done with cellular automata? First he reduced
their complexity and studied the simplest one-dimensional systems,
with only two possible states. Consider an infinitely long tape,
or perhaps an endless row of a checkerboard, and each square can have
one of two states: an X or a space, for example, or one of two colors
of checkers. Just for a standard of reference we start each cellular
automaton with a row having just one X (or black checker) and the
rest spaces (or red checkers), like this:
...+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...
| | | | | | | | | |X| | | | | | | | | |
...+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...
Over time, the system evolves according to very simple rules,
with each cell's new state based only on it's old state and
those of its two nearest neighbors. Here, for example, is one
such set of rules. Since "self and two neighbors" involves
three input states to the rule, there are 2^3 or 8 rules
needed to specify the new state for every possible configuration
of old states:
+-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
| | | | | | |X| | |X| | | |X|X| |X| | | |X| |X| |X|X| | |X|X|X|
+-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
| | | | | | | |
V V V V V V V V
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | | | | |X|
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
In this case, the new cell is blank unless the old cell and its
two neighbors are all three X. Starting with the standard single X,
the system evolves this way, with each row being a new time step:
...+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...
| | | | | | | | | |X| | | | | | | | | |
...+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...
| | | | | | | | | | | | | | | | | | | |
...+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...
| | | | | | | | | | | | | | | | | | | |
...+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...
In this case, the X evaporates, and all subsequent rows consist of
all blanks. Clearly this is a very simple behavior. One might
be tempted to conclude that all possible behaviors of such a simple
system would also be quite simple. But this is where Wolfram's
first surprise appears.
The choice of any rule set for this system involves eight binary
decision: whether to produce an X or space for each of the eight
possible inputs. Therefore there are 2^8 or 256 possible rule sets
for this system. Wolfram analyzes all 256 early on; here is a visual
representation of half the results, 128 through 256 (this is a sample
page at his web site for the book):
http://www.wolframscience.com/preview/nks_pages/?NKS0056.gif
He finds that the behavior of these systems fall into four
general categories, and proceeds to produce a taxonomy for them.
He goes on to explore systems with more complex sets of rules,
with more dimensions, more states, more inputs besides nearest
neighbors, allowing fore continuous (non-quantized) sates,
continuous space, and continuous time. He keeps finding only
the four basic types of behaviors, and concludes that they he might
as well study the simplest rule systems, since they are complex
enough.
If you would like to study these systems, here are three resources:
http://www.wolframscience.com/
Has programs used to create the book; requires Mathematica.
http://ccl.northwestern.edu/netlogo/models/CA1DRule30
Requires NetLogo package (free download).
http://www.javaosx.com/apps/nkos.jsp
Java app requires Mac OS X.
Why is this a new kind of science? Well, up until now the scientific
method has been to create a mathematical model of a phenomenon and then
test it with experiment. If the results don't fit, tweak the model.
You end up doing only the math that results in models that resemble
the phenomenon you are studying. A friend of mine has called this
"crisis management" in science. By contrast, Wolfram is seriously
interested in exploring the set of all possible theories. If we can
end up with a bigger array of known effects and the models which
produce them, it will make our efforts at specific model-making
more efficient. And we might learn some amazing things along the
way. Wolfram shows that Rule 30 in his set of 256 is a better random
number generator that those now in widespread use, and also that Rule
110 is "Turing-complete," and so can be used to emulate any other
rule system of any number of states and dimensions. Usually we
say something is complex if it seems random, or capable of a wide
range of behavior, and Wolfram finds both types of complexity in
these simple little critters.
Of course, the big question is: is he really on to something?
I will address that question in a future newsletter. (Short answer:
yes.)
TO BE CONTINUED...
======================================================================
newsletter archives:
www.well.com/~abs/Cyb/4.669211660910299067185320382047/c3m_0101.txt
www.well.com/~abs/Cyb/4.669211660910299067185320382047/c3m_0102.txt
======================================================================
Privacy Promise: Your email address will never be sold or given to
others. You will receive only the e-Zine C3M unless you opt-in to
receive occasional commercial offers directly from me, Alan Scrivener,
by sending email to abs@well.com with the subject line "opt in" -- you
can always opt out again with the subject line "opt out" -- by default
you are opted out. To cancel the e-Zine entirely send the subject
line "unsubscribe" to me. I receive a commission on everything you
purchase during your session with Amazon.com after following one of my
links, which helps to support my research.
======================================================================
Copyright 2002 by Alan B. Scrivener