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$
  • $\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
7
$\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
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$
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.