图灵机——乐高电脑

Turing Machine – Working Lego Computer

作者：The Bananaman 201864801 / 发布于：2024-09-12

What is a Turing machine?

It's an abstract model of an algorithmic machine. Although it was not designed to be implemented in real life, some people actually do this using esoteric "technologies" such as Minecraft Redstone or Conway's Game of Life – I decided to make it using Lego bricks. It's named after its creator, Alan Turing– an English cryptologist.

The machine consists of:

an infinitely long (in real life: long enough to do all practical programs) tape with symbols that can be moved left and right
a "head" over one of the symbols that can read it and overwrite it with a new one,
some registers containing the state of the machine,
a table linking each combination of state and symbol to an instruction what to do next.

…and the working cycle of the machine looks like this:

read the symbol from the tape
based on the symbol and the state, see what to do next in the table
based on the instruction, go to a new state and print a new symbol in place of the one that has been read
also based on the instruction, move the tape 1 symbol left or right or exit the program

The cycle continues until the machine stops. This way it can execute any computer algorithm – so it's technically a computer, although it works a bit differently than the electronic ones we use every day.

About the model

The model has 4 ( 2²) possible symbols and 8 (2 ³) possible states, so in total 32 possible symbol-state combinations. Each instruction has 7 bits (3 for the state, 2 for the symbol, 1 for moving left/right and 1 for stopping), so the "source code" takes 7*32 = 224 bits or 28 bytes. That means you can make 2^224 ≈ 2.69*10⁶⁷ programs ! (most of them will be useless though).

The mechanism is also quiet complex for a Lego set. It connects all the functions to 1 input, so that the model requires no electric motor. You can see how it works in the video.

Won't there be a problem with Intellectual Property?

No, the Turing machine is a mathematical model and has no Intellectual Property :)

Isn't it too big?

Since October 2024, the Lego IDEAS' part count limit is 5000 parts. This model has ~2900 parts which still could make it quiet expensive, but a lot of them are functional (i.e. part of the mechanism) or used to make the framework more sturdy because the mechanism is very precise and needs good support.

Why would it be a good set?

Because: