Home • Essays • Lost Articles • Loose Ends • Collections • Computing • Projects • Widdershins • Quotations • Links • Us


A New Kind of Spreadsheet

Cellular Automata Invade Our Favorite Business Tool...

When it hit the bookstore shelves not too long ago, I was at the head of the line to buy Stephen Wolfram’s self-published book, "A New Kind of Science" (Wolfram Media, 2002) – possibly, you were there too. Myself, I hardly winced at the $69.95 sticker, since that is a small price to pay for a chance to enter the mind of a bona fide genius. A MacArthur award winner, originally educated in theoretical physics at Eton, Oxford and Caltech, Wolfram created the widely used software system Mathematicatm. He has used the profits from his software company to fund his lifelong pursuit of pure science in the fields of systems theory, mathematics, biology and computer science – using his own invention, Mathematicatm, as a tool to help his explorations along.

In trying to understand how complexity can derive from simple systems and programs, Wolfram spent some years studying "cellular automata". These are sets of cells, wherein each cell transforms itself sequentially according to the state of its neighbors. The cells obey a very small set of pre-programmed rules – a simple transformation protocol. So, for example, a cell will become white if it sees 3 other black cells residing in the 3 cell locations immediately above it (i.e., to its NW, N and NE). But it will become black if there are only 2 black neighbors in those 3 cells, say, residing in its N and NW directions. As in this example, the cellular scheme that Wolfram investigated early on was composed of a single, 1-d, horizontal line of cells. The result of each cell’s transformation was placed on the next horizontal line directly underneath that cell, and so on as the pattern grew and changed. (John Conway’s old computer game called Life worked the same way, except it operated on a 2-d field.) For his 3-adjacent-neighbor example, Wolfram established a way of defining the protocol graphically, with the 8 possible states of the neighboring 3 cells above, and the resulting transform state below:

In this model, there are 256 possible transform rule combinations (28). The one above is labeled "Rule 90" by Wolfram. When carried out, it produces a pattern of nested triangles. Other rules created complex, unpredictable patterns. One of these is Rule 110. Incredibly, Rule 110 has been shown to be able to emulate a Universal Computer (Turing Machine)! Here is its transform protocol:

When I read this early section of the book, I was struck by the simplicity and elegance of this rule format. It occurred to me that it was so simple, it ought to be able to be represented and carried out on a computer spreadsheet. After all, I knew you could nest a total of 7 "IF" statements in MS Exceltm, and given that there are 8 transform states in this particular cellular automata model, that might be enough to define and control it – the 8th state becoming the final "default" condition.

My poor peanut brain is subject to overload whenever I do Exceltm statement nesting, and I got a real rip-snorter of a headache before I finally got my parentheses correct. Here is how I ended up. I first defined the transform protocol in a group of spreadsheet cells, in the same format as shown above. I used a character "X" to represent a black cell, and a blank for a white one:

The B4 cell master formula is as follows (be careful you don't snag your pants leg on those parentheses):


Set the transform protocol rules in row 2 -- the black (X) or white (blank) result of each of the 8 "neighbor states" -- and copy the master formula from cell B4 into a big area of the spreadsheet. Enter an "X" in a cell up near the top middle of your copied area to "seed" it. The cellular automata "history tree" will unfold below it:


As a postscript, I have to say that I got bogged down a bit before I finished the book -- it is a long one -- but I did slog through it all. The "notes" section in the back occupies close to a third of the total pages, and this (to me) was the most interesting reading. I think Wolfram's point is that biological systems -- you and me -- are made up of billions of simple cellular units, and those individual units don't really need lots of rules or "intelligence" to operate. But the output of their collective congress can produce fantastic complexity when viewed as a whole. In the final analysis, that unpredictable and wonderfully symphonic system behavior ends up being the epiphenomenon we call "I".

  Back to Recreational Computing...  




First-time visitors -- including you!

Free Web Counter

Free Hit Counter The Foggiest Notion The Foggiest Notion The Foggiest Notion The Foggiest Notion The Foggiest Notion


Luck Favors the Prepared Mind...

Essays • Lost Articles • Loose Ends • Collections • Computing • Projects • Widdershins • Quotations • Links • Us

Site contents Copyright 2004-2008 by Gary Cuba       Email: webmeister at thefoggiestnotion dot com