Skip to 0 minutes and 0 secondsIn this step, we're going to have a look at Turing machines, which were hypothetical computers invented by Alan Turing in 1936. A Turing machine consists of an infinitely long tape. This tape is divided up into cells, and into each cell can be written a 1, a 0, or an empty space. Above the tape is a head that can either move left, right, and read the symbols written in the cells. The head is also capable of erasing and writing new values into the cells. The direction the head moves, which values it erases, and which values it writes in is dependent on a of instructions provided to the machine.

Skip to 0 minutes and 45 secondsHere, the head is in state 2, and the instructions say that if it reaches 0, then erase it, write in a 1, move one cell to the right, and change your state to 5.

Skip to 1 minute and 1 secondState 5 might read, if I'm reading a 1, erase it, write in a 0, and move one cell to the left, and change the state to 7. It seems incredible, but with such a simple system, Alan Turing proved that any problem that is computable can be computed by a Turing machine. So let's build a Turing machine and see what this looks like. We've got our tape, our head, some initial instructions, and we'll place some 1's and 0's on our tape to begin with. Now, the first symbol is a 0, and the instructions say that when reading a 0, it should write a 1 and move left.

Skip to 1 minute and 42 secondsMoving 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 0's to 1's and 1's to 0's. The instructions for this Turing machine only had one state, but more complex Turing machines can be built using multiple states. Let's have a look at one of these now. We start in state A, with a head position underneath the first symbol.

Skip to 2 minutes and 25 secondsLooking at the instructions, we see that in state A, with a symbol of 0, there's no write, and the head should move to the right, and the Turing machine should remain in state A. Next it reads a 0 and moves to the right, then reads a 1 and moves to the right again. Now it's reading a blank, which means it moves 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.

Skip to 3 minutes and 5 secondsIn state C, there were no write actions to be done. 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 as you see them on the screen. Then run the instructions two more times and see if you can figure out what this Turing machine does. Help each other out, and share your answers in the comment section.

Turing machines

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, and we’re going to take a closer look at them in this step.

Alan Turing Aged 16

A Turing Machine consists of an infinitely long tape, that 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.

Animated FIG showing a head moving left and right, reading a cell and erasing and writing to a cell.

The direction that the head moves, which values it erases, and which values it writes in, 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 you’re reading a 1.)

Turing machine following the instructions for state 2.

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.

Turing machine following the instructions for state 5

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

So let’s build a Turing Machine and see how that might work.

We have our tape, our head, some initial instructions, and we’ll place some 1s and 0s on our tape to begin with.

A simpler representation of a Turing machine, with three cells filled on the tape, reading 1 1 0 from left to right. The head is shown pointing at the 0.

Now 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.

The Turing machine following the instructions above, finishing with the head pointing at a blank cell, with 0 0 1 in the three cells to the right of it.

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. Let’s have a look at one of these now.

A Turing machine with 3 states, following the instructions below. 0 0 1 is changed to 0 1 0, and the head finishes off pointing at the rightmost 0.

We start in State A, with the head positioned underneath the first symbol. Looking at the instructions, we see that in State A, with a symbol of zero, there’s no write, the head should move to the right, and the Turing Machine should remain in State A.

Next it reads another zero 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 zero, which means it writes a 1, moves Left and switches to state C.

In State C, there are no write actions to be done. 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.

Help each other out and share your answers in the comments section.

Share this video:

This video is from the free online course:

How Computers Work: Demystifying Computation

Raspberry Pi Foundation