Commissioned for this museum · after Stephen Wolfram's elementary cellular automata, 1983
Eight Rules Is Enough
JavaScript·1983·27 lines·859 bytes
/*
* Rule 110. A line of cells, each alive or dead. To make the next line,
* look at each cell with its two neighbours -- eight possible arrangements
* -- and read off what to do from the bits of the number 110.
*
* That is the whole of it, and it is enough to compute anything at all.
*/
const WIDTH = 64;
const GENERATIONS = 32;
const RULE = 110;
let cells = Array(WIDTH).fill(0);
cells[WIDTH - 1] = 1; // one living cell, at the right-hand end
for (let gen = 0; gen < GENERATIONS; gen++) {
console.log(cells.map((c) => (c ? "#" : " ")).join(""));
cells = cells.map((_, i) => {
const left = cells[(i - 1 + WIDTH) % WIDTH];
const self = cells[i];
const right = cells[(i + 1) % WIDTH];
// The three cells make a number from 0 to 7. That is which bit to read.
return (RULE >> ((left << 2) | (self << 1) | right)) & 1;
});
}Curator’s note
A row of cells, each alive or dead. To work out the next row, look at every cell together with the two beside it. Three cells, each one of two states, is eight possible arrangements — and all this program has to say is what to do in each of the eight. Write those eight answers out as ones and zeros and you have a number between 0 and 255. This one is 110.
That is the entire rule. RULE >> ((left << 2) | (self << 1) | right) & 1 reads the arrangement as a number from 0 to 7 and pulls out that bit. There is no other logic anywhere, and there is no state beyond the row itself.
Start with a single living cell and it produces the picture above: triangles inside triangles, never settling into a repeat and never dissolving into noise. Most of the two hundred and fifty-six rules do one or the other within a few rows.
Matthew Cook proved in 2004 that this particular one is Turing complete. Not "resembles computation" — complete, in the sense that anything any computer can calculate can be arranged as a starting row of these cells, with the answer read off further down. A rule small enough to fit in a byte, with no memory, no instructions and no way to address anything, is exactly as powerful as the machine it is running on.
Set beside recursion built out of nothing but functions, it is the same surprise from the other end.