The Turing machine can compute anything that can be computed. It is the very definition of computation and the fundamental tool for reasoning about computers. You really need to know what it is all about. Here is an illustrated guide.

You could say that the computer was invented twice – once by Charles 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 ever 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 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, i.e. a Turing machine without a tape, 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.That is a Turing machine is more powerful than a finite state machine because it can count.

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 input A symbols even 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!

Infinite or just unlimited

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 and this is a subtle difference.

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 difference between the tape actually being infinitely long or just unlimited…

This idea is subtle and if you want to know more read: The Programmer's Guide To The Transfinite

Feeble or All Powerful?

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

That is a Turing machine is about what can be computed in principle.

It actually defines computing, computation and what is computable.

Any system that can compute anything a Turing machine can is called Turing complete. There are lots of things that are very simple that can be proved to be Turing complete and so the ability to compute things seems to be all round us.

What is more so far no system has been found that can goes beyond a Turing machine. That is if you have a system that can compute something then a Turing machine can compute it as well. Any example that you find that seems to go beyond the computing abilities of a Turing machine i.e. can compute something that a Turing machine cannot always relies on something non-physical that means it cannot be built exactly as described. Usually the non-physical aspect involves measuring something with infinite accuracy or working infinitely fast.

In this sense a Turing machine is a model of what is physically computable.

Notice that while all machines are equal in terms of what they can compute they are not equal in terms of how fast they get to an answer. You can build a faster Turing machine but not one that can compute something that goes beyond a Turing machine.

<ASIN:0753822008>

<ASIN:0099116413>

<ASIN:0470229055>

<ASIN:3211826378>