Is there a single valid definition for a Turing Machine, or is it mutable?

Question

I'm just learning about Turing Machines, and I'm a bit confused by the difference in formal description between Wikipedia and my textbook.

My textbook says the following:

$$M=\langle Q,\Sigma,\Gamma,\delta,q_{0},q_{accept}, q_{reject} \rangle$$

where:

1. $Q$ is the set of states,
2. $\Sigma$ is the input alphabet not containing the blank symbol $\sqcup$,
3. $\Gamma$ is the tape alphabet, where $\sqcup\in\Gamma$ and $\Sigma\subseteq\Gamma$,
4. $\delta: Q\times\Gamma\to Q\times\Gamma\times\{L,R\}$ is the transition function,
5. $q_0\in Q$ is the start state,
6. $q_{accept},q_{reject}\in Q$ are the accepting and rejecting states, respectively, and $q_{accept}\neq q_{reject}$

While Wikipedia states

Hopcroft and Ullman (1979, p. 148) formally define a (one-tape) Turing machine as a 7-tuple $M= \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$ where

• $Q$ is a finite, non-empty set of states
• $\Gamma$ is a finite, non-empty set of the tape alphabet/symbols
• $b \in \Gamma$ is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
• $\Sigma\subseteq\Gamma\setminus\{b\}$ is the set of input symbols
• $q_0 \in Q$ is the initial state
• $F \subseteq Q$ is the set of final or accepting states.
• $\delta: Q \setminus F \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}$ is a partial function called the transition function, where L is left shift, R is right shift. (A relatively uncommon variant allows "no shift", say N, as a third element of the latter set.)

There are obviously a few similarities, but there are a few differences as well. Namely the ordering of the items in the 7-tuple $M$. Also, my textbook has three entries for separate special states, and the Wikipedia entry has only two - My book doesn't have a special element just for the blank character.

Answer 1

The ordering of the items in the 7-tuple M is completely immaterial to the behavior of the Turing machine. There is no "correct" or "incorrect" ordering; but I would say that both orderings are essentially the same definition. And I don't see that the blank character is treated any differently in the two definitions. In both, it's part of the tape alphabet but not the input alphabet.

For the two definitions to be effectively different, you would need to find a difference that does not correspond to a re-ordering of the 7-tuple, or is just in the wording of how the blank symbol is treated.

The only actual difference between the two definitions seems to be that your book has $q_{\mathrm{accept}}$ and $q_{\mathrm{reject}}$ as the halting states, while Wikipedia permits a general set $F$ of halting states. This is because your book only deals with Turing machines that compute languages (so for every string $x$, either $x \in L$ or $x \not\in L$) while Wikipedia also wants to handle Turing machines that compute functions. For a Turing machine that computes a function, you can assume that there is only one final state, $q_{\mathrm{halt}}$; the value of the function will be written on the tape when the Turing machine halts.

Answer 2

There are several valid definition of a Turing machine but they (the TM's) are all equivalent in power (they all compute the same functions). You could use the original definition (coined by Alan Turing himself in his paper "Computing Machinery and Intelligence". He describes the Turing machine in English. It's what a Turing machine consists of that matters not how the pieces are ordered.

Answer 3

As mentioned before by other people the are variety of Turing machines with a little bit different definitions like two-way infinite tapes, arbitrary numbers of read-write heads, multiple tapes, ... See this link. The point is that all of them are "equivalent" in theory. It's up to you which is better for your problem.