RULE 110
A one-dimensional cellular automaton. Eight entries in a lookup table, and enough to compute anything.
THIS PAGE MOVES
It is a live automaton. Rows of cells scroll steadily up the screen for as long as it runs. It does not flash. If steady motion affects you, go back.
A one-dimensional cellular automaton. Eight entries in a lookup table, and enough to compute anything.
GENERATION 0
In Drawn mode, click or drag across the seed row above the tape to toggle cells. With the row focused, the arrow keys move, Space toggles and Enter runs.
The table
Each tile is a cell with its two neighbours above the cell it becomes. Read the bottom row as a binary number, 01101110, and it is 110. That is the whole rule, and it is fixed here.
Rule 110 is a one-dimensional cellular automaton. There is a row of cells, each on or off, and a clock. On every tick each cell looks at itself and its two neighbours, finds that three-cell pattern in a fixed table of eight entries, and becomes whatever the table says. The table is the whole rule, and its eight outputs read as a binary number are where the name comes from. There is no memory beyond the previous row and no randomness once the first row is set.
A table that small should not be able to do much, and yet it can do everything a computer can. Matthew Cook proved it in 2004. Run the rule from a random row and the tape settles into a repeating background crossed by moving structures called gliders. Each glider is a signal. When two of them meet, the collision either destroys them, passes them through or emits new ones, and those outcomes can be arranged to act as logic. Wire enough of them together and the rows become a program, running one line at a time, with nothing but this table to drive it.