Implementing a Turing Machine
with Lego moving parts only

To celebrate the centenary of Alan Turing's birth, some master's students from the ENS de Lyon in France built a Turing Machine in Lego without any electronic components which is pretty unique. The machine works entirely with pneumatic Lego cylinders, and gears. It proves that the classical Lego pieces are Turing-powerful! The main challenge was to built the action table and to synchronize every part, without using Lego Mindstorms (Lego electronic components) or a computer.

Turing Machine

If you want to know precisely what is a Turing Machine, you should read AlanTuring.net, Wikipedia or Stanford encyclopedia (don't forget to build your own Paper Turing Machine). We won't give its definition here, because it has been greatly done elsewhere. We will just give the idea behind it, and say a word about the beauty of computability which motivates the design of a Lego Turing Machine.

A Turing Machine is a mathematical object, defined in 1936 by Alan Turing, aimed at describing what is a computation. Everybody has a feeling of what is a computation: if you got two numbers in base 10, let say 123 and 456, and you want to compute their sum, you do it digit by digit from right to left and propagate possible carries to get 579. If you want to compute their product, you decompose it into simpler multiplications for which you learnt a finite number of tables and sum the results of the subproblems: 123x456=(1x100+2x10+3)x(4x100+5x10+6)=(1x4)x(100x100)+(1x5)x(100x10)+(1x6)x(100)+(2x4)x(10x100)+(2x5)x(10x10)+(2x6)x(10)+(3x4)x(100)+(3x5)x(10)+(3x6)=56088. When you want to teach someone the method you use to perform a multiplication, you describe your algorithm: you give a finite (for example you need 10 minutes or 2 pages) description of the procedure you use to get the result. Turing Machines are the mathematical objects describing algorithms. A Turing Machine for the addition of natural numbers in base 10 gives the set of instructions you have to perform in order to compute the sum of two numbers. An important remark is that the description of the procedure is finite, but it allows to compute the sum of any couple of numbers: 123+456 or 1234567890+2345678901 or larger numbers!

Now, let's become serious. A Turing machine describes how to compute something. But what is this something? It is a function. For example, a function can be the addition, or the multiplication: given a finite input (in our examples 123 and 456), a function associates a unique output. The input and output can be one or more natural numbers, negative numbers, a sentence written in Latin alphabet or whatever. The important thing is that it is finite. Then a function associates a unique output (the result) to each input. Functions can be simple: the addition or multiplication of two natural numbers; or more tricky: given a natural number, give its decomposition as a product of prime numbers (natural number greater than 1 that has no positive divisors other than 1 and itself); or even uncomputable: given a mathematical statement, decide whether it is true or false. Yes, some functions are not computable: there exists no algorithm to compute them. Moreover, there are infinitely more uncomputable functions than computable ones! There exists an infinity of functions, and an infinity of Turing Machine (algorithms), but the number of functions is still infinitely bigger than the number of Turing Machines.

At this point, a natural question is: if Turing Machine are able to compute so little functions, why don't we compute whith another mathematical model? Actually, Turing Machines are not the only mathematical object describing algorithms. Such objects are called effective models of computation, where effective means something like "in compliance with the real world". Nevertheless, a wonderful fact is that every effective models of computation are equivalent! Two models are equivalent if they can compute exactly the same set of functions. Remember: let F be the set of all functions, a Turing Machine cannot compute every function of the set F, but only a subset C called the set of computable functions. The believe that any other effective model of computation one can imagine will again be able to compute all functions within C and nothing else is called the Chruch-Turing Thesis, and C is called the set of computable functions. One a the most fundamental question of computer science is: why is something computable or uncomputable?

Something of interest is the existence of Universal Turing Machines. A Universal Turing Machine U is a machine capable of simulating any other Turing Machine. What do this mean ? Let M be any Turing Machine and x be an input, the output of M on x is written M(x). U is universal if we can write an input y on the tape and the run of U on y outputs  M(x). y is indeed simple: M has a finite description (mainly: its action table), so this description can be written on the tape, it uses n cells; and on some other empty cells, we can write x. Now, U has all the information that defines M(x) on the tape, and it is possible* to construct a machine U that reads the input x on the tape, then reads the action table of M on the n dedicated cells of the tape, and then perform on x what M would have done if it where run on a tape containing x. Such a U is a bit tricky, but not much. Nowadays, a tape is called a hard drive, the action table of M written on a tape is a program, and U is a computer!

*note that the existence of uncomputable functions says that for some other problems (again there are lots of them, infinitely more that computable ones), even when provided with all the information that defines the question, it is not possible to define a Turing Machine that computes the result.

It is possible to change the action table of our Lego Turing Machine, and it is possible to implement a Universal Turing machine on it. Consequently, this Lego stuff is able to compute the set of computable functions C: it has exactly the same computational power as your laptop of cellphone! In comparison with a modern computer which performs one instruction every nano-second (0.000000001 second), our machine performs one every 100 seconds. It can do anything a modern computer does, but to perform what this latter executes in 1 second, our Lego Turing Machine takes 3168 years 295 days 9 hours 46 minutes and 40 seconds*. Anyway... the important fact is that it is able to do it, isn't it ?

*this number is actually completely wrong, because an instruction of a Turing Machine is deeply different from an instruction of a modern computer. Notwithstanding, the aim of this freaky number is to emphasize the fact that this Lego Turing Machine is earnestly equivalent to a modern computer.

This is the heart of computability. Modern computers are every year faster, and their speed will continue to increase. However, they remain restricted to the set of computable functions, C. They can compute the functions of C always faster, but they cannot escape C: their expressivity remains the same. The study of this expressivity, of the meaning of this computational power, is called computability theory.

You may hear that we are nowadays able to compute things that where impossible to compute in the past years, that computers are more powerful today than yesterday. This statement needs to be precised. Actually, the fact is that those computations where only too long to perform in the past years (for example they may have taken 100 years if you had launched them in 2000), but today you can compute them in a reasonable time (for example 100 seconds) which allows to effectively get the result. An interesting example is chess: it is possible today, and it has always been possible, to write down an algorithm which tells you step by step the best move to perform, but today's computers are far too slow and i am sure to die before getting any move to perform if i launch such an algorithm on my brand new laptop... Nevertheless, one day, and i think that i will still be alive when it will occur, we will be able to perform this computation in a reasonable time, and then, playing chess with a computer will become very boring because you will loose every game*. Let me repeat that such an algorithm already exists and is easy to type on a computer, computers are simply too slow to perform the computation in a reasonable time. Computability theory is interested in mathematical truth which are independent of the computational time: the question is not knowing whether something will be feasible in 10 or 20 years, but rather if something is fondamentaly feasible or not, fundamentaly true or false.

*well... i am lying in order to be clearer. Actually, since we have yet never computed all possible chess moves, we don't know if it is the white or the black which are able to win every game, or if we arrive at a draw with two perfect players...