Markus Schwagenscheidt

PostDoc in Mathematics

The Lego Turing Machine

In June 2018, Julian Bitterlich and I gave a course on 'Computability Theory' during a summer school for high school students at the TU Darmstadt. The summer school has been organized annually since 2014 by Anna von Pippich and Fabian Völz and aims at students aged between 14 and 19 who are particulary interested in mathematics. In addition to three lectures on the basics of the theory of computation (you can find the notes here) we built a Lego Turing machine together with the seven students attending our course. We spent about six hours in total to build the machine and write some programs for it.

Our Lego Turing machine is based on the famous machine by Jeroen van den Bos and Davy Landman, which they built in honour of Alan Turing's hundredth birthday in 2012. There are nice building instructions by Soonho Kong. He used the last generation Lego Mindstorms NXT 2.0 Kit. Here I would like to show you how we built and programmed a similar Lego Turing machine with the newer Lego Mindstorms EV3 Set. Since time and financial resources were rather limited we tried to simplify some parts of the machine and to use as few additional Lego parts as possible. We used the standard Lego Mindstorms EV3 software (available on the Lego website) to program the machine. You can download our sample project here.

One fun program that you can run on the Lego Turing machine is a 4-state busy beaver printing thirteen 1's in 107 steps when given only 0's as input. Here is a video (in original speed!)

1. How the machine works

Our Lego Turing machine works in the same way as the machine of van den Bos and Landman, with some simplifications: Its main features are

  1. a moving tape, equipped with 16 switches representing the symbols 0 and 1,
  2. a fixed colour sensor which reads the current symbol (red means 1, not-red means 0),
  3. a fixed head with a rotating lever which can flip the current switch from 0 to 1 or from 1 to 0.
In each step, the colour sensor first reads the content of the tape (0 or 1). Then, depending on the symbol read and the current state of the machine, the head prints 0 or 1 on the tape (i.e., the lever flips the current switch or not), the machine goes into a new state, and the tape moves one step to the left or to the right. The state of the machine is stored as a variable in the machine's program, see below.

There are three main differences between our machine and the machine of van den Bos and Landman:

  1. We only use 16 tape cells instead of 32.
  2. Our colour sensor is fixed. That way it is easier to build. Nevertheless, if you have enough time then there are certainly enough parts to build a moving colour sensor, which looks nicer and makes the 'reading' step more visible.
  3. The movement of our tape is simpler. It is easier to build, needs less parts, is much (very much!) faster, but less precise. It is really a lot of fun to let our machine run on full speed.

2. What you need

  1. One Lego Mindstorms EV3 Set (Home Edition). We used one middle motor, one large motor, and the colour sensor to bring the Turing machine to life. Don't forget to buy suitable batteries!
  2. Additionally, the following parts are needed, mainly for the tape:
    1. 16 pieces, 90 degree white angle connector, Nr. 4654049
    2. 30 pieces, red technic axle 2 notched, Nr. 4142865
    3. 50 pieces, red technic bush, Nr. 4227155
    4. 5 pieces, red technic axle/pin connector perpendicular, Nr. 4188298
    5. 25 pieces, blue technic pin 1/2, Nr. 4143005
    6. 10 pieces, grey technic gear rack 1 x 4, Nr. 4211450
    It seemed that the colour sensor detects red much more reliably than white, which is why we put red pins and bushes on the white switches. To minimize errors I recommend to use red pins and bushes, and switches in a different color (e.g., white). It might also work if you use red switches, without additional pins and bushes, but I did not try it. The colours of the other parts do not really matter.
  3. I bought the above parts online at 1000Steine.de for about 20 Euros.

3. Building instructions

I hope that the pictures explain the construction good enough to enable you to build your own machine.

4. Programming the machine

We used the 'Lego Mindstorms Home Edition EV3' software (Version 1.3.1) for the programming of the Lego Turing machine. You can download our sample project here. It contains a 2-state busy beaver program explained below and the 4-state busy beaver program running in the video above.

I assume that the reader has a basic idea about the usage of the software. As an example, here is our program for a 2-state busy beaver which prints four 1's on the zero input (click to enlarge).

Let us go through the program.

The subroutine 'Step' looks as follows (click to enlarge).

Here's what it does:

Impressum