HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
definitionwhytheparttapemachineturingnot

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#45589, answer score: 8

Revisions (0)

No revisions yet.