What is a Turing machine? According to Wikipedia:

“A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algorithm.”

An ideal Turing machine has an infinitely long tape with a tape head that moves forwards and backwards over the tape. The tape head can read and write a number of different symbols on the tape at its current square or erase the tape at that position.

Obviously an infinite tape isn’t possible but how many squares would be enough for some interesting programs? 27 seemed a reasonable number. For symbols I could use RGB LEDs (WS2812 or Neopixels) with the seven principal colours representing different symbols and black representing an empty or blank square. The head can’t physically move but I could indicate the current position by making its LED a little brighter.

A rectangular PCB to represent a linear tape was the obvious choice but a rectangle isn’t a very interesting shape. So I twisted the tape into more of an S-shape. It was starting to look a bit snake-like which suggested adding a head and tail and then to decorate the surface with scales to represent the skin. With an ENIG gold finish the result was quite visually appealing in KiCad’s 3D render.

I wanted to keep the top side of the board uncluttered so all the components apart from the LEDs would go on the bottom side. I wanted a USB interface both to supply power and to allow programs to be uploaded from a host PC. I needed a microcontroller in a small package with USB support that could be easily hand soldered. The Microchip PIC16F1454 fitted the requirements. It comes in a 14-pin SOIC package and Microchip makes available C source code to support a virtual serial connection to a PC. It has enough RAM to store a program of up to 256 characters as well as 10 variables. It can also self-program its flash memory so a user program can be non-volatile. A few additional passive components were all that were required.

WS2812 LEDs are connected in series with only a single microcontroller pin needed. These components need tight software timing which required coding in assembler.

In the firmware there is an interpreter for the compact instruction set I developed (see below).

Before beginning a PCB I decided to build a simulator app running on Windows desktop using C# and WPF. With a GUI, syntax highlighting and single stepping it was easy to write and debug programs. Once tested a program can be uploaded to the target board from within the app.

Instruction Set

Most of the instructions are single characters or a pair of characters.

The capital letters R G B C M Y W K set the symbol (colour) of the current square (with K being black for a blank square).

> and < move the tape head to the right and left; << and >> move the head to the ends of the tape.

$ defines a variable; ++ and -- increment and decrement a variable. Simple expressions for variable assignments with left-to-right priority which can be overridden with parentheses.

? is a conditional test. The following instruction is executed if the condition is true or skipped if not.

# defines a label; ^ jumps to a label.

%n waits for n time periods or indefinitely if 0.

Finally ; marks a comment.

Examples

Some sample programs:

Starting from the least significant pixel, toggle each pixel and repeat if the pixel then becomes set, otherwise move on to the next more significant pixel.

The two numbers are represented by strings of LEDs at the two ends of the tape (in different colours). Initially count the number of red and green LEDs. Then apply the algorithm using two subroutines to subtract from the ends of the LED strings. After the program completes the number of red/green LEDs remaining on is the greatest common divisor.

This program...