Systems
Rule 30: one line of logic that never settles
Rule 30 fits in one formula, left XOR (centre OR right), yet from a single black cell it grows a pattern whose right side looks like noise. Why it is lopsided, how its centre column became a random-number generator, why that is not cryptography, and the open problems still attached to it.
Rule 30 is completely determined and still unpredictable in practice. Knowing a rule exactly is not the same as knowing where it goes.
The whole rule in one line
Like every elementary cellular automaton, Rule 30 decides each new cell from three cells above it: left, centre, right. In the standard order the answers are 111 to 0, 110 to 0, 101 to 0, 100 to 1, 011 to 1, 010 to 1, 001 to 1, and 000 to 0. Read the outputs as one binary number, 00011110, and you get 30. How that numbering works for all 256 rules is in 256 rules, one byte each.
Stephen Wolfram introduced Rule 30 in 1983. The table collapses into one formula: the new cell is the left cell XOR (the centre cell OR the right cell). Check any row: for 100 the centre and right are both 0, so the result is the left cell, 1; for 101 the right is 1, so the result is 1 XOR 1, which is 0.
Neat on the left, noise on the right
Start from a single black cell and the pattern grows as a triangle. Its left edge quickly settles into regular diagonal stripes. Its right side never settles at all: triangles of every size open and close with no visible order.
The formula explains the lopsidedness. Because the new cell is the left cell XOR something, changing the left cell always changes the result, so every difference keeps travelling to the right and never fades. The rule is not mirror-symmetric; its mirror image is Rule 86, which is chaotic on the left instead.
A column of coin flips
Now read only the centre cell, one row at a time. The sequence starts 1101110011000101 and keeps going without any visible pattern. Over the first 4,000 rows, about half the cells are black, the four possible pairs 00, 01, 10 and 11 each appear about a quarter of the time, and no short repeating cycle shows up.
Wolfram proposed exactly this use in his 1986 paper on random sequence generation, and Mathematica used Rule 30 to generate random integers. A rule with no randomness in it at all produces a column that passes for coin flips in many statistical tests. That is the strange part: the disorder is not added from outside, it is computed.
Random-looking is not secret
Everything about Rule 30 is determined. Give the same starting row and you get the same picture every time, which is what makes it pseudo-random rather than random. That is fine for simulations, games and sampling, where you want repeatable noise.
Cryptography asks for more. Wolfram proposed a Rule 30 stream cipher in 1985, and in 1991 Willi Meier and Othmar Staffelbach published an analysis showing that such generators are weaker than they look. Passing statistical tests means an observer cannot easily see a pattern; it does not mean an attacker cannot find one.
Three questions still open
Wolfram calls this kind of behaviour computational irreducibility: the only general way to know row one million is to compute the rows before it. For Rule 30 nobody has proved even the basic facts. In October 2019 he offered three prizes of $10,000 each: does the centre column never become periodic, do black and white occur equally often on average, and does computing the nth cell really take at least on the order of n steps?
A rule that fits in one line still has questions about it that nobody can answer. Nature seems to run something similar; the shell of the cone snail Conus textile carries a pattern that looks much like Rule 30. The quickest way to feel the difference between knowing a rule and knowing its future is to type 30 into the lab and watch.