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
- a moving tape, equipped with 16 switches representing the symbols 0 and 1,
- a fixed colour sensor which reads the current symbol (red means 1, not-red means 0),
- a fixed head with a rotating lever which can flip the current switch from 0 to 1 or from 1 to 0.
There are three main differences between our machine and the machine of van den Bos and Landman:
- We only use 16 tape cells instead of 32.
- 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.
- 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
- 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!
- Additionally, the following parts are needed, mainly for the tape:
I bought the above parts online at 1000Steine.de for about 20 Euros.
- 16 pieces, 90 degree white angle connector, Nr. 4654049
- 30 pieces, red technic axle 2 notched, Nr. 4142865
- 50 pieces, red technic bush, Nr. 4227155
- 5 pieces, red technic axle/pin connector perpendicular, Nr. 4188298
- 25 pieces, blue technic pin 1/2, Nr. 4143005
- 10 pieces, grey technic gear rack 1 x 4, Nr. 4211450
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 states of the machine are represented by finitely many numbers 0,1,2,3,...,n. The initial state is 0 and the halting state can be chosen arbitrarily (in our example it is 2). The state of the machine is stored (and initialized with 0) in the first red variable box named 'State'.
- The main program sits inside the big loop. The program (the loop) ends when the 'State' variable has been set to the halting state. The halting condition is checked by the last red variable box and the red comparison box.
- Inside the loop, there is a switch depending on colour comparison. If the colour sensor reads 'red' (which means that there is a 1 on the tape), then the program continues in the upper half of the switch, otherwise it continues in the lower half.
- In both halfs of the colour-comparison-switch there is a state-comparison-switch. We have one branch for each state (i.e. the value of the red 'State' variable) except for the halting state. You can add states with the little plus button in this switch.
- In every branch we see a MyBlock subroutine 'Step' which sets a new state (#), writes a new symbol (a), and moves the tape left or right (<->).
The subroutine 'Step' looks as follows (click to enlarge).
Here's what it does:
- First, the 'State' variable is set to the new state.
- The first big switch writes the new symbol. The two small switches inside this switch check whether the current symbol on the tape already equals the symbol that we want to write before moving the lever. This ensures that the lever does not hit a white 90-degree switch from the wrong side and pushes the tape out.
- The second switch moves the tape. You have to play around a little bit with the angle-parameter of the motor to make sure that the tape moves exactly one step to the left or right.