## Want to keep learning?

This content is taken from the Raspberry Pi Foundation & National Centre for Computing Education's online course, How Computers Work: Demystifying Computation. Join the course to learn more.
1.5

## Raspberry Pi Foundation

Skip to 0 minutes and 0 seconds In 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 seconds Here, 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 second State 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 seconds 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 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 seconds Looking 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 seconds In 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.

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.

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

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.

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.

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.

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.

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.