Physics is local. The two great pillars of Twentieth Century science, general relativity and quantum mechanics, can be viewed as supplanting the mysticism of ``action at a distance'' and ``force fields,'' by such mundane, self-evident, and intuitive mechanisms as the Riemann curvature tensor, virtual gluons, and the Higgs field. Both of these theories describing the universe in the large and the very small (albeit in mathematically incompatible ways), tell us that all the complex fabric of events we observe are consequences of individual particles locally responding to conditions directly affecting them, whether moving along geodesics in curved spacetime or undergoing interactions through particle exchange. Both theories have withstood all experimental tests to date, including many thought impossible when they were originally propounded.

A cellular automaton (CA) is a mechanism for modeling systems with local interactions. A cellular automaton is a regular lattice of cells with local state, which interact with their neighbors subject to a uniform rule which governs all cells. The neighborhood (the set of cells whose state can affect a given cell at one instant) can be classified by the dimensionality of the automaton (most experimentation is done with one- or two-dimensional automata), and by the geometric fashion in which cells are interconnected.

The rule is the ``program'' that governs the behavior of the system. All cells apply the rule, over and over, and it is the recursive application of the rule that leads to the remarkable behavior exhibited by many cellular automata. When experimenting with cellular automata, one is primarily engaged in defining new rules which lead to interesting or useful behavior. The programs in the Rudy Rucker CA Lab from Autodesk are tools for the person engaged in such experiments. Our programs allow you to create a rich set of rules and experiment with their behavior without requiring the purchase of expensive special-purpose hardware.

Cellular automata appear to be abstract and devoid of practical applications, much as was said of computer graphics not long ago. If you want to model a universe which seems to be made up of particles which interact locally, there are two basic ways to go about it. The first is to create a huge array of numbers that represents the interacting items, then find the biggest number cruncher you can lay your hands on and set it gnawing away at the problem. The supercomputer boom, fueled by applications of this approach to weather prediction, computational fluid dynamics in the transonic and hypersonic regimes, plasma dynamics, and an almost endless list of other applications testifies to the effectiveness of this approach.

But maybe there's another way. Until recently, cellular automata were
primarily a theoretical tool. The price of a cellular
automaton with uniform edge size increases as the *n*th power of its
size, where *n* is the dimensionality of the cellular automaton. This
gets out of hand rapidly, even if you're only working with two
dimensional cellular automata. Therefore, although they may be the
way the universe is really assembled and therefore worthy of study, no
one would consider building one!

Hardware realizations of cellular automata, such as the CAM-6 board, have been built. The CAM-6 is not a true cellular system; it emulates one by using a fast RAM array and a look-up table, but it permits exploration of a rich set of cellular automata with performance adequate to study their behavior in detail. The CAM-6 is a highly effective tool, but it is, at $1,500, an expensive one. It's priced out of the reach of many creative people who should be exploring cellular automata. It was the desire to make cellular automata experimentation available at a low price to a large number of people that spurred the development of this product.

For cellular automata need only to find a concrete, compelling
application to a real-world problem to burst into silicon and totally
change the way we think about computing. Consider this: inside the
computer you're using now are ranks and ranks of RAM chips. A
256K x 1 static RAM chip has a memory cell consisting of four to
six transistors, connected in rows and columns to circuitry on the
periphery of the chip. Even when the computer is running flat-out,
you're using precisely one cell at a time. This is the classic
bottleneck in the von Neumann computer architecture (John von Neumann
was very aware of this problem; in fact, he and Stanislaw Ulam
*invented* cellular automata precisely as a tool for modeling complex
systems), which has led to proposals such as Backus' functional
programming, neural systems, and many other architectural proposals,
such as SIMD machines, which seem to be more effective in generating
Ph.D.s than numbers.

If a two-dimensional cellular automaton with 256K cells were realized in silicon, it could compute 262,144 times faster than a serial processor accessing data bit-by-bit from a memory array. Yet, engineered for volume production, made in comparable volumes, and given time to slide down the learning curve, it need cost no more than a RAM chip. This is the potential of cellular automata. The beauty of two-dimensional cellular automata is that they map perfectly into our semiconductor manufacturing technology: they need the things it does best as opposed to, say, neural systems where the number of connections exceeds the capability of two layers of metal.

If there is merit in Edward Fredkin's suggestion that the fine-grain structure of the universe is really a cellular automaton, then cellular automata machines will play the role of particle accelerators in exploring this level of reality.

Some of the brightest minds of our century have been involved with
cellular automata because they comprehended what cellular automata can
do. John von Neumann, Stanislaw Ulam, John Horton Conway,
Stephen Wolfram, and Edward Fredkin do not
spend their time on nonsense. With the Rudy Rucker *CA Lab* from
Autodesk, you can begin to explore the potential that attracted those
men to create and research this new way to compute. And perhaps you
will discover something that will add your name to the list.

There's plenty to discover. Rudy's semitotalistic 16-state RC program
permits you to create 16^{(16×9)} different rules for cellular
automata. This is a number slightly larger than 10^{176}. My more
general 256-state CA program lets you program 256^{216} distinct CA
rules, which is a number larger than 10^{157826}. These numbers are
``effectively infinite''. Roughly 10^{17} seconds are thought to have
elapsed since the big bang ushered in the universe. If you had been
around since then, creating, testing, and evaluating one rule per
second, you still wouldn't have made a dent in this number, anymore
than a buck makes a dent in a trillion dollars. Take away one dollar
and you still have about a trillion. Even with enough time, you'd
have a lot of trouble writing down the results of your exhaustive
search for rules, as the universe is believed only to have on the
order of 10^{80} particles in it, so you'd run out of places to make
notes even if you turned the entire universe into a cosmic
all-encompassing Post-it^{tm} note. If the still-unconfirmed Grand Unified
Theories are correct, by the time 10^{40} seconds have passed, more than
half of the protons will have evaporated into little poofs of energy
and leptons, taking with them the fruits of your labors, and leaving
what's left of you with 10^{157826} bottles of beer on the wall.

So get started, people! The human mind works a lot better than blind
search (one imagines a middle manager reporting, ``Nothing much
yet--we need more monkeys, more typewriters.''). *CA Lab* unleashes your
creativity in a virtually infinite domain, where your discoveries may
be not only interesting or rewarding, but may create a whole new
world. The challenges in cellular automata are clear: how to realize
them in hardware, how to apply them to useful tasks, and how to make
money doing it. You now possess a tool for exploring all three.

Editor: John Walker