Tech Tuesday: Turing Machines
Posted by childofthehive | Filed under Tech Tuesday
2012 is Alan Turing year, celebrating the life of one of the founders of computing and one of the minds behind the cracking of the Enigma code. In honour of this, I’m writing a couple of Tech Tuesday posts about Turing’s contributions to computing.
This post, is about Turing Machines. He called them a(utomatic)-machines but they later became known after their inventor. To my knowledge, Turing never actually made one of these machines but he described them in 1936 as a theoretical exercise. By defining a machine that could calculate, or computer, answers to problems, he was able to know whether or not certain problems were actually solvable.
But what is a Turing Machine?
A Turing Machine consists of a few elements. First, you have a tape, broken down into equal sized sections. Each of these sections may be blank or may have symbols written in them (usually, 0 and 1, but you can have more). In general, when people talk about Turing Machines, it’s considered that this tape can be as long as necessary to complete the computation, so the tape is theoretically infinite.
The second element of the machine what’s called a head. This head is something which is pointed at a single section of the tape. It can read whatever symbol is written there as well as write a symbol onto the tape, replacing whatever symbol was there to begin with.
The machine also has a set of rules. These rules look at the state the machine currently is in as well as the symbol written on the tape and determines a next action. For example, if the machine is in state A and 1 is written on the tape, write a 0 onto the tape, move the tape to the right and go to state B, if 0 is written on the tape, write a 0 onto the tape, move the tape to the left and go to state C.
You also need to define what the starting state is for the machine and one or more stopping states. If a machine arrives at a stopping state, the calculation is over.
But why should people care about Turing Machines? Nowadays, computers can do a lot more than just move a tape back and forth. Yet Turing Machines were discussed in two different modules of my university course because they are still significant in understanding computing.
One reason is the power behind this apparently simple model. You can, in theory, calculate using a Turing Machine anything that you could calculate using a more complex computer. I say in theory because there are a couple of things that Turing Machines aren’t good at (solving two problems at the same time, for example) and because it wouldn’t be practical to use a Turing Machine as the complexity of the problem increases. While the model allows for the tape to be as long as necessary and for the machine to have as many rules as required, you wouldn’t want to build or simulate a Turing Machine with a tape twenty thousand miles long with five thousand states and a few million rules. You’d be sitting forever waiting for the calculation to complete.
Once you’ve accepted the limits of practicality however, these machines are very useful in the theory of computability. This is the study of what can or can’t be computed. Essentially, there are some problems a computer is capable of solving and some which is can’t. A problem is proved to be computable if you can design a Turing Machine that would solve it. As stated above, this isn’t necessarily practical, so a problem is also proved to be computable if you can solve it using functions which have been proved by Turing Machines. For example, it’s possible to design a Turing Machine that adds two numbers together, therefore addition of two numbers is solvable. Multiplication can be thought of as repeated addition (e.g. 3×4 is just 3+3+3+3) and since we’ve proved with a Turing Machine that addition is computable, multiplication is computable. You can do this again and again, building up the complexity until you can work out if very complex functions can be computed.
When computers were first created, they were a long way from the machines we have today. The earliest computers were machines that, as the name implies, computed the answers to calculations. Turing Machines were the first of these and so were the foundation that led to the massive range of computers available to us today.
Tags: Alan Turing, computers, Turing Machines
