The Problem Defined

My goal was to find more self-replicating systems that emerge spontaneously from a random field of cells. I stumbled upon the first one (see System A, Rule 1 above) by testing lots of rules and looking at graphs of the number of live cells over time.  At first, I was just looking for more examples of interesting rules such as Conway's game of life (see green line below). However, when I found the first self-replicating system, I was much more interested in these because of the implications for the Origin of Life.

The problem is that the total number of rules is way too many to look through by hand (4,294,967,296 for the 2-rule system in which the original self-replicator was found). I needed some way to detect self-replicating systems, or to at least narrow down the number of rules to visually examine. One method would be to analyze the cells and look for repeating patterns. I imagined it would be difficult to write efficient code to do this. It would also be taxing on the cpu which would limit the number of rules that could be tested. Another approach would be to analyze the number of cells alive at each iteration, a number easily calculated as each iteration of the grid is generated. This second approach seemed promising based on a comparison of the graphs below.

The green line is the percentage of cells alive for each iteration of Conway's rules (B3/S23) starting from a random field of cells. The red line is the simple rule of B2/S3. The result of this rule set is just noise and the percentage of cells remains fairly constant.  The blue trace is the original self-replicating rule set (alternates between B3/S23 and B2/S56) where the creatures emerge from the random cells and replicate to take over the world.

The green and blue traces are similar but the blue, self-replicating trace has a unique feature:  there is a periodic nature to it as shown by the small vertical lines at the bottom.  The number of alive cells seems to rise and fall every 12 iterations.  If we look at the life cycle of the self-replicator below, we notice that the creature replicates itself every 12 iterations. The overall problem of detecting self-replicating systems was thus reduced to the problem of detecting periodic fluctuations in the population graphs.