A Turing Machine built using LEGO

In honor of the Alan Turing year 2012

To honor Alan Turing, we built a simple LEGO Turing Machine, to show everyone how simple a computer actually is. Primary goals were to make every operation as visible as possible and to make it using the automatic components of just a single LEGO MINDSTORMS NXT set, to make it easy to reproduce for those interested. The LEGO Turing Machine is part of the exhibition  Turing's Erfenis  at CWI. Contact the builders at info@legoturingmachine.org.

Video

Short documentary by Andre Theelen of  ecalpemos.nl

The Turing Machine

According to  Wikipedia:

"A Turing machine is a device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer."

Unlike what the name suggests, it is not a physical machine but rather a theoretical model. It's very simply, but describes the fundamental capabilities of practically all computers in use today. This means that if something can be done on a computer, it can also be done on a Turing machine. This makes it a great model for scientists to use to discover the limits of computers (e.g. complexity theory) and also to show to a broad audience how a computer fundamentally operates.

However, abstract models are just that, an abstraction of something. In order to really show how simple the fundamental model of a computer is, we have developed a physical implementation of the Turing machine, using LEGO Mindstorms NXT.

Hardware: LEGO

Our LEGO Turing machine uses a tape based on a classic interpretation of computer memory: switches. Additionally, it uses a light sensor to determine the value of a switch: if the switch is on, the sensor will see the black colour of the switch's surface. But if it is turned off, the sensor will see the white colour of the LEGO beam, making it possible to distinguish between the states. Finally, a rotating beam mounted above the tape can flip the switch in both directions.

Alan Turing's original model has an infinite tape, but LEGO had a slight problem supplying infinite bricks. So we chose to fix our tape size to 32 positions. Our LEGO Turing machine only uses automatic components that are part of a single LEGO Mindstorms NXT set: one NXT brick, three electric motors and one color sensor. The final model contains parts of the NXT 2.0 set as well as a bunch of parts (mostly large beams, but also a cork screw and a set of gear racks) from two other LEGO Technic sets. We believe a slightly smaller version can be constructed using only one Mindstorms NXT 2.0 set (8547-1) and the medium-sized Technic set Mobile Crane (8053-1), which are both currently available.

Instructions

Since we only have 32 positions, and the most basic alphabet, it would be difficult to encode our instructions on the same tape as the input. Another goal was to make the device tamper proof, such that it could be operated by visitors off the exhibition. Therefore, to avoid limiting the instruction size and to protect the running program, we chose to write the instructions to a file on the NXT brick and uses the simplest interpreter to run these instructions.

Basic instruction set

W(0|1) = write either 0 or 1 on the tape
M(F|B) = move the tape either forward or backward
J(_|0|1)[0-9]+ = read & jump (always, when 0, or when 1) to a row in the instruction table

The instructions running in the video can be found in this file on github. It implements a simple adder of two numbers.

Software: Rascal

The software we have developed to execute programs in a basic Turing machine language can be found on  github  Additionally, we have developed an interactive development environment (IDE) using the  Rascal Meta-programming Language  which is stored in our public  subversion repository.

Credits

Built by

Additional contributions by