Why is Alan Turing often described as the father of Computer Science? Watch Marc Scott explain the significance of the Turing machine.
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.
Help each other out and share your answers in the comments section.