Fun with Cellular Automata

October 15, 2004 | Computer Science, My Projects | By: Mark VandeWettering

A Family of Cellular AutomataAs part of my dose of IT Conversations recently, I listened to this interview with Stephen Wolfram, author of the book A New Kind of Science. Wolfram is an odd duck, but I found his talk to be suprisingly good, and he raised an interesting question: do random programs do anything interesting?

He decided to try to analyze some very simple programs to see if they did indeed have interesting behavior. Instead of choosing complex machines like a Pentium, he instead used a 1D cellular automaton. If you haven’t heard of these before: here is how they work:

  • The world consists of a linear array of cells. In this example, the cells form a ring, so every cell has two neighbors, and there are no funny boundary conditions.
  • Each cell can be either on or or off.
  • Time proceeds by steps. All cells are updated simultaneously.
  • To compute the next value of a cell, the contents of it and its two neighbors are used to look up the next value in a rule table. For instance, a given rule might map the pattern ON-OFF-ON to ON.
  • We graph the evolution of the “world” by displaying each successive generation as we go down the page.

There are 256 possible rulesets (since there are 8 patterns, and each pattern can be mapped to two outputs, there are 2^8 possible rulesets), so I wrote a simple program to run each ruleset on a world consisting of 128 cells evolved for 128 generations. I then cut those all together to make the quilt pattern you see on the right.

Rule #30What’s surprising is that there are some really fairly complicated patterns. For instance, the pattern on the right is generated by rule 30. It displays some rather chaotic structures, even from these almost trivial rules. Wolfram suggests that very simple interactions in nature generate either very simple behavior, or behavior which is essentially equivalent to universal computation. I’m not sure whether this is idea is novel, useful or just a crackpot theory, but it was fun to kill 10 minutes writing up the simple program.

Share Button
Be Sociable, Share!

Comments

Comment from stran
Time 10/20/2004 at 7:04 am

Dude- this is cool stuff. I actually read this book last year and i have to say it got me thinking! Wolfram is definitely an interesting cat and he certainly has a very high self opinion. I’d say they could drop more than a couple pages from what was a very long book by eliminating some of his “I’m so awesome” type ramblings.

Anyway- I think the book will have its biggest impact on biology. I think the concepts he displays correlate well to Darwin’s evolutionary concepts. In particular his idea of mutation as the key to the propigation of new species. Anyway, there’s a lot there I’d like to discuss… maybe as podcast! I’m not a biologist, though….

:)