17. Elementary Cellular Automaton
The biology wing of the university carried its own peculiar scent— sharp alcohol from glass flasks, mingled with the faint, sour tang of specimens suspended in cloudy jars. Lanterns flickered against cabinets lined with pinned beetles, pressed plants, and fish skins stretched brittle as parchment.
At the far end of a long oak table stood Dr. Kettunen, a Finnish professor newly arrived in Dorpat. His beard was trimmed neatly, his eyes bright with that particular fever of discovery. Before him lay shallow glass dishes, their surfaces veined with pale filaments that branched like frost upon a window.
„They grow strangely,“ he said, gesturing to the plates. „Not in smooth circles, as one might expect, but in uneven branching forms, spreading outward like frost upon glass. I cannot decide if it is order or accident. Tell me, Mihkel—you study mathematics. Could numbers explain this? Or is it only nature’s whim?“
Johann leaned over the dishes, wrinkling his nose. „They look like little armies—marching, retreating, marching again. If they’re soldiers, they’ve drunk too much beer, for their lines wander!“
Mihkel did not smile. His gaze lingered on the branching filaments, and he felt a thrill beneath his ribs. Not disorder—rules. Each cluster obeyed some hidden pattern, depending only on its nearest neighbors. Growth was not mystery; it was instruction.
„Perhaps I can try something,“ he murmured, already pulling a folded strip of tape from his coat pocket.
That night, in the secrecy of his workshop, he copied the dish into symbols: a row of living cells marked as bars, emptiness as noughts. He set the strip into the Logic Mill.
The gears turned, clicking in steady rhythm. The tape advanced. A new row formed—then another, and another—branching shapes unfurling across paper like a frozen echo of the colonies in Kettunen’s dishes.
On the input tape, you’ll receive a row of cells:
+
means the cell is alive-
means the cell is empty
Your task is to simulate the elementary cellular automaton with Rule 22 for exactly 5 steps.
At each step, the next state of a cell is determined by its three-cell neighborhood (the cell itself and its left and right neighbors).
Rule 22
is defined by the following transitions:
A cell becomes +
in the next step if exactly one of the these three cells (left, itself, right) is alive. Otherwise it becomes -
.
The tape should grow as needed to accommodate new cells.
Functionally, -
behaves the same as the blank _
of the Logic Mill (both mean “no cell”).
The difference is visibility:
blanks _
can stretch arbitrarily and make it impossible to count distances between cells,
while -
is always written explicitly as part of the row.
This way, every row is fully specified using only +
(alive) and -
(empty),
so you can always traverse and measure the tape unambiguously. The only exception is the input tape -
.
For example, if the input tape is +
then after 5 steps, the output tape should be: +++-----+++
.
Here is the full evolution step by step:
-
+
-
+++
-
+---+
-
+++-+++
-
+-------+
+++-----+++