[Solved]: Is there a single valid definition for a Turing Machine, or is it mutable?

Problem Detail: 

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.

Asked By : agent154

Answered By : Peter Shor

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9168