As 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.

What’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.