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.

 

 

Buddhabrot – the last fractal?

Writing sketches for posts in the Fractals category of this blog made me realize that for many fractals (e.g. Mandelbrot, Julia, Newton etc.), visual appeal depends to a large extend on color mapping. In other words: mathematics may have blessed these fractals with a potentially beautiful complexity, but it still takes a programmer to visualize it as such.

Another thought that crossed my mind was whether the (perceived) infinite complexity of fractals couldn’t be just revealing the incompleteness of the mathematical system that produces and observes them (in which case we should name them Gödel fractals).

The above observations became manifest again when I was looking for a way to color the inside of the Mandelbrot set, that’s usually left uncolored. After a couple of very unappealing attemps, I discovered someone’s method for producing the so called Buddhabrot fractal.

 

However, as you can see, the result on my small 480×320 pixel display doesn’t even come close to some of the beautiful images that pop up in Google. Actually, it looks more like one of Marie Curie’s early X-ray images. On the other hand, I suspect that many beautiful realizations of the Buddhabrot fractal have been enhanced with the same post-processing techniques that are used for beautifying pictures of galaxies and nebulae. That feels a bit like cheating to me, because I could probably make my Buddhabrot look like Donald Trump that way… (would that still be called beautifying?)

 

Now that this somewhat demystifying idea of ‘artificial beauty’ has tempered my facination for fractals a bit, it’s time to return to the challenge of creating fast and memory-friendly algorithms for IFS-generated shapes, like space filling curves.

ESP32 – mixed feelings

 My ESP32 boards: LOLIN32 Pro, LOLIN32 Lite, LOLIN D32 and LOLIN D32 PRO 

After a false start with ESP32 (my LOLIN32 Pro had an overheating CP2102 chip*), I’m gradually becoming more familiar with ESP8266’s big brother. However, experience with 4 different boards (all with rev. 1 chips) still leaves me with mixed feelings. My personal balance so far:

Pros:

  • The specs and features are impressive, especially given its low price
  • Control over its two cores via FreeRTOS works great
  • It has a fair number of GPIOs (unlike the ESP8266)
  • Sketches run very fast (if they run…). Great for my fractal sketches!
  • No longer needs yield() commands to prevent it from crashing

Cons:

  • It’s extremely sensitive to solderless wiring (probably because of its high bus speeds)
  • The 4 different boards I tried all had problems feeding power-hungry peripherals
  • I’m experiencing some unexplicable issues, especially when driving TFT displays

Tips for troubleshooting:

  • Provide your ESP32 with enough power. Some USB outlets will not deliver enough juice, especially not through low quality USB cables
  • Use an external power supply for power-hungry connected devices, otherwise (at least) SPI may become unstable
  • Consider using contact spray for unstable solderless projects
  • Don’t use heavily used breadboards
  • Never use a hammer (though working with ESP32 can be frustrating…)

So will my ESP8266 boards start gathering dust from now on? Certainly not before I manage to run a turbo version of my beloved What’s Up sketch on the ESP32. I just can’t wait to watch those plane icons slide more smoothly over the map. Bodmer’s TFT_eSPI library offers enough speed for that, but I keep having issues with it when used in the What’s Up sketch on ESP32.

* The issue was reportedly caused by a design flaw. After I had received a LOLIN32 Lite for replacement, I discovered that using a longer USB cable (2+ meter) fixed the problem!

Tic-Tac-Toe trainer

Turning an Arduino into an invincible Tic-Tac-Toe master is hardly a challenge, but I wrote a sketch for it anyway because I need it for a more ambitious project. For that project, I also had to design a couple of flawed Tic-Tac-Toe strategies with different levels of ‘vincibility’.

Next, I’ll have two Arduinos play matches against each other and analyse the outcome for all combinations of competing strategies. Now the strategies can be ordered based on their success rate.

The final goal is to make the Arduino act as a Tic-Tac-Toe trainer for beginners. While guiding their learning process by letting them play against increasingly better strategies, I can monitor their progression and compare it with the learning process of an Artificial Neural Network (ANN), for which I’m currently writing a sketch. Will 2,000 bytes be able to keep up with 100,000,000,000 human neurons?

This is a work in progress. For now, the video shows the Arduino in invincible mode, with me playing at the level of a befriended nation’s president. I even managed to put myself in a lost position after my very first move. It definitely takes some skills to loose this game…