A three-cell rule that looks random. What it is and why it's interesting.
#cellular automata#randomness
Rule 30 is a one-dimensional cellular automaton: a row of cells, each on or off, updated in steps. A cell's next state depends only on itself and its two neighbours.
the rule
There are eight possible neighbourhoods. Reading the outputs as a binary number gives the rule its name: 00011110 is 30.
neighbourhood 111 110 101 100 011 010 001 000
next state 0 0 0 1 1 1 1 0
Written as logic: next = left XOR (centre OR right).
from a single cell
Start with one cell on and run it forward. The left side settles into regular diagonal stripes; the right side never does.
█
███
██ █
██ ████
██ █ █
██ ████ ███
██ █ █ █
██ ████ ██████
██ █ ███ █
██ ████ ██ █ ███
██ █ █ ████ ██ █
██ ████ ██ █ █ ████
██ █ ███ ██ ██ █ █
██ ████ ██ ███ ███ ██ ███
██ █ █ ███ █ ███ █ █
██ ████ ██ █ █ █████ ███████
why it matters
- The centre column passes many standard statistical tests for randomness, despite being fully deterministic.
- It's a clean example of simple local rules producing complex global behaviour.
- The same pattern shows up on the shell of the Conus textile sea snail.
open questions
- How short can the rule's period be on a finite ring of n cells?
- Which cheap tests does the centre column fail first, if any?