Chips from the lathe

This first post of 2020 just shows some videos of mini projects from the past 3 months.

Here’s an improvement (I hope) of my previous attempt to simulate fire on a small TFT display. I’ve added a glowing particles effect, did some parameter fine tuning and changed the color palette. The simulated area forms a layer over a jpg image, read from SD card.

Alas, my phone’s camera misses most of the improvements…


The next video shows the tesselation process of a 2D area according to the Majority Voting principle. In the initial state, every pixel randomly gets one out of three* possible colors. Then, in each (discrete and simultaneous) next step, every pixel takes the color of the majority of its ‘neighbours’. It’s no surprise that the chosen definition of neighborhood has great influence on this self-organizing process and its final state.

* The classic example uses 2 colors, but I chose to have 3 for a more fashionable (?) look.


Finally, meet Perrier Loop, the most complex Self-replicating Cellular Automaton that I managed to squeeze into my cellular automata framework for ESP32 (so far).  Grid cells can be in one out of 64 states (colors). Their state transitions are governed by 637 rules that use 16 variables (placeholders for up to 7 states, so the real number of rules is much larger). Each cell complies to this exact same set of rules to determine its next state, based on its current state and that of its 4 orthogonal neighbours (Von Neumann neighborhood).

In mathematical terminology, Perrier Loop is a self-replicating universal Turing machine.

And it looks so simple on this 320×240 display….

Self-replicating Cellular Automata

Studying John von 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 more copies of the initial pattern… etc. etc.

I guessed that Von Neumann’s universal automaton, with its 29 cell states and large set of rules, could be well out of ESP32’s league. Fortunately there are some famous (be it less universal) simplifications, so I started with the simplest one 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 start patterns and rules from Golly. It runs on ESP32 WROVER modules, using 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.

As a proof of concept for the new framework, I initialised it with the specific data for Langton’s Loop, an automaton similar to Chou-Reggia-2, but with more rules. Everything worked fine, as did two slightly more complicated automata that have variables in their Golly rules, as well as substantially more states: Evoloop-finite and Perrier Loop.

Now that I have it up and running, my CA framework for ESP32 WROVER modules reduces simulation of most 2D cellular automata to feeding it with their specific data: states, transition rules (with or without variables), neighborhood (Moore or Von Neumann) and rule symmetry, all imported from Golly.

[ 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 (slow version)

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).

(See this post for an implementation of Perrier Loop inside the same framework)

* 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 [sic], 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-symbol 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-symbol 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 2-symbol 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.



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.