Why is the tape not part of the definition of a Turing Machine?

Question

I've wondered why the tape/tapes are not part of the formal definition of a Turing Machine. Consider, for example, the formal definition of a Turing machine on Wikipedia page. The definition, following Hopcroft and Ullman, includes: the finite set of states $Q$, the tape alphabet $\Gamma$, the blank symbol $b \in \Gamma$, the initial state $q_0\in Q$, the set of final states $F\subseteq Q$, and the the transition function $\delta:(Q\backslash F)\times \Gamma\rightarrow Q\times\Gamma\times\{L,R\}$. None of which is the tape itself.

A Turing Machine is always considered to work on a tape, and the transition function is interpreted as moving its head, substitution of symbol and changing state. So, why is the tape left out of the mathematical definition of a Turing machine?

From what I can see, the formal definition in itself doesn't seem to imply that the Turing Machine operates like it's often described informally (with a head moving around on a tape). Or does it?

Answer 1

To formally define an instance of a Turing machine (not the general concept) you don't need to explicitly mention the tape itself, or its contents. To denote a configuration of this particular machine, or a computation performed by it, that is when you need some form of notation to describe the contents of the tape.

Answer 2

It's a bit gray area, but I would say the definition splits the model from the instance. If you wish to have a simple idea in mind think about hardware vs software.

The model is the hardware: The is one head. There is one tape. The tape is infinite on one side and contains blanks (besides the input). The head can move one step at a time.

The instance is the software: the input dictates what the tape holds at the beginning, the state/transition function tells how the head moves and how the machine "works". The final states give the meaning of success/failure.

Both parameters are configurable --- both can be changed. Alternative models exist with two tapes, two heads, two-sided tapes, non-empty tape, etc. But once you fix the model, you need to settle the other "configurable" parameters, as the number of possible states, and transition function.

What makes a parameter part of the model rather than part of the instance? That's just gray area, and I don't think there's a good answer to it (maybe I'm wrong. Anyone?). It feels that separating to "Hardware"/"Software" makes the most sense to classifying parameters as part of the model or part of the instance, but we can imagine other universes in which this classification is different (e.g., where the TM is a 8-tuple, which also contain $P$=the position of the head at the beginning, or $M$=the number of tapes, or $pattern$=a pattern that repeatedly appears on the tape after the end of the input, etc.)

Answer 3

Here already good answers, but I try to make a succinct one.

Definitions shouldn't be excess or verbose.

Indeed, Turing machine definition defines the tape abstraction as well. The q0 - is the start of the tape. The alphabet is a content of the tape. And δ:(Q∖F)×Γ→Q×Γ×{L, R} states that the tape has left and right and infinity in the both directions.

So, tape, head, moves just human-friendly representations of the model, they're already in the mathematical model, but they aren't a formal model themselves.

Answer 4

Les provides a concise and correct answer: mathematical definitions are as concise as possible, and explicitly including an infinite tape into a definition of a Turing machine would make its definition much less concise, so we don't.

This doesn't answer the question: why? How can the definition exclude the infinite tape when we need one?

The answer: we don't. In a sense, Turing machines don't actually require infinite tapes, and their definition makes this clear.

By definition, a Turing machine's move takes the machine from one configuration to another; a configuration includes a finite string, which we regard as a finite fragment of written tape. Each move either moves the tape head by one position or overwrites the symbol under the tape head. However - and this is essential for its operation:

• whenever we move off that finite piece of string, we assume the symbol under the tape head is $b$, the blank symbol.
• there is no bound on how often we can do this.

So in order for arbitrary Turing machines to operate indefinitely, an infinite supply of blank tape cells is required at both ends. Meanwhile, at any point, its configuration, describing the stretch of tape it has written on, is always finite: after $n$ steps, the tape head can never have strayed farther than $n$ cells from its starting point.

One way of rephrasing this is to say: the machine operates on an infinite tape, entirely filled with blanks, except for a finite fragment that its tape head is on. This is what most explanations say.

Another way of rephrasing this is to say: the machine operates on a finite tape, extended with blanks whenever its head moves off the tape at either end.

These are both valid ways of conceptualizing how the machine operates: in both cases, if you actually had a machine operating like that, it would correctly implement a Turing machine.

If all you're interested in is teaching students how Turing machines work, it probably doesn't matter which conceptualization you pick.

However, I think the first conceptualization is a mistake, for several reasons:

• It is unrealistic. We can't actually build a machine with an infinite tape. We can build a machine with a finite tape extended on request.
• It is counterintuitive. We don't think of machines performing tasks arbitrarily often as containing an infinite amount of resources. For instance, we don't think of a photocopier as containing an infinite amount of copying paper. Turing machines model the activity of computing. They model what would happen if we replaced a computer (which, at the time of its invention, was a woman performing calculations on paper) with a machine capable of performing arbitrary programmable computations. We don't think of that woman as containing an infinite amount of paper. Rather, we assume she'll be supplied with whatever amount of paper she needs, and we regard a failure to do so as a failure of the environment, rather than saying such a woman can't possibly exist. Why not do the same for the machine?
• It invites incorrect conclusions. I've seen this a lot. For instance:
  • People say Turing machines cannot actually be built, while finite state machines can. Well, we cannot build arbitrarily large finite state machines any more than we can supply arbitrary amounts of tape to a Turing machine.
  • People say Turing machines don't model computers correctly, while finite state machines do. This serves to make an important point: if all we're interested in is using a machine for deciding input languages, then a computer operating only on its (fixed) internal storage can fully implement any finite state machine up to a certain size, while it cannot fully implement most Turing machines, as it will run out of internal storage for many of them. However, this is often generalized by saying: computers are finite state machines, which is misleading:
    • It doesn't paint a realistic picture of most computer programming. Indeed, dataflow programming is in fact based on finite state machines, but traditional imperative programming is not; it uses programs that are much closer to Turing machine instances.
    • In practice, computers also interact with external sources of input, output and storage that aren't fixed in size.
    • Turing machines aren't supposed to model computers in the first place; they model arbitrary computing.

To sum up: the idea of Turing machines using or containing an infinite tape serves to emphasize an important technical point, but it is not necessarily the most intuitive way of thinking about Turing machines, and it invites certain incorrect conclusions. Use with caution.