Turing Machine (thing)

The machine has a tape head that can read and/or write a symbol on a tape. It can also shift the tape one position to the left and to the right.

At any time, the machine is in some internal state.

The machine's operation is defined by a finite set of transitions. A transition is specified by four items: a state, a symbol, another state, and an action. The transition is applicable whenever the machine is in the first state, and the head is on the specified symbol. It is applied by moving into the second state and performing the action. The action is either a move to the left, or a move to the right, or a symbol (to be written on the tape, overwriting whatever symbol was there).

That's it. Anything that behaves according to these specifications is a Turing machine. The transitions completely define the machine's operation. Different Turing machines differ by having different transition tables. The set of transitions must be finite, implicitly restricting the set of internal states and the set of different symbols the machine can read or write to be finite as well.

If no two transitions share the same first state,symbol pair, which ensures that at most one transition is applicable at any point in the computation, the Turing machine is said to be deterministic.

A computation of a Turing machine is a (finite) sequence of valid applications of transitions. Clearly, the set of possible computations depends on the initial tape content. The Turing machine may end up in a state, above a symbol, for which no applicable transitions exist. The computation is finished: the Turing machine halts. It is also possible for a Turing machine never to halt.

For example, consider the Turing machine without any transitions. This machine, regardless of the tape contents, will always halt immediately. Now consider the machine with one transition: in state s, on symbol a, it will go to state s and write symbol a. This Turing machine will always halt whenever it is started with its tape head on a symbol other than a; but when started on an a, it will never halt.

The next section is going to be tricky: it deals with a pet peeve of mine. I know it's a pet peeve because whenever I bring it up people will disagree with me, refuse to understand the point, or refuse to understand its relevance. So I'm interested in your views on the matter.

Note that a Turing machine is a simple device that could actually be built: its mathematical model is realistic. Clearly, a real-life Turing machine could malfunction or break down, but it is often argued that Turing machines are inherently unrealistic because they contain an infinite tape. This is false.

It is false for two reasons:

• the tape isn't part of the machine
• the tape doesn't need to be infinite

As you can see in the definition above, the Turing machine itself consists of a tape head, some way of holding a state, and a mechanism to impose a set of transition rules. It assumes the presence of a tape on which it can move its head and on which it can read and write its symbols, but the tape is not actually part of the machine. It is neither part of it mathematically (there is no mention of the tape in the mathematical definition of a TM) nor conceptually. Sometimes it is argued that a Turing machine models computers; certainly, with computers, we consider internal memory and disk space part of the machine, so analogously, the tape should be considered part of a Turing machine. But a Turing machine doesn't model computers, it models the activity of computing. When we think of that activity, we do not consider it to be restricted to a fixed amount of working memory. When we think of a person conducting computations, we do not assume the person is operating with a given, fixed amount of resources such as working memory or scrap paper. What is more, we do not consider scrap paper to be part of the person. Likewise, a Turing machine does not contain the tape it uses.

From the definition above you can also see that the computation of a Turing machine will never use more than a finite amount of tape. To be exact, after n steps it can never have strayed further than n positions from where it started. It has never looked anywhere else on the tape. So the tape doesn't need to be infinite: in actual practice, it can be extended whenever the tape head reaches an end.

However, while we never actually need an infinite amount of tape, it is fundamental to computing with Turing machines that we can supply arbitrary amounts of tape as the need arises. For some Turing machine configurations, it is possible to calculate a maximum stretch of tape in advance such that the machine's operation will never run off of it, no matter what the initial tape contents are; but this is not true in general. As a matter of fact, some computational tasks can only be implemented by Turing machines with the property that, no matter how much tape you provide initially, even if you only decide on the amount after looking at the initial tape contents, the machine may still turn out to run off the end of it when put to work. There is a hard mathematical proof of this fact. So it is fundamental to the computing power of Turing machines that they can write on an arbitrarily large amount of tape; that we cannot even predict how much tape will be needed. This is what books and articles about Turing machines (such as the writeups below) really mean to say when they (again, incorrectly, in my opinion) write that Turing machines "have" an "infinite" amount of tape.

Many things can be said about the details of computing with Turing machines. This leads to general conclusions about the power of computing in general (computability and decidability), but we can also study certain classes of Turing machines, restricted in the way they use their tape, and the expressive power that results from these restrictions: the restrictions on which most research has focused are summarized in the Chomsky hierarchy.