11
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ next section in wikipedia says: "In the words of van Emde Boas (1990), p. 6: "The set-theoretical object [his formal seven-tuple description similar to the above] provides only partial information on how the machine will behave and what its computations will look like."" it is quite similar to the software/ hardware dichotomy/ synergy/ interdependency. software assumes a particular hardware that it runs on. if someone discovered some software in the future, they could not understand its "meaning" without also understanding the hardware it runs on. $\endgroup$ – vzn Sep 4 '15 at 20:32
  • $\begingroup$ Why is the road not part of the car? $\endgroup$ – Andrej Bauer Jan 19 at 22:41
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So a tape is needed to define a configuration and computation, only ? $\endgroup$ – Shuzheng Aug 26 '15 at 15:38
  • $\begingroup$ Yes, the machine just operates on the tape. Different contents of the tape do not create different machines. $\endgroup$ – André Souza Lemos Aug 26 '15 at 15:56
  • 1
    $\begingroup$ In other words: the question only cites the syntax of TMs. Only when defining semantics does the tape enter the picture. (Analogy: the syntax definition of C (or any other programming language) does not mention the assumed hardware architecture/OS/CPU instruction set either.) $\endgroup$ – Raphael Aug 27 '15 at 14:08
  • $\begingroup$ Even semantically, it's most natural to think of the machine remaining the same machine even when the tape contents change. (Formally, this isn't the case, as the initial contents are part of the machine's definition.) $\endgroup$ – reinierpost Jan 6 at 19:07
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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 overwrite 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.
  • we can do so infinitely often.

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 two 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 misleading 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 arbitrary 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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.