According to book by Peter Linz, the transition function for non deterministic Turing machine is:

$Q\times \Gamma\rightarrow 2^{Q\times \Gamma\times \{L,R\}}$

  • $Q$ is a set of states
  • $\Gamma$ is a set of tape alphabet
  • $L$ is a movement of head to left
  • $R$ is a movement of head to right

whereas the definition given by wikipedia is

$Q\times \Gamma \rightarrow (Q\times \Gamma \times \{L,S,R\})$

Book by Ullman et. al. says above transition function is of "Turing machine with Stay option". Ullman's book does not give any formal definition for non deterministic Turing machine. So which definition is correct? I feel Peter Linz's book gives correct definition. Or both are same?

  • $\begingroup$ With your second definition you obtain a deterministic Turing machine. You would get a non-deterministic TM with $Q \times \Gamma \times Q \times \Gamma \times \{L, S, R\}$ or like in Linz' notation $2^{Q \times \Gamma \to Q \times \Gamma \times \{L, R\}}$. It is not hard, however, to simulate a "Turing machine with stay option" on a "Turing machine without stay option" and vice versa. This would be an easy homework exercise, so I encourage you to write it down :) $\endgroup$ – ttnick Jun 24 '18 at 17:57
  • $\begingroup$ Dont you think first two sentences of your comments contradicts each other? First sentence says $Q×Γ→(Q×Γ×{L,S,R})$ is deterministic. Second sentence says its non deterministic. Peter Linz's book says its (TM with stay option) deterministic. So wikipedia is wrong, correct? $\endgroup$ – anir Jun 24 '18 at 18:13
  • $\begingroup$ Ah, I'm sorry the Linz part should be $Q \times \Gamma \to 2^{Q \times \Gamma \times \{L, S, R\}}$. With both you get a non-determinsitic TM. I cannot find anything wrong with the wikipedia definition. They introduce a non-deterministic transition relation $\delta$ and say it is deterministic if $\delta$ is the graph of a function. $\endgroup$ – ttnick Jun 24 '18 at 18:24
  • $\begingroup$ Do you mean Peter Linz missed $S$ in $Q \times \Gamma \to 2^{Q \times \Gamma \times \{L, \color{red}{S}, R\}}$? $\endgroup$ – anir Jun 24 '18 at 18:32
  • $\begingroup$ @anir What's written on Wikipedia is $\delta\subseteq(Q\setminus A\times\Sigma)\times(Q\times\Sigma\times\{L,S,R\})$ not what you stated (even ignoring the use of $\Gamma$ instead of $\Sigma$ which presumably you did for consistency). It is saying $\delta$ is a relation not (necessarily) a function. $\endgroup$ – Derek Elkins left SE Jun 24 '18 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.