Sean Murphy has been doing some interesting experiments with two-dimensional cellular automata, described at his Fourier Life web site. The name comes from his use of Fourier analysis to detect replicators in cellular automaton rules: if one does a Fourier transform of the graph of live cells vs time starting from random initial conditions, replicators show up as regularly spaced peaks in the frequency domain, in contrast to oscillators which would only show up as a single peak.

Based on this technique, he's found many individual replicators and near-replicators, with interesting patterns of behavior. Two of my favorites are "Qix!" and "Butterflies vs Centipedes" (both on three-state semitotalistic Von Neumann neighborhood automata): in Qix!, replicators compete with wick-stretchers, that eventually fill the grid with a Mondrian-like rectangular subdivision, while in "Butterflies vs Centipedes" the butterflies and centipedes refer to two different types of replicators that can both be seen at the same time in different regions of the grid.




Comments:

ext_1178084:
2012-04-25T03:09:52Z

Thanks for the link to my site!

Oscillators actually show multiple peaks in the Fourier Transform as well, but the amplitude is usually lower than with self-replicators. There is definitely not a perfect correlation between detecting multiple peaks in the Fourier Transform and self-replicators, but it certainly helps in narrowing down the number of rule sets that need to be examined by hand.

Sean

ext_697963:
2012-04-25T23:42:21Z

So much annoying ads <_< Is there going to be an arxiv.org preprint?

11011110: 2012-04-26T19:04:48Z

Oh, are there ads there? Sorry about that. I tend to block them, so I didn't notice.