Fourier Life

As I mentioned in my post on Amazon’s web services one of the things I’ve been thinking about is a way to do analysis on the GOL universe to find interesting things even if I’m not watching. Poking around the web turned up Fourier Life which discusses an automated method of finding replicating structures in cellular automata. As discussed there one of the most interesting things about cellular automata is the emergence of self replicating structures from random fields of cells. This obviously has interesting similarities to the emergence of biological life and is one of the areas that I’m exploring as well. The method used is to plot the percentage of living cells vs. time and to look for periodic fluctuations. When replication occurs the number of cells increases and decreases with regularity and this can be detected by running a Fourier analysis on the sequence. If replicators are present then the analysis show peaks at the replication rate of the structures and indicates there is more than just random noise present in the field of cells. This seems like a good start to a status monitoring routine that can watch what’s happening even if I’m not around. The images below illustrate this process and are the work of Sean Murphy from http://stm1968.tripod.com/fourierlife/. A catalog of search programs to aid in finding interesting patterns has also been put together by David Eppstein at http://www.ics.uci.edu/~eppstein/ca/search.html.

One thing interesting to note is that it’s been known for a long time that Conway’s rules don’t produce self replicators from random fields of cells but other rules do. I find this odd since Conway’s rules are Turing complete and should be able to perform any computation that any other rule set does. Fortunately the software I’ve written makes it easy to use other rule sets and I’ll be exploring those as well. Considering that John Conway himself stated the following about HighLife (rule B36/S23) I’ll likely explore that next.

“It seems to me that ‘B36/S23’ is really the game I should have found, since it’s so rich in nice things.”