A student team from the Computer Science Department of ENS de Lyon (Elie GEDEON, Anael GRANDJEAN, Thomas LAMBERT, Yannick LEO, Thomas LEVENTIS, Robin PERROTIN, Etienne PYCIRCAN & Florent ROBIC) has build a Turing machine. We do not mean to simulate a Turing machine as it is indeed very easy to simulate a Turing machine on a modern computer. The challenge was really to build a purely mechanical Turing’s machine y using only LEGO™ bricks, gear, rod, pneumatic jack…
Building a Turing Machine is both a paradox and a dream. It’s a paradox since the aim is to “physically” build an abstract machine. It’s also a dream since the technology used remind the childhood sensation of inventing, designing, building anf giving birth to a machine that was not intended as a practical computing technology, but rather as a hypothetical device representing a computing machine.
Description d’une machine de Turing
The Turing machine was described by Alan Turing in 1936, who called it an “a(utomatic)-machine”. The Turing machine is not intended as a practical computing technology, but rather as a hypothetical device representing a computing machine.
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. A Turing Machine is similar to an old antic typewriter Remington machine without any key… From an informal point of view (taken from wikipedia), a Turing machine consists of:
- A tape which is divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol (here written as ‘B’) and one or more other symbols. The tape is assumed to be arbitrarily extendable to the left and to the right, i.e., the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written to before are assumed to be filled with the blank symbol. .
- A head that can read and write symbols on the tape and move the tape left and right one (and only one) cell at a time.
- A state register that stores the state of the Turing machine, one of finitely many.
- A finite table (occasionally called an action table or transition function) of instructions that, given the state the machine is currently in and the symbol it is reading on the tape (symbol currently under the head) tells the machine to do the following in sequence :
- Either erase or write a symbol, and then
- Move the head for one step left or for one step right or stay in the same place, and then
- Assume the same or a new state as prescribed.
Designing a LEGO™ Turing machine
The design has required more than 20.000 LEGO™ brick: 32 pneumatic jacks, 1200 gears, 24 lifts, 50m of pipes and hundreds of hours for the design and building. The LEGO™ Turing machine consists of the main parts as the the abstract one::
- The cart, for the tape. The cart is divided into cells, one next to the other. Each cell contains a symbol represented by a yellow square brick that code a binary value. Each break can be shift on the left (0 value) or on the right (1 value) in its cell.
- Thanks to a mechanism controlled by the machine, the cart can move to the left or to the right.
- The head car read and write symbols on the cart.
- The memory or table that encodes the actions of the machine and store the state register.
- The scheduler that trigger each component of the Turing machine one after the other: 1 cycle every 40sec. Style some improvement before reaching the pertaflops!