You could say that the computer was invented twice – once by Babbage and once by Alan Turing. While Babbage’s machine was supposed to be a practical thing, Turing’s was just a machine of the mind. It was invented not to compute tables of numbers but to solve problems in logic and to probe the limits of computation and human thought. ...

In Grammar and Torture we look at every computer science student’s nightmare – formal grammar and meet the idea of a hierarchy of machines, ranging from the simple finite state machine to the Turing machine, which corresponds to different complexities of language, computer or human. This is interesting but it also raises the question of what a Turing machine is and why did anyone every bother to think up such an idea? While a Turing machine does have connections with grammar and languages it is so much more. But to start at the beginning…

Tapes and Turing machines

In a nutshell a Turing machine is a finite state machine with the ability to read and write data to a tape. Although we have looked at finite state machines before, a quick reminder is in order. Essentially a finite state machine consists of a number of states – finite naturally! When a symbol, a character from some alphabet say, is input to the machine it changes state in such a way that the next state depends only on the current state and the input symbol.

You can represent a finite state machine in a form that makes it easier to understand and think about. All you have to do is draw a circle for every state and arrows that show which state follows for each input symbol. For example, the finite state machine in the diagram has three states. If the machine is in state 1 then an A moves it to state 2 and a B moves it to state 3.

A Turing machine is a finite state machine that has an unlimited supply of paper tape that it can write on and read back. There are many formulations of a Turing machine, but essentially the machine reads a symbol from the tape, which is used as an input to the finite state machine. This takes the input symbol and according to it and the current state that it does three things:

1) it prints something on the tape
2) moves the tape right or left by one cell
3) changes to a new state

A Turing machine can also perform a special action – it can stop or halt – and surprisingly it is this behaviour that attracts a great deal of attention. For example, a Turing machine is said to recognise a sequence of symbols written on the tape if it is started on the tape and halts in a special state called a final state. What is interesting about this idea is that there are sequences that a Turing machine can recognise that a finite state machine can’t. For example, a finite state machine can recognise a sequence that has three As followed by three Bs e.g. AAABBB and so can a Turing machine. But only a Turning machine can recognise a sequence that has an arbitrary number of As followed by the same number of Bs. This at first seems very odd but a little thought reveals it to be quite reasonable, obvious even! To discover if the number of Bs is the same as the number of As you have to do something that is equivalent to counting them, or at least matching them up, and given there can be arbitrarily many As before you ever see a B you need unlimited storage to count or match them up. The finite state machine doesn’t have unlimited storage but the Turing machine does in the form of its tape!

At this point we could fall to arguing the impossibility of the Turing machine because its tape can’t be infinitely long. The machine doesn’t, in fact,  need an infinite tape, just one that isn’t limited in length. Imagine if you will that Turing machines are produced with a very long but finite tape and if the machine ever runs out of space you can just order some more tape. This is the subtle difference between the tape actually being infinitely long or just unlimited…

We could also start arguing that the Turing machine is not really of any importance because it is a very feeble machine but there are two reasons for not dismissing it. The first is that Alan Turing thought up the machine as a model for computation. He reasoned that any computation that could be performed by a human involved writing down intermediate results, reading them back and carrying out actions that depend only on what has been read and the current state of things. That is, the Turing machine is the simplest implementation of “computing” and informally we say that if something can be computed then it can be done using a Turing machine. It might take a little longer to work out an answer with a Turing machine than the latest Pentium based PC but that’s not the point. If it can be computed we accept the premise that it can be computed by a Turing machine even if we have to wait a while for it to finish.

The Universal Turing Machine

Now we come to the masterstroke of Turing machine theory – the Universal Turing machine. Suppose you have a Turing machine that computes something. It consists of a finite state machine, an initial state and an initialised tape. This information can be coded onto a new Turing machine tape – the description of the finite state machine can be written first as a table of symbols representing states and transitions to states. The initialisation information can then be written on the tape and the remainder of the tape can be blank and used as the original machine’s tape. Now all we have to do is to design a Turing machine that reads the beginning of the tape and uses this as a “lookup table” for the behaviour of the finite state machine. It can then use another special part of the tape to record the machine’s current state. It can read the symbols from the original machine’s initial tape, read the machine definition part of the tape to lookup what it should do next, and write the new state out to the working area. What we have just invented is a Turing machine that can simulate any other Turing machine – i.e. a Universal Turing Machine.

Just in case you hadn’t noticed a universal Turing machine is just a programmable computer and the description on the tape of another Turing machine is a program.

What is computable?

At this point it all seems very reasonable – anything that can be computed can be computed by a specific Turing machine. Even more generally, anything that can be computed can be computed by a universal Turing machine. This all seems innocent but there is a hidden paradox waiting to come out of the machinery and attack – and again this was the reason Turing invented all of this!

Consider the “halting problem”. This is just the problem of deciding if a given Turing machine will eventually halt on a specific tape. In principle it look reasonably easy. You examine the structure of the finite state part of the machine and the symbols on its tape and work out if the result is halting or infinitely looping.  Given that we claim that anything that can be computed can be computed by a Turing machine let’s suppose that there is just such a machine called “D”. This machine will read the description of any Turing machine, “T”, and its initial data from its tape and will decide if T ever stops. That is, the machine D itself comes to a halt in one of two states – either “T Halts” or “T doesn’t Halt”.

Now we make a small change to the machine D to produce machine E – by adding two additional states L and R. These are arranged so that if machine D reaches the original “Halt” state it loops forever round L and R, no matter what is on the tape.

Notice that if machine D can be built so can machine E and this machine simply stops if machine T would never stop and never stops if machine T stops. All this seems innocent but you might notice the trap built into machine E. Take machine E and create a tape TE which is a description of machine E suitable for a universal Turing machine. Now feed this tape into machine E itself and consider what will happen. If machine E comes to a halt on tape TE this means that the machine described by TE does not halt – but wait a minute the machine described by TE is machine E! If you try to wriggle the other way and say that machine E does not halt then this means that the tape describes a machine that does halt and again this machine is Turing machine E.

At this point you probably want to start to pick your way through this explanation to find the flaw and I have to admit that I have cut a few corners in the interests of simplicity but you can trust me that any defects can be patched up without changing the overall paradox. We are now left with the problem of interpreting these results and this isn’t so difficult. If machine D exists you can use it to construct a paradox and as paradoxes of this sort cannot exist – it is a “set of all sets” paradox – we have to conclude that machine D cannot exist. In other words, it is impossible to build a Turing machine that can solve the halting problem – and given we believe that anything that can be computed can be computed by a Turing machine we now have the unpleasant conclusion that we have found a problem that has no solution. We have found something that is beyond the limits of computation.

As soon as you have one the flood gates open and there turn out to be lots of non-computable problems – does machine T halt on tape TT, does machine T ever print a particular symbol, does T ever stop when started on a blank tape and so on.

Non-computable numbers

You can comfort yourself with the thought that these non-computable problems are a bit esoteric and not really practical – but there is more. We are all very smug about the ability to compute numbers such as pi to millions of decimal places, it seems to be what computers were invented for. The bad news is that there are non-computable numbers. To see that this is the case think of each Turing machine tape as being a number – simply read the binary number you get from a coding of its symbols. So to each tape there is an integer and to each integer there is a tape. The number R starts with a decimal point and has a 1 in decimal position n if the nth Turing tape represents a machine that halts when run on U, the universal Turing machine, and a 0 if it doesn’t halt. Clearly there is no Turing machine that computes R because this would need a solution to the halting problem and there isn’t one… R is a non-computable number but again you can comfort yourself with the idea that it is a bit strange. The really bad news is that it is fairly easy to prove that there are far more non-computable numbers than there are computable numbers. Just think about how many numbers there are and how many tapes – there is only a countable infinity of computable numbers but there is an uncountable infinity of numbers in total. Most of the world is outside of our computing…

<ASIN: 0470229055>