Eat Your Heart Out Star Trek
Continuing this series on Cellular Automata, I’d like you to look at a very simple rule. This rule is credited to Carnegie Mellon Professor Ed Fredkin, and I’ll have more to say about him in a bit. For now, this is his rule:
A cell is on if and only if an odd number of its neighbors are on
What does this rule do? Well, let’s try it. I started with an initial pattern of “on” cells that formed a “+” sign and ran it for a few generations. Here’s an animation of the results, showing the progression of the grid:
It made copies of the pattern! But maybe this was the choice of pattern? How about something different, like a smiley face?
Same result! It keeps replicating its pattern, no matter how large or complex.
And maybe it’s just me, but I love how the the pattern seems most chaotic right before it “crystallizes” into copies.
There Goes the Neighborhood
Cells decide their state by applying the rule we give them, and using for information only their own state and/or the state of their neighbors. Yet how do we define a cell’s neighbors or its neighborhood?
Up until now, I’ve been considering the 8 adjacent cells (above, below, left, right and diagonally) as the neighborhood. This is known as the “Moore Neighborhood” and here’s an image below (courtesy of Wikipedia).
The blue cell is the active cell — the one whose state is being decided, and the red cells are its neighbors, or its neighborhood.
However, the “Moore Neighborhood” isn’t the only possible neighborhood. One alternative is the “Von Neumann” neighborhood, which consists of the 4 cells (left, right, above and below) around the current cell. Here’s a diagram of what the Von Neumann neighborhood looks like (courtesy of Wikipedia)
Again, the blue cell is the active cell, and the red cells are its neighbors, or its neighborhood.
So what happens if I use the Von Neumann neighborhood with the replicator rule?
It still replicates, but now the arrangement mirrors that of the neighborhood. In fact, looking back on the previous examples, it’s now clear they also mirror the arrangement of their neighborhood (Moore).
This is a pretty robust replicator. It even functions when the boundaries wrap around to the other side (so the extremities interact).
If you’re interested in trying out this and other rules, you can download a free Cellular Automaton Package for Windows, Mac, Linux, Android or iPad.
It’s Not What You Do, but the Way You Do It
That there’s replication going on is not impressive; it’s HOW the replication happens that is.
There is no replication command in this system. There is no program that scans cells, calculates distances and copies them. Each cell operates independently and simultaneously, following an update rule that’s identical to every other cell. Each cell uses as information only its own state and/or the state of cells immediately adjacent to it. No cell knows where it is, its relationship to the whole, what the whole is like, or that there is even a whole. This is strictly a local phenomena.
Yet despite this locality, global copying takes place. We’ve got a process emerging through interactions of parts that don’t exhibit this property. It’s this phenomena — Emergence — that makes Cellular Automata so fascinating.
The idea that we can create something that seems to take on a life of it’s own — to the point that we can study it — is fascinating. We can all be researchers, scientists with our computers. And yes, people catalog rules and the patterns in those rules. This is how I stumbled on this replicator rule, by studying an inventory of these patterns.
Ramifications on Reality?
If I believe simplicity underlies reality at it’s most fundamental — possibly far below the Quantum level — then this is food for thought. Here is a system that is deterministic, local, and with a simple, uniform rule governing it. It’s hard not to wonder if reality is something like this.
What’s more, such a view would not undermine any current science, but explain it. For instance, apparently non-local phenomena and randomness can be explained by deeper, local deterministic connections (maybe I’m dancing too close to the Hidden Variable Theory?). An analogy would be seeing two apparently identical balls roll differently, and chalking it up to randomness, then looking deeper and finding this apparent randomness was caused by deterministic phenomena like slight imperfections in the ground or slight differences in their composition that throws them off balance.
On the other hand, why should things be deterministic? Why not random? Aren’t both an arbitrary choice when we get fine-grained enough? Could determinism actually be an emergent property of an underlying randomness? For that matter, is the macro world deterministic? We can predict things with varying levels of accuracy, but there’s always a limit to how accurate we can get, which I assumed was due to our ignorance. Is that so, or is that simply randomness?
And why should things be simple? After all, if I expect complete simplicity, I’m forced to ask why there’s something instead of nothing. After all, to have nothing is much simpler than to have something. Once I allow for something, then why do I draw the line there? Why do I accept a something consisting “only” of cells, states, connections and an update rule, instead of a something consisting of a huge array of particles and laws?
Still, the view that reality may be something like a Cellular Automata has been proposed by some. Which brings us to…
Early in this article, I mentioned Ed Fredkin. Fredkin believes reality at its most fundamental may be something like a Cellular Automaton. He called this view “Digital Physics”, but has since come to prefer the phrase “Digital Philosophy” (DP).
[…] DP is an atomic theory carried to a logical extreme where all quantities in nature are finite and discrete. This means that, theoretically, any quantity can be represented exactly by an integer. Further, DP implies that nature harbors no infinities, infinitesimals, continuities, or locally determined random variables. […].
At the most fundamental levels of physics, DP implies a totally discrete process called Digital Mechanics. Digital Mechanics (DM) must be a substrate for Quantum Mechanics. […]