To honor Alan Turing, the Centrum Wiskunde & Informatica (CWI) built a simple LEGO Turing Machine — part of the Turing’s Erfenis exhibition at CWI — to show how simple a computer actually is, making every operation as visible as possible and using just a single LEGO MINDSTORMS NXT set.

“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.” — Wikipedia

 

Actually, it’s not a physical machine; rather, a theoretical model that describes the fundamental capabilities of almost 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.

LEGO Turing machine

CWI’s LEGO Turing machine uses a tape based on a classic interpretation of computer memory: switches. It also uses a light sensor to determine the value of a switch: if the switch is on, the sensor will see the black color of the switch’s surface; if off, the sensor will see the white color, making it possible to distinguish between the states. A rotating beam mounted above the tape can flip the switch in both directions.

Alan Turing’s original model had an infinite tape, but LEGO had a slight problem supplying infinite bricks so they chose to fix the tape size to 32 positions.

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.

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

LEGO Turing Machine from ecalpemos on Vimeo.