Intro

This project, the Turing Machine Demonstrator, is a fully realized electromechanical interpretation of the theoretical computing model conceived by Alan Turing in his seminal 1936 paper On Computable Numbers. It transforms the abstract principles of computer science into a physical, functional machine, offering a vivid demonstration of how computation fundamentally works.

This model is widely used to distinguish a calculator from a computer. A system or machine is considered Turing complete if it can, in principle, compute everything that a Universal Turing Machine (UTM) can compute.

It has the following parts.

The parts

The moving Turing tape

An aluminium profile carries 19 7-segment digits. Each digit can represent a 0, a space, or a 1, and is written using an ON-OFF-ON switch. The tape is moved by a stepper motor and a linear rod. A guidance nut is attached to the profile and moves along the rotating rod. The profile is kept aligned by eight guidance wheels. A positioning LED ensures that the tape is precisely positioned before writing a new symbol.

The read head

The tape is read using LDRs. The positioning LED, as well both right segments of the 7-segment display (the “1”) and the left two segments (forming part of the “0”), are detected. When the positioning LED is seen, the tape is correctly placed.

• If the 7-segment LEDs are off, the symbol is a space.

• If only the right LDR detects light from both the right segments, the symbol is 1.

• If both - the left and right segments - LDRs detect light, the symbol is 0.

Special attention has been given to calibrating the light levels. It is important to reliably determine the threshold values that distinguish between LED segments being on or off. This is dynamically handled by the software.

The write head

Two opposing linear actuators are used to toggle the switch and write a symbol on the tape. The actuator retracts when the read head confirms that the required symbol has been correctly written.

The program

The “program” of a Turing machine consists of a state table. For each combination of state and read symbol, the table specifies:

1. The new symbol to write (0, space, or 1)

2. Whether the head must move left, right, or stay in place

3. The new state

To explain how a Turing machine program works, I developed a Turing Machine Game, which allows the player to experience the mechanics of a Turing machine and become a “busy beaver.” See details here: https://hackaday.io/project/203270-the-turing-machine-game

The machine starts with three pre-programmed programs. Depending on the first digit read — 0, space, or 1 — one of these programs is executed.

In the downloadable files you will find a helpful Excel sheet, The Turing Test, which simulates a Turing machine and checks your program quickly and easily.

Entering a program

A program can be entered into the Turing machine using a program reader — the modern equivalent of a punch card. Instead of holes, the program sheet contains a checkerboard-like pattern where black squares represent 1 and white squares represent 0.

An Excel sheet is provided to enter a Turing program, convert it to a format readable by the Turing Test Excel tool, and generate the machine-readable program sheet.

Even better, there is also a blank template sheet so that people can write their own program in situ using a black marker.

The program reader

The program reader contains photodiodes in the box, white LEDs in the bar above the box, and a narrow slit through which the program sheet is fed. The program sheet is moved manually through the reader.

The control box

The machine is controlled via a control box with an Arduino mega 2650 and 1700 lines of C++ code. The box displays:

• The mode (blue display)

• The current state and number of steps (white display)

• The action information per read symbol: red for 0, yellow for space, and green for...