Strategy for searching for elementary cellular automata (cyclic boundary conditions) that repeat

Question

I am looking for elementary cellular automata rules and initial conditions that give rise to interesting cycles (Cyclic boundary conditions, such that the leftmost entry is the neighbour of the rightmost entry). After running a rule with some starting state, the state of the CA might (will?) start repeating in "cycles".

I would like to search for and record rules and initial conditions that lead to interesting cycles (Similar to what was done here. The interesting-ness of a rule+initial condition will later be determined by a few metrics specific to my application.

How should I perform the search given that the CA width/dimensionality will be high (around 100) and the cycle period should be long (500-1000)?

This is my current strategy in python-like pseudo code:

dimensionality = 100
trails_per_rule = 10
max_evolutions = 1000

results = [] # Container to store the interesting rules and initial conditions
For rule in all ECA rules:  # Loop though all ECA rules
    states_that_lead_to_cycles = []  # For a given rule, create an intermediate store of states that lead to cycles.
    for trail in range(trails_per_rule): # Look for cycles using several starting states
       state = random_bit_array(dimensionality) # initial state
       if state in states_that_lead_to_cycles:
          break # Don't run an evolution that you know will lead to a cycle.
       else:
          evolution_store = [state]; # Contrainer to store the evolution of states as the rule is applied
          for i in max_evolutions:
              state = evolve(rule,state) # Apply the ECA rule
              if state is in evolution store: # Check if a cycle is identified
                 results.append(initial state, rule and cycle information) # Store the interesting cycle
                 states_that_lead_to_cycles.append(evolution_store[indexes of the cycle]) # Save all states that occur in the cycle and avoid them in future runs
                  break
              else:
                  evolution_store.append(state)

The reasoning is that all states that are confirmed to occur in a cycle should not be investigated again, since it is known that they will lead to a cycle. Since there are too many initial conditions to perform an exhaustive search, random initial conditions are chosen.

1. Does this seem like a reasonable strategy?
2. Will all rules eventually lead to cycles since there is a finite number of states that can be taken in the evolution? Are there different cycles possible for a given rule based on what the initial condition is?
3. Should I search only through the inequivalent ECA's? How can this be done?

Any advice or critique on my understanding will be appreciated.

Answer 1

Yes, all initial states under all CA rules on a finite grid will eventually lead to a cycle (or a fixed state, which can be viewed as a cycle of length 1). More generally, iterating any fixed deterministic map on a finite domain of $n$ elements from any initial value in the domain will inevitably lead to a cycle in at most $n$ steps.

However, note that the expected length of the cycle, and the number of steps needed to find it, is proportional to $n$ for a randomly chosen bijective map and to $\sqrt n$ for a random non-bijective map. While the maps generated by CA rules are not randomly sampled from the set of all possible maps between grid states, AFAIK the same average-case behavior still holds empirically: the average cycle length for a randomly chosen CA rule on a $k$-cell lattice with $s$ states per cell is proportional to $s^k$ if the rule is reversible (and thus generates a bijective map), and to $s^{k/2}$ if it is not.

Of course, specific rules can deviate from this average-case behavior, and it's possible that your "interesting" rules happen to have a cycle structure that differs significantly from the average. (Indeed, I already implicitly noted one example of such a class of non-average rules, namely the reversible ones.) However note that, if this is the case, it also implies that most rules are not "interesting" by your definition.

---

As for the reasonability of your search strategy, I see no reason why it shouldn't work, in the sense that it should do what you say: find rules and initial states that lead to a cycle in less than some fixed number of steps.

However, I suspect that your search method is needlessly complicated, in the sense that (at least with your sample parameter values):

• For most rules, you're unlikely to find any cycles at all (since your maximum number of search steps, 1000, is significantly lower than the average expected cycle length $\sqrt{2^{100}} = 2^{50} ≈ 10^{15}$).

• For rules where many random initial conditions do converge quickly to a short cycle, it's likely that either:

  • (almost) all patterns converge to the same final state or cycle (e.g. the all-zero state, or a cycle between the all-zero and all-one states), or
  • there are many more cycles than your trials per rule (consider e.g. Conway's Game of Life, where a typical final cycle consists of a bunch of isolated static patterns and/or low-period oscillators scattered randomly on the grid).

  In either case, there's little point in trying to detect whether two random initial states converge to the same cycle: either they almost always do (and the cycle is likely short, and thus would be quickly detected anyway), or they almost never do. (That is, of course, unless determining which of these two possibilities occurs is part of what you want to investigate!)

In general, I'd only bother trying to detect collisions between cycles if your number of trials per rule, multiplied by the maximum number of steps per trial, was comparable to or higher than the square root of the number of possible lattice states (so that observing two trials converging to the same cycle was likely even for a random rule).

In particular, if you did not try to detect collisions between separate cycles, you could use less memory-hungry cycle detection algorithm such as Floyd's ("tortoise and hare") or Brent's algorithm. While these typically need more steps to find the cycle (by some small constant factor), they also don't require looking up and storing states in a hash table, which saves time and memory accesses. Due to their low memory usage, these algorithms are also very well suited for parallel implementation e.g. on a GPU, which could likely speed up your search by many orders of magnitude.

(Also, if you really wanted to count the number of times each distinct cycle was found, you could still do that even in a parallel implementation: just pick a distinct state — e.g. the lexicographically lowest one — from each cycle found and return it as a representative of the cycle. The just count the number of times each representative state was returned.)

---

Ps. Yes, you can save some time by searching only one representative of each class of equivalent rules, since the cycle structure of equivalent rules will be isomorphic (i.e. identical up to a relabeling of the states).

The accepted answer to the question you linked already gives Python code for finding a representative of each equivalence class of ECA rules, but the general approach is:

1. For each rule, generate all of its equivalent rules by applying all the known equivalence transformations (such as swapping the left and right neighbors, or swapping the two cell states in both the input and the output) iteratively, until no more new equivalent rules are found.
2. Pick some canonical representative out of this set of rules, e.g. the one with the lowest rule number.
3. Mark all the equivalent rules as already processed, so that you won't need to repeat the process above for each of them. (Or just don't, and remove the duplicates from the list of canonical representative rules at the end.)

Note that there's some room for ambiguity in the definition of rule equivalence. In particular, for the subset of rules that are invariant under cell state inversion, there are additional transformations (such as inverting only the output states of the rules) which generate a rule that is in some sense equivalent to the original (in that the time evolution of any pattern under the transformed rule encodes its evolution under the original rule, and vice versa) but whose cycle structure is subtly different (e.g. the all-dead and all-live states are fixed points under one of the two equivalent rules, but form a 2-cycle under the other).

Also note that, on a finite lattice, even the two basic rule equivalences (left/right reversal and cell state reversal) will only be true equivalences if the grid boundary conditions are compatible with them. A cyclic boundary (where the left side of the grid loops around and connects to the right side) is compatible with both, but e.g. an all-zero boundary is not compatible with cell state reversal, and a boundary that was all zeroes on the left and all ones the right would not be compatible with either (although it would be compatible with their combination).