Section 1
A deterministic rule that looks random
Rule 30 reads a three-cell neighbourhood and writes one output bit. The rule table: 111→0, 110→0, 101→0, 100→1, 011→1, 010→1, 001→1, 000→0 — those output bits, read right to left, are 00011110 = 30. Start with one black cell on an infinite white tape and apply this rule repeatedly.
The pattern that grows is a triangle. The left edge follows a ragged coastline, the right edge slopes uniformly at one cell per step (the maximum speed in this 1D system), and the interior is full of irregular structure that looks like static.
Focus on the centre column — the bit directly above the initial seed cell at each step. The first 100 bits:
No visual period. The sequence starts 1 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 0 0 1 … and keeps going with no obvious pattern. A good pseudorandom number generator converts a small seed into a long sequence that no feasible statistical test can distinguish from a uniformly random sequence. Rule 30's centre column passes the first check — eyeballing it reveals nothing.
Section 2
Extracting random numbers from the centre column
Run Rule 30 for N steps. Read the centre column. The resulting bit string is your random output. Below: pick how many bits to extract per draw and advance through the sequence with Next.
Centre-column extractor
Each draw advances the position in the pre-computed sequence. The centre column is computed from the infinite-tape evolution — a tape wide enough that the light cone never reaches the edge within the steps shown. Values repeat only when the position wraps around (after 10,001 bits).
Rule 30 evolved for 150 steps from a single black cell. Centre column highlighted in blue.
Section 3
Statistical tests pass
The empirical tests below were computed on the first 10,000 bits of the single-cell-seed centre column. The three tests shown are drawn from NIST Special Publication 800-22, the standard battery for evaluating pseudorandom number generators.
| Test | What it checks | Result (n = 10,000) | Threshold | Verdict |
|---|---|---|---|---|
| Monobit | Are 0s and 1s equally probable? | — | |Z| < 1.96 for α = 0.05 | — |
| Runs | Are runs of consecutive bits the right length? | — | |Z| < 1.96 for α = 0.05 | — |
| Lag-1 autocorrelation | Is each bit independent of the one before it? | — | |r| ≈ 0 for a random sequence | — |
The monobit Z-statistic measures how far the proportion of 1s deviates from 0.5. The runs test measures whether consecutive same-value blocks are too short or too long. Lag-1 autocorrelation measures whether each bit predicts the next. A truly random sequence scores near zero on all three; Rule 30's centre column does.
Section 4
Where Rule 30 fails as a cryptographic PRNG
Passing statistical tests is necessary for a cryptographic PRNG (CSPRNG) but not sufficient. A CSPRNG must also be computationally unpredictable: given a long output sequence, no computationally bounded adversary can predict the next bit with probability better than 1/2. Rule 30 does not meet this bar.
Right diagonal is trivially predictable
The rightmost cell at step t depends only on the rightmost cell at step t−1. The right diagonal propagates at the maximum speed — one cell per step — and its value is determined by a single bit of the seed, not the full interior. An adversary who sees a window of output can immediately fix a portion of the state.
Meier & Staffelbach (1991): seed recovery from output
Meier and Staffelbach showed that the seed of a finite-tape Rule 30 PRNG can be recovered from its output using a known-plaintext-style attack — much less output than a naive exhaustive search would require. The attack exploits the linear structure of the right-diagonal propagation. Rule 30 is not a CSPRNG under this result.
Column correlations
Different columns of the Rule 30 evolution are correlated. Taking a single column — even the centre — and another column a fixed distance away, the joint distribution is not uniform. Vuillemin and others identified these correlations in the late 1980s. Using only the centre column mitigates but does not eliminate them.
Non-surjective, so periodic on finite tapes
Rule 30 is not surjective (see Gardens of Eden). On any finite cyclic tape, every orbit is eventually periodic — the state space is finite and the rule is deterministic. Cycle lengths can be large, but they exist. The centre column from a single-cell seed on an infinite tape avoids this, but practical finite implementations must account for it.
Section 5
Where Rule 30 sits in the PRNG landscape
Many algorithms make random-looking numbers. They occupy a spectrum from fast-and-weak to slow-and-strong.
Rule 30 alongside Mersenne Twister, xoshiro256++, and ChaCha20.read in layers
Start here Some PRNGs are fast and fine for games and simulations. Some are slow and strong enough for passwords and keys. Rule 30 sits in the fast-and-not-cryptographic tier — useful in many contexts, disqualified from security-critical ones.
High school Mersenne Twister (MT19937) is the standard non-cryptographic PRNG — Python's random module, many scientific libraries. ChaCha20 is the cryptographic standard, used in TLS and operating system entropy pools. Linear congruential generators (xn+1 = axn + b mod m) are the textbook bad option — fast but easily cracked. Rule 30 is broadly similar in tier to Mersenne Twister: good statistics, not cryptographic, with a simpler and more transparent construction.
Undergrad
| Generator | State size | Period | TestU01 BigCrush | Cryptographic | Notes |
|---|---|---|---|---|---|
| Rule 30 (∞ tape) |
∞ (or tape width) | Unknown / open | Not formally tested | No | Seed recovery attacks known (Meier & Staffelbach 1991) |
| LCG (textbook) |
32–64 bits | 232–264 | Fails many | No | Predict output trivially from a few values |
| Mersenne Twister (MT19937) |
19,937 bits | 219937 − 1 | Fails some (linear complexity) | No | State recoverable from 624 consecutive outputs |
| xoshiro256++ | 256 bits | 2256 − 1 | Passes | No | Modern recommendation for non-crypto; very fast |
| ChaCha20 | 256-bit key + nonce | 264 per key/nonce | Passes | Yes | IETF RFC 7539; used in TLS 1.3, Linux getrandom() |
Going deeper The TestU01 framework (L'Ecuyer & Simard, 2007) provides the BigCrush battery — 106 statistical tests, the most demanding published suite. Even Mersenne Twister fails three BigCrush tests (the linear complexity test, because MT's output satisfies a known linear recurrence over 𝔽2). Rule 30's centre column has not been formally submitted to TestU01 BigCrush in published literature; Wolfram's analyses predate the framework. xoshiro256++ (Blackman & Vigna, 2019) passes all BigCrush tests and is the current recommendation for non-cryptographic use in scientific computing. For cryptographic work, ChaCha20 (Bernstein, 2008) is the IETF standard and is provably a PRF under a well-studied hardness assumption. Rule 30 sits between LCG and MT in the historical record — more transparent than MT, arguably simpler to analyse, but less tested and with known structural weaknesses.
Section 6
When to use Rule 30
- ✅ Educational demonstrations of emergent randomness. Rule 30 is the canonical Class III rule — the clearest example of deterministic local rules generating apparently random global output. Show it.
- ✅ Self-contained Monte Carlo generators. For simulations where you want a transparent, audit-friendly PRNG with no external library dependency, the finite-tape Rule 30 construction is defensible — as long as no adversary picks inputs.
- ✅ Procedural content and visualizations. Texture generation, terrain noise, game seeds — Rule 30's visual character is distinctive and statistically sound for these purposes.
- ✅ Studying the boundary between determinism and randomness. The open conjecture, the prize problems, the contested column correlations — Rule 30 is a productive research object.
-
❌
Cryptographic key generation. Seed recovery attacks disqualify it. Use
os.urandom()or a CSPRNG. - ❌ Nonces for security protocols. An adversary who observes output can recover internal state. Never use Rule 30 where output confidentiality is required.
- ❌ Any context where the adversary selects inputs. The structural weaknesses of finite-tape Rule 30 are exploitable when an attacker controls the seed or can observe multiple draws.
Section 7
Rule 30 and the edge-of-chaos story
Rule 30 is the canonical Class III rule — the one Wolfram returns to whenever he wants to demonstrate that simple deterministic rules can produce behaviour indistinguishable from randomness. The PRNG application is one downstream consequence of that property, alongside the open prize problems, the column correlation debates, and the broader question of whether complexity can be computed cheaply.
The four Wolfram classes partition rule space by long-run behaviour: collapse, periodicity, chaos, localized interaction. Rule 30 lands firmly in Class III — not because it is random (it is perfectly deterministic), but because no practical test has yet found the pattern. Whether that reflects deep combinatorial richness or merely the limits of the tests applied is, as of late 2025, still open.
Explore the full rule space on the Elementary CA Zoo home page — every rule, every class, and the Langton λ lens that locates the edge between order and chaos.