Periodicity and Attractors

Many cellular automata eventually repeat.

A fixed point repeats every generation.

An oscillator repeats after several generations.

On a finite grid, deterministic cellular automata must eventually revisit a previous state because only finitely many states exist.

That makes cycle detection a fundamental measurement: where entropy asked how uncertain a state is, recurrence asks whether the dynamics ever come back.

Hash each state

For binary arrays we can store the bytes:

def state_key(state):
    return state.tobytes()

Then track when each state first appeared:

def find_cycle(history):
    seen = {}

    for t, state in enumerate(history):
        key = state_key(state)

        if key in seen:
            start = seen[key]
            return {
                "transient": start,
                "period": t - start,
                "repeat_at": t,
            }

        seen[key] = t

    return None

(Verified: constant histories report transient 0, period 1; alternating two-state histories report period 2; Rule 30 shows no cycle within 200 generations — None is a finding about the window, not a verdict about the rule.)

The detection logic as a flow — one pass, first repeat wins:

    flowchart LR
    S[state at time t] --> K{seen before?}
    K -->|no| R[record first-seen time]
    R --> S
    K -->|yes| C[transient = first-seen, period = t - first-seen]
  

Four outcomes, four different claims — do not confuse them:

Fixed points

A fixed point has period one:

state(t+1) = state(t)

Detect it cheaply:

def is_fixed(previous, current):
    return bool(np.array_equal(previous, current))

Examples include empty worlds and stable Life still lifes.

Oscillators

A period-two oscillator satisfies:

A -> B -> A -> B ...

But there is no reason to restrict ourselves to period two.

Cycle detection lets us discover arbitrary periods within our observation window.

Transients matter too

Two rules may both settle into period-one states.

One may do so after three generations.

Another may spend thousands of generations generating structure before settling.

So record both:

transient length
cycle period

The pair contains much more information than final state alone.

Finite worlds can mislead us

A finite periodic grid guarantees eventual recurrence.

That does not imply the corresponding infinite cellular automaton is globally periodic.

Our measurements always belong to an experimental setup:

rule + initial state + world size + boundary conditions

This is another reason to store experiment metadata alongside metrics.

Detecting recurrence without storing everything

For long simulations, keeping every full state may be expensive.

One option is hashing:

import hashlib


def digest_state(state):
    return hashlib.blake2b(state.tobytes(), digest_size=16).digest()

Store digests first and retain occasional checkpoints if you need exact reconstruction.

For very long runs, classic algorithms such as Floyd’s tortoise-and-hare cycle detector can find cycles with constant memory, provided the transition function is deterministic.

Attractor basins

Run the same rule from many random initial conditions:

from collections import Counter

periods = Counter()

for seed in range(100):
    history = run_rule(90, seed=seed, initial="random")
    cycle = find_cycle(history)
    periods[cycle["period"] if cycle else None] += 1

Now we can ask whether many starting states converge to the same type of attractor.

This begins to reveal the structure of the rule’s state space — “begins” deliberately, since period histograms approximate basin structure rather than mapping it: two attractors can share a period, and long transients can outlast the window.

A useful behavioral record

def recurrence_metrics(history):
    cycle = find_cycle(history)

    if cycle is None:
        return {
            "cycle_found": False,
            "transient": None,
            "period": None,
        }

    return {
        "cycle_found": True,
        "transient": cycle["transient"],
        "period": cycle["period"],
    }

Combine this with density, activity and entropy.

We are gradually building a multi-dimensional description of behavior.

Next: sensitivity

A rule can also be characterized by what happens when we change one bit of its initial state.

Do the two futures remain similar?

Or does the difference spread across the world?

That question leads us directly to sensitivity to initial conditions.

Research

• Zenil, H. & Martinez, G. J. — Cellular Automata (Scholarpedia). Attractor-basin analysis (Wuensche) relating basin structure to space-time patterns and rule-table measures is the literature behind this chapter’s sampling loop — and the same source warns that finite observations can miss long transients, which is why transient length is recorded alongside period here. http://www.scholarpedia.org/article/Cellular_automata

• Berto, F. & Tagliabue, J. — Cellular Automata (Stanford Encyclopedia of Philosophy). Gives the reason recurrence detection matters beyond bookkeeping: for universal systems no analysis predicts the evolution, so empirical orbit-following — transients, cycles, basins — is the method, not a stopgap. https://plato.stanford.edu/entries/cellular-automata/