Self-replicating Cellular Automata

Studying John van Neumann’s self-reproducing universal constructor* reminded me of some unfinished business in my earlier Cellular Automata (CA) projects. Always looking for coding challenges, I wondered if I could write a sketch for simulating self-reproducing CA loops that would fit inside an ESP32.

The general idea is to have a 2-dimensional grid of cells, each of which can be in one out of n states. These cells periodically change their states simultaneously, according to a set of rules. Each cell complies with the same set of rules, which lets it calculate its new state based on its current state and that of its direct neighbours. The way this ‘organism’ will evolve also depends on its initial pattern. A self-reproducing CA is a combination of states, rules and initial pattern that will continuously produce copies of the initial pattern, that will produce copies of the initial pattern… etc. etc.

Surely, von Neumann’s universal automaton, with its 29 possible cell states and inevitably large set of rules, would be out of ESP32’s league. Fortunately there are some famous (be it less universal) simplifications, so I started with the simplest I could find: Chou-Reggia-2.

ESP32 WROVER simulating Chou-Reggia-2 on a 320×240 display (1-pixel per cell)

The video shows the indefatigable CA at work, producing ever more copies of the initial pattern (just 5 cells). It mimics a much sought after form of life: old cells don’t die…

They’re just like kids, they grow up so fast ūüėČ

 

In order to squeeze my Chou-Reggia-2 algorithm into the ESP32, I had to come up with some new programming- and storage techniques for cellular automata. I ended up writing a framework for CA sketches, that can import patterns and rules from Golly. It runs on ESP32 WROVER modules, using its PSRAM for storing a double display/states buffer. The two cores of the ESP32 cooperatively calculate a new grid state based on the current one.

Once my framework was ready for use, I could easily apply it to a slightly more complicated self-replicating cellular automaton: Langton’s Loop. It’s basically the same sketch that produced Chou-Reggia-2, only the rules and initial pattern are different.

[ After further optimization, my CA sketches run 5x faster than what is shown in the videos! ]

Close up of Langton’s Loop on an ESP32-driven 320×240 TFT display

Because every ‘cell’ is represented by a single pixel on a small 2.4″ display, I had to zoom in on the pattern in order to show the difference between ‘living’ and ‘dead’ cells (Langton’s ‘organism’ grows like coral: inner cells die, but their cell-walls are preserved).

 

* Von Neumann’s abstract and purely logical reasoning about self-replication eventually helped biologists to understand how (real) cells manage to make exact copies of themselves.

 

 

Busy Beaver

Today I discovered that Langton’s Ant is not the only Turing machine that’s nicknamed after an animal. There’s also the Busy Beaver, invented by Tibor Rad√≥. Despite its chaotic behaviour and unpredictable* outcome, the machine itself is extremely simple and can easily be simulated on a TFT display by an Arduino.

[video shows the final 3 steps of the busiest of all 4-state, 2-color beavers]

The beaver’s workflow is: read cell color -> lookup instructions for current [cell color/system state] combination¬† -> adjust state -> adjust cell color -> move head -> start again, unless state equals X.

In general, the components of a Turing machine, as described by Alan Turing in 1936, are:

  • an infinite tape, divided into an infinite number of cells, each of which can contain a symbol from a finite set of characters, including a ‘blank’ (the alfabet)
  • a head that can read and optionally change the content of a cell, as well as optionally move to the next or previous cell on tape
  • a finite set of n possible states that the system can be in, plus at least one additional state that marks the end of the process
  • a finite set of instructions that, based on the current state and the currently read symbol, decides about: (1) whether the symbol will be erased, overwritten or left as is; (2) whether the head will move one cell (left or right), or keeps it position over the tape; (3) what the next system state will beome.

The alfabet in my sketch consists of 0 (‘blank’, white cell) and 1 (blue cell). The four system states are represented by A, B, C and D. Note that this 4-state machine has a 5th state X, the exit state. A beaver must have exactly one (1) exit state. Also, all of its instructions must include movement of the head.

The algorithm could (in theory) simulate any 4-state, 2-color Turing machine on a 480×320 TFT diplay, but my sketch is initialized for simulating the ‘busiest’ of all possible 25,600,000,000** 4-state Busy Beavers: the one that stops with the maximum numbers of ‘1‘s on tape (13, after 107 steps). Luckily, it will not run out of Arduino’s limited virtual tape during the process (‘real’ Turing machines have an infinite tape, that’s why they can only exist as mathematical models).

It would have been impossible to simulate the busiest 5-state beaver, since several super computers and my Arduino ūüėČ are still searching for it. So far, ‘we’ have found one that has 4098 ‘1‘s on tape when it stops.

*¬†Turing proved that no single algorithm can exist, that’s capable of predicting the outcome of all possible beavers. Apart from the trivial ones, you’ll simply have to run them…

**In a Busy Beaver Turing machine, the head will always be moved. That reduces the number of¬†possible [color, state, move] instruction triplets for a¬†4-state, 2-color beaver to 2x5x2 = 20 (remember the 5th X state). We have to provide instruction triplets to 4×2 = 8 state/color combinations (state X doesn’t need one), so there are 208 different 4-state, 2-color Busy Beavers.

 

 

Game of Life (revisited)

In an earlier Game of Life post, I had my Arduino Uno simulate ‘Life’ on a modest 64×32 cell grid. After receiving the ESP8266 WiFi Color Display Kit from Squix (see previous post), I discovered Bodmer’s TFT_eSPI library, highly optimized for its 320×240 ili9341 display in combination with esp8266 based boards. It even comes with a Game of Life example sketch!

Bodmer’s example would clearly run out of memory for 1-pixel cell grids, because it stores every single 1-bit cell state in its own 8-bit integer! So I modified the sketch, now storing eight consecutive cell states in one byte, like I had already been forced to do in my¬†earlier Game of Life sketch.

The small price for this storage expansion (by a factor of 8!) is speed, but the library is so fast that the result is still beyond my expectation. The video shows that a 320×240 grid can easily handle patterns as large as the famous Line puffer. (After I made the video, I discovered that the pattern moves noticeably faster if the esp8266 ‘s clock speed is set to 160MHz, and even faster on an ESP32.)

I wrote a small application that converts RLE* files to grid initialization commands. These can be used in the initGrid() function of the sketch. More pattern files will be added.

*Run Length Encoded files for many GoL patterns are freely available on Internet.

 

Ant-ology

Following up on cellular automata after my previous Game of Life project, I sort of rediscovered Langton’s Ant. It’s another example of extremely simple rules, leading to some intriguing arm wrestling between order, complexity and chaos.

Langton’s ant lives on an infinite grid of squares. Every next move it makes is determined by these simple rules:

  • If it’s on a black square, it turns left and moves to the next square in that direction
  • If it’s on a white square, it turns right and moves to the next square in that direction
  • The square it moves from reverses color

The grid size needed for properly simulating the process made me use a Wemos D1 R2 board instead of my faithful Arduino Uno. This first sketch is as simple as the ant’s rules. It maps a 106×160 cell grid on a 320×480 pixel display (3×3 pixel cells).

Infinity of the grid is simulated by ‘folding’ it in both dimensions (toroid shape), so the famous ‘highway’ will lead the ant back to its self created chaos, from where it will try to build new highways.

Meanwhile, I’ve developed some¬†multi-ant ideas, so more sketches may follow.

 

(For this video, I started with an all black grid and removed the delay at the end of the loop() function in order to turbo-boost the ant)

 

 

Game of Life

Conway’s Game of Life is a¬†nice demonstration of how simple rules can generate complex structures.¬†It’s also a great introduction to the fascinating world of Cellular Automata.

see also: Game of life (revisited)

The¬†Game of Life, or simply ‘Life’, takes place on¬†an infinite 2-dimensional grid, populated by cells. In every next generation, the new state of each cell depends on the current¬†state of¬†the¬†eight¬†surrounding cells¬†(its¬†‘Moore neighborhood’), following this¬†simple set of rules:

  1. Living cells die if they have less than 2, or more than 3 living neighbors.
  2. Dead cells are brought to life if they have exactly 3 living neighbors.

The initial state of the system completely determines the further process, in which order and chaos can easily get involved in a continuous arm wrestling game.

Mathematicians and Life enthusiasts have found some incredible patterns like the Gosper Glider Gun, the Puffer Train and the Breeder. This video starts on a grid with ~25% of the cells ‘alive’ (randomly chosen).

The main challenge of running¬†a simulation of¬†‘Life’¬†on an Arduino Uno¬†lies in¬†its limited RAM memory size (2K only!). Since the rules are applied to all cells simultaneously,¬†we need to store both the old and the new state of the grid.

First I used¬†Booleans to store cell states, but¬†since every boolean claims a full byte (8 bits),¬†the largest grid¬†that Uno could handle was about¬†17×17 in size. The trick was to use¬†bytes instead, where each byte¬†now holds¬†the state of¬†eight consecutive LEDs in¬†one of¬†the¬†rows, thus replacing¬†eight boolean bytes!

With this new approach, Arduino Uno can¬†simulate a 64×32 cell grid on my 128×64 pixels monochrome I2C Oled display (using 89% of Uno’s precious RAM). In that configuration, cells¬†are represented by¬†2×2 LED squares, lit¬†when alive¬†and¬†unlit when dead.

Note that you can define the initial state of the grid within the seed() function of the sketch. I used a simple border rule for the video: neighbor cells outside the grid are considered dead.