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 it’s 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.