Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 10 down vote accepted

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.

share|improve this answer
    
It seems redundant to have a separate $\Sigma$ and $\Gamma$... if $\Gamma$ is just $\Sigma\cup \{blank\}$... At least in the examples I've seen this is the case. –  agent154 Jan 26 '13 at 15:45
    
I agree—it is certainly redundant to have Σ, Γ, and {blank} all defined in the 7-tuple. –  Peter Shor Jan 26 '13 at 15:53
3  
@PeterShor I think $\Sigma$ and $\Gamma$ could differ by elements other than $blank$. $\Gamma$ contains the set of things you can read/write; these serve as markers/indicators in general (a symbol could indicate when to stop moving to the left in some $TM$, etc$\dots$). $\Sigma$ is what the alphabet of your language is made of. You don't want to include markers in your alphabet because that could change the language. It makes more sense to separate the two. –  saadtaame Jan 26 '13 at 16:28
4  
@saadtaame; you're right; I wasn't thinking. Having Turing machines with work symbols that aren't input symbols is a perfectly reasonable thing to do (and will make programming them quite a bit easier in some cases), although it doesn't increase the power of Turing machines. –  Peter Shor Jan 26 '13 at 16:33

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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