One Rule, and the Whole Row Falls

Stand a few thousand dominoes on a table and you have made something strange: a machine where every tile knows exactly one thing, which is whether the tile beside it has fallen. Nobody choreographs the middle of the run. You set an initial row, you tip the first one, and the pattern that travels down the table is a consequence, not a plan. That is precisely the bargain of an elementary cellular automaton — the toy Stephen Wolfram spent the mid-1980s cataloguing, a strip of cells where each new cell looks only at itself and its two neighbours and consults a tiny lookup table to decide: up or down.

There are only eight possible neighbourhoods for three binary cells, so a rule is just eight yes/no answers — one byte, 0 to 255. Here is the run for rule 90, which I like because it topples into a Sierpinski triangle from a single lit cell:

#                   
                  # #                  
                 #   #                 
                # # # #                
               #       #               
              # #     # #              

The rule number is the program. Reading bit pattern out of it is the whole engine:

let width = 39, gens = 20, rule = 90
var row = [Int](repeating: 0, count: width)
row[width / 2] = 1
for _ in 0..<gens {
    print(String(row.map { $0 == 1 ? "#" : " " }))
    var next = row
    for i in 0..<width {
        let l = row[(i - 1 + width) % width]
        let r = row[(i + 1) % width]
        next[i] = (rule >> ((l << 2) | (row[i] << 1) | r)) & 1
    }
    row = next
}

Perl needs less ceremony for the wraparound, because its % stays non-negative on a positive divisor, so -1 % 39 is already 38 — no + width fudge:

my ($width, $gens, $rule) = (39, 20, 90);
my @row = (0) x $width;
$row[int($width / 2)] = 1;
for (1 .. $gens) {
    print map({ $_ ? '#' : ' ' } @row), "\n";
    my @next;
    for my $i (0 .. $width - 1) {
        my $p = ($row[($i - 1) % $width] << 2)
              | ($row[$i]              << 1)
              |  $row[($i + 1) % $width];
        $next[$i] = ($rule >> $p) & 1;
    }
    @row = @next;
}

Both print the identical triangle. Change one number — rule = 110 — and the same six lines stop drawing fractals and start doing arithmetic: rule 110 is Turing-complete, which is the formal way of saying a properly arranged chain reaction can compute anything at all. That is not a metaphor I invented for the dominoes. People genuinely build AND and OR out of merging and blocking domino lines, and Matt Parker crowd-sourced a domino adder that carries as it collapses. Same deal on my table tonight: local click, local click, and a shape I did not draw arriving at the far edge.