Lego Computer Science: Turing Machines Part 3: the program

by Paul Curzon, Queen Mary University of London

We have so far built the hardware of a Lego Turing Machine. Next we need the crucial part: software. It needs a program to tell it what to do.

Our Turing Machine so far has an Infinite Tape, a Tape Head and a Controller. The Tape holds data values taken from a given set of 4×4 bricks. It starts in a specific initial pattern: the Initial Tape. There is also a controller. It holds different coloured 3×2 bricks representing an initial state, an end state, a current state and has a set of other possible states (so coloured bricks) to substitute for the current state.

Why do we need a program?

As the machine runs it changes from one state to another, and inputs from or outputs to the tape. How it does that is governed by its Program. What is the new state, the new value and how does the tape head move? The program gives the answers. The program is just a set of instructions the machine must blindly follow. Each instruction is a single rule to follow. Each program is a set of such rules. In our Turing Machines, these rules are not set out in an explicit sequence as happens in a procedural program, say. It uses a different paradigm for what a program is. Instead at any time only one of the set of rules should match the current situation and that is the one that is followed next.

Individual Instructions

A single rule contains five parts: a Current State to match against, a Current Value under the Tape Head to match against, a New State to replace the existing one, and a New Value to write to the tape. Finally, it holds a Direction to Move the Tape Head (left or right or stay in the same place). An example might be:

Current State: ORANGE
Current Value: RED
New State: GREEN
New Value: BLUE
Direction: RIGHT

But what does a rule like this actually do?

What does it mean?

You can think of each instruction as an IF-THEN rule. The above rule would mean:

the machine is currently in state ORANGE AND
the Tape Head points to RED

THEN (take the following actions)

change the state to GREEN,
write the new value BLUE on the tape AND THEN
move the tape head RIGHT.

This is what a computer scientist would call the programming language Semantics. The semantics tell you what program instructions mean, so what they do.

Representing Instructions in Lego

We will use a series of 5 bricks in a particular order to represent the parts of the rule. For example, we will use a yellow 3×2 brick in the first position of a rule to represent the fact that the rule will only trigger if the current state is yellow. A blue 2×2 brick in the second position will mean the rule will also only trigger if the current value under the tape head is blue. We will use a grey brick to mean an empty tape value. The third and fourth position will represent the new state and new value if the rule does trigger. To represent the direction to move we will use a 1×2 Red brick to mean move Right, and a 1×2 yeLLow brick to mean move Left. We will use a black 1×2 brick to mean do not move the tape head (mirroring the way we are also using black to mean do nothing in the sense of the special end state). The above rule would therefore be represented in Lego as below.

A Turing machine instruction
Current state: orange
Currnent value red
New state green
New value blue
Direction red — A single instruction for a Lego Turing Machine. Image by CS4FN

Notice we are using the same colour to represent different things here. The representation is the colour combined with the size of brick and position in the rule. So a Red brick can mean a red state (a red 3×2 brick) or a red value (a red 2×2 brick) or move right (a red 1×2 brick).

Lego programs

That is what a rule, so single Turing Machine instruction, looks like. Programs are just a collection of such rules: so a series of lines of bricks.

Suppose we have a Turing machine with two states (Red and Orange) and two values on the tape (Blue or Empty), then a complete program would have 4 rules, one for each possible combination. We have given one example program below. If there were more states or more possible data values then the program would be correspondingly bigger to cover all the possibilities.

A Turing Machine Program
Red-Blue -> Red-Blue-Red
Red-Grey -> Orange-Blue-Yellow
Orange-Blue -> Orange-Blue-Yellow
Orange-Grey -> Black-Grey-Red — A 4 instruction Turing Machine Program for a Turing Machine with two states (Red, Orange) and two data values (Blue, Empty). Image by CS4FN

A Specific Turing Machine

Exactly what it does will depend on its input – the initial tape it is given to process, as well as the initial state and where the tape head initially points to. Perhaps you can work out what the above program does given a tape with an empty value followed by a series of three blue bricks (and then empty data values off to infinity (the blank value is the only value that is allowed to appear an infinite number of times on an initial tape) and the Head pointing to the rightmost blue brick value. The initial state is red. See the Lego version of this specific machine below.

A Turing Machine with Tape, Controller and Program. — A full Turing Machine ready to execute. Image by CS4FN

Note something we have glossed over. You also potentially need an infinite number of bricks of each value that is allowed on the tape. We have a small pile, but you may need that Lego factory we mentioned previously, so that as the Turing Machine runs you always have a piece to swap on to the machine tape when needed. Luckily, for this machine a small number of bricks should be enough (as long as you do not keep running it)!

What does this Turing Machine do? We will look at what it does and how to work it out in a future article. In the meantime try and work out what it does with this tape, but also what it does if the tape has more or less blue bricks in a row on it to start with (with everything else kept the same).

Note that, to keep programs smaller, you could have a convention that if no rule fits a situation then it means the program ends. Then you could have fewer rules in some programs. However, that would just be shorthand for there being extra rules with black new states, the tape being left alone, and the tape head moves right. In real programming, it is generally a good idea to ALWAYS be explicit about what you intend the program to do, as otherwise it is an easy way for bugs to creep in, for example, because you just forgot to say in some case.

Alan Turing invented Turing Machines before any computer existed. At the time a “computer” was a person who followed rules to do calculations (just like you were taught the rules to follow to do long multiplication at primary school, for example). His idea was therefore that a human would follow the rules in a Turing Machine program, checking the current state and value under the tape head, and changing the state, the value on the tape and the movement of the head. A person provides the power and equivalent of a robotic arm that follows the underlying Turing Machine algorithm: the Turing Machine algorithm that if followed causes each Turing Machine’s program to execute.

If a human animating the machine was good enough for Turing, it is good enough for us, so that is how our Lego Turing Machines will work. Your job will be to follow the rules and so operate the machine. Perhaps, that is exactly what you did to work out what the program above does!

Next we will look at how to work out what a Turing Machine does. Then it will be time to write, then run, some Turing Machine programs of your own…