# Turing machines

**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.Help each other out and share your answers in the comments section.

#### How Computers Work: Demystifying Computation

## Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.

You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education