### A Turing machine built using LEGO Mindstorms

##### June 21, 2012

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.

## comments 1

June 21, 2012by Jukka

Awesome! I am at the moment myself programming 3 NXT Lego robots. It consists of master robot that finds it’s way through a maze and 2 slave robots that follow it like a body of a centipede. They communicate through Xbee Wifi block. :) Cool stuff.