Elementary cellular automata · Wolfram

How complex can the simplest possible computation get? A 1-D row of cells, each updated from only itself and its two neighbours — can such a trivial rule make order, fractals, randomness, or universal computation?

▶ Run the simulationSee the measured result

Units: dimensionless (fractal dimension D = log₂3 of the Sierpiński gasket / rule-90 spacetime; secondary knowns: rule 254 solid triangle D = 2 exact, rule 30 centre-column density → 1/2)

How the lab tests it

A cell's next state is a function of (left, self, right) — 8 inputs, so the rule is one of just 256 bytes (Wolfram). Stack the rows into a spacetime picture and measure what three rules do: rule 90's fractal dimension by mass-scaling (live cells in L rows ∝ L^D), rule 30's centre-column density and block-entropy (is it random?), and rule 110's behaviour.

What it checks

the whole Wolfram zoo from 8 bits: rule 90 paints the SIERPIŃSKI triangle with fractal dimension D=log₂3≈1.585 (measured to the digit, since the live-cell count in 2^k rows is exactly 3^k); rule 30 manufactures RANDOMNESS — its centre column has density ≈½ and per-bit entropy ≈1.0, indistinguishable from a coin (Wolfram used it as a PRNG); rule 110 is COMPLEX — gliders on a textured background, and provably Turing-complete (Cook 2004). Determinism alone yields order, fractals, chaos, and computation

Elementary cellular automaton calculator (the 8-bit rule table, its mirror and complement twins, the 88 classes, rule 90's exact 3^k mass and the log₂3 dimension)

Two hundred and fifty-six programs fit in a byte, and one of them draws the Sierpiński triangle. An elementary cellular automaton is the smallest interesting thing in computing: a row of cells, each 0 or 1, each looking only at itself and its two neighbours, all updating together. Eight possible neighbourhoods, one output bit each, so eight bits — the rule number — is the entire program. Rule 90 is the byte 01011010, and what it says is 'become the XOR of your two neighbours'. Start it from a single live cell and it paints Pascal's triangle modulo 2, whose live cells are the Sierpiński gasket, whose dimension is not a whole number. This page takes the rule number you type and assembles all of that from it. It decodes the byte into its eight-row lookup table and tells you whether the rule is additive over GF(2) — tested on all eight rows rather than inferred from three; it builds the rule's mirror and complement twins by permuting the byte's own bits, and counts the 88 inequivalent elementary rules by walking those two operations over all 256; and it grows the rule from a single seed and measures the dimension of what grows, using the identical estimator the simulation above uses. For rule 90 it also computes the answer a second way, with no generation at all: the live-cell count of row n is 2 raised to the number of 1-bits in n (Kummer 1852, Lucas 1878), so the mass of the first 2^k rows is exactly 3^k, and the dimension is ln 3 / ln 2 with no fit and no free constant — the two routes are printed side by side so you can see them agree. Three of the things it computes are not decoration. First, the lacunarity: at row counts that are not powers of two the mass falls below the pure power law by up to 19%, which is why a dense-L slope reads about 0.35% low, and this page reproduces the laboratory's seven-window ensemble — mean, standard error and worst window — from integer arithmetic alone, predicting a disclosed bias instead of excusing it. Second, the depth test that separates a fractal from a filling pattern: rule 90's exponent is log₂3 at every depth, while the rivals' are not exponents at all but readings that climb with depth toward 2 — rule 250 reads 1.939 at 512 rows and 1.961 at 4096, rule 30 reads 1.884 and then 1.923. Third, the grid: a single seed spreads at most one cell per step, so a run of g steps is boundary-free on a width of 2g + 3 and no wider, which is the number the simulation above is sized by.