======================================================================= Cybernetics in the 3rd Millennium (C3M) -- Volume 1 Number 2, Oct. 2002 Alan B. Scrivener --- 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." ( 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. ( www.amazon.com/exec/obidos/ASIN/0716715899/hip-20 ) Some other useful "Life" links: Explanation and Java demos: www.math.com/students/wonders/life/life.html Comprehensive guide to "Life" on the web: www.radicaleye.com/lifepage/ Archives of a paper newsletter on "Life" from the 1970s: 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. ( 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): 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: www.wolframscience.com/ Has programs used to create the book; requires Mathematica. ccl.northwestern.edu/netlogo/models/CA1DRule30 Requires NetLogo package (free download). 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