Cellular Automata Systems

This post explains the cellular automata systems I've explored (each can be selected from the Cellular Automata System dropdown box above). All but the simplest system explored have produced self-replicating creatures which appear spontaneously from a random field of cells.

System	# of Rules	Emergent Self-Replicators
A. 2-State: Alternating Rules	232	yes
B. 2-State: Edge & Corner Combinations	248	yes
C. 3-State: Sum of All Edge States	324 (~238)	yes
D. 2-State: From Pattern (Conway-Like)	216	no (yes from pattern)

A. 2-State: Alternating Rules

This was the system in which the first emergent self-replicator was found (Sytem A, Rule 1). The system uses the Moore neighborhood and simply counts the total number of neighbors. However, unlike Conway's Life which uses the same rules for every iteration, my system alternates between two different rules. I found many self-replicating rules, but gave up on this system when I realized it isn't a local cellular automata, i.e. each cell needs not only the number of neighbors but also which generation the whole world is on.

B. 2-State: Edge & Corner Combinations

After abandoning the "2-State: Alternating Rules" system, I looked extensively in the 2-State, Moore neighborhood with just one rule for every iteration but didn't find anything. I thought having more possible rules might help. I decided to count the edge (E) and corner (C) neighbors separately and treat each combination of edge and corner neighbors as a Born/Survive rule. This new system had many more possible rules to explore (2^48 vs. 2^16), and I did find emergent self-replicators in it!

Below is the rule code for the Fourth of July rule (System B, Rule 1). The code is shown both as a written list of Born/Survive states and in a graphical view I created in my original Visual Basic 6 program.  The first entry (Rule-Born (E|C): 0|2) means that a cell is born into an empty cell if that cell has a combination of 0 edge neighbors and 2 corner neighbors.

Rule-Born (E|C): 0|2, 0|3, 1|4, 2|0, 2|3, 2|4, 3|2, 3|4, 4|0, 4|3, 4|4

Rule-Survive (E|C): 0|1, 1|2, 1|3, 1|4, 2|0, 2|4, 3|0, 3|2, 3|3, 4|4

C. 3-State: Sum of All Edge States

Once I had found self-replicating rules in the 2-State system, I was interested in exploring other systems.  The simplest 3-state system is to simply take the sum of the states (0, 1 or 2) of the edge neighbors (the von Neumann neighborhood). The range of values for any cell with at least one neighbor is 1 to 8 (the maximum has all four edge neighbors in state 2).

Below is the rule code for Game of Jacks (System C, Rule 2), both written out and in the visual representation from my Visual Basic 6 program. The 'N' refers to the neighbor sum and 'S' refers to the state that cell will be changed into (either 1 or 2 because state 0 is the empty cell). For example, the first rule (Rule-Born (N|S): 1|2) means that a cell will be born if the sum of neighbors is 1 and that cell will be born as state = 2. The last rule (Rule-State2 (N|S): 8|2) means that if a cell currently in state 2 has a neighbor sum of 8 it will be set to state 2 in the next iteration (i.e. stay as state 2).

Rule-Born (N|S): 1|2

Rule-State1 (N|S): 1|1, 3|1, 4|2, 6|1, 8|2

Rule-State2 (N|S): 1|1, 3|1, 4|1, 8|2

D. 2-State: From Pattern (Conway-Like)

Self-replicators have been described previously for simple Conway-Like systems by D. Eppstein on his Cellular Automata: Replicators page, but none emerge spontaneously from a small, random field of cells (or if they do, it is quite rare).  I found most of the self-replicators described by Eppstein by starting from a small group of cells, iterating for 512 generations, and then applying the Fourier Transform method to detect self-replicators.  So far, I have not found any new ones. I looked extensively in the rule for Conway's Life (B3/S23) but, as Eppstein also noted, no self-replicating patterns were discovered.

I don't consider this last set of self-replicators to be examples of Fourier Life because they do not emerge spontaneously. But I include them here because the Fourier Transform method can detect them, and because they're interesting!