£199.99 £139.99 for one year of Unlimited learning. Offer ends on 28 February 2023 at 23:59 (UTC). T&Cs apply

Turing Machines Explained

A Turing machine consists of an infinitely long tape, which has been divided up into cells. Each cell can contain either a 1, a 0, or an empty space. Above one cell of the tape is a head, which can either move left or right, and can read the symbols written in the cells. The head is also capable of erasing symbols and writing new symbols into the cells.

While Babbage and Lovelace can be considered the parents of computers and programming, Alan Turing is often called the father of computer science. During the war effort, Turing worked on cracking encrypted messages used by the German armed forces, and helped design machines to make this possible.

It was when working on a mathematical problem concerning Decidability and The Halting Problem, though, that Turing realised he needed a mathematical description of a machine that could solve algorithms. These machines came to be known as Turing machines.

What is a Turing Machine?

A Turing machine consists of an infinitely long tape, which has been divided up into cells. Each cell can contain either a 1, a 0, or an empty space. Above one cell of the tape is a head, which can either move left or right, and can read the symbols written in the cells. The head is also capable of erasing symbols and writing new symbols into the cells.

The direction that the head moves, which values it erases, and which values it enters, are dependent on a set of instructions provided to the machine.

In the machine shown below, the head is in state 2, and the instructions say that if it reads a 0, then erase it, write in a 1, move one cell to the right and change your state to 5. (There’ll also be instructions in the case it reads a 1.)

State 5 might say, if you’re reading a 1, erase it, write a 0, and move one cell to the left. Then go to state 7.

It seems incredible, but Alan Turing proved that any problem that is computable can be computed by a Turing machine using this simple system.

Build a Turing Machine

Now you are going to build a Turing machine and see how that might work.

You have your tape, your head, some initial instructions, and you will place some 1s and 0s on your tape to begin with.

The first symbol seen by the head is a 0, and the instructions say that when reading a 0, it should write a 1 and move left.

Moving left, it then reads a 1, which according to the instructions means it should write a 0 and move left.

It then reads another 1, writes a 0 and moves left, and finally reads a blank at which point the program halts.

So this Turing machine is designed to flip bits. It changes 0s to 1s and 1s to 0s.

The instructions for this Turing machine only had one state, but more complex Turing machines can be built using multiple states. You are going to have a look at one of these now.

You start in state A, with the head positioned underneath the first symbol. Looking at the instructions, you will see that in state A, with a symbol of 0, there’s no write instruction, the head should simply move to the right, and the Turing machine should remain in state A.

Next, it reads another 0 and again moves to the right. Then, it reads a 1, and moves to the right again. Now, it reads a blank, which means it’s got to move to the left, but it also changes to state B.

Looking at the instructions for state B, if it’s reading a 1, it erases it and writes a 0, and then moves left, staying in state B. Next, it reads a 0, which means it writes a 1, moves left and switches to state C.

In state C, there are no write actions perform. The head just keeps moving right until it eventually reaches a blank, at which point it moves left and the program halts.

Now it’s your turn to have a go. Get yourself a piece of paper, a pencil, and an eraser, and copy out the tape, the head, and the numbers exactly as you see them on the screen. With the machine in this state, run through the instructions again, and then once more. See if you can figure out what this Turing machine does.