The Solution: Fourier Transform

The key to finding emergent self-replicating creatures is to apply a Fourier Transform to the number of cells which are born, survive or die. For the original self-replicating rule set, here are the graphs:

The graphs above are slightly wavy with a period corresponding to the number of iterations the creature takes to self-replicate. The Fourier Transform is able to extract this information from the graphs, as shown below.

The Fourier transforms of the three traces reveal two important things. First, peaks or inflections appear at regular intervals, although all peaks are not present in all three traces. Second, the number of sections between the peaks is equal to the period of self-replication divided by two: there are 6 segments above and the period is 12.  For an odd-numbered self-replication period such as 7, the graph is separated into 3.5 segments with the half-segment on the right (higher values on x-axis).

Once the Fourier Transform is computed, it is simply a matter of finding the peaks located at regular intervals. One can go about this task in multiples ways, and the choices I describe below are only one possibility. However, the important result from the Fourier Transform is that periodic self-replication shows up as peaks at regular intervals, the location of which are determined by the number of iterations required to replicate.

Once the peaks were detected (I combined together the three graphs and then used a signal-to-noise ratio of >3.5 to detect peaks), the following parameters were calculated for each possible period of replication (I used 5 to 48):

• avg_hgt:  average peak height
• num_pks:  number of peaks detected
• frac_per:  fraction of peaks found for a given period out of the total number expected for that period
• frac_tot:  fraction of peaks in the given period out of the total number of peaks

Through a process of trial and error, the formula below was found to work well for finding self-replicating systems.

Selector = avg_hgt * 2^(num_pks/2) * frac_per^2 * frac_tot

The Selector is calculated for each possible period of replication (5-48) and the highest Selector value is saved for that run (usually 512 iterations).  Once again, other formulas will work as well.  And different formulas may work better for different rule systems. I have in fact tried many different formulas but I never ran enough trials to say which ones were better than others. The above is one of the simpler ones.

In a standard run, I randomly tested about 15,000 rules, calculating the Selector for each one and saving them in a database. I only ran each rule on a 100x100 grid for 512 iterations to see the diagnostic frequency peaks in the Fourier Transform. Then I analyzed the database, examining visually only the ones with Selectors above a certain value (usually Selector >100 using the formula above).

In other cases, I experimented with a genetic algorithm to find self-replicating systems. Each generation would consist of 30 rule codes, and I ran the experiment for 512 generations.  The process was fairly complicated, and at the end of the day it's not clear that it worked any better than just random chance for finding self-replicating systems. However, for the experiments that did find replicators, the genetic algorithm was able to find similar rule codes with similar replicators.

To see the emergent self-replicators I've discovered with this method, choose System B or C above and try the various Rules.