2

From what I understood, it seems that the difference is that a NTM can have 2 inputs for which there is a different output or direction.

For example, state A for input 1 can result in output 0 and left, o output 1 and right.

Is that all, or am I missing something?

john
  • 21
  • found simple explanation here https://stackoverflow.com/questions/13524011/i-do-not-understand-the-concept-of-non-deterministic-turing-machine – roottraveller Jul 14 '17 at 07:32

1 Answers1

1

Yes, given a state $p$ and tape symbol $a$, the machine can enter state $q$, write symbol $b$, and move left or right. For a DTM, there is only one thing it can do. But for an NTM, there are multiple transitions it can do.

A more symbolic way of saying this is that the transition function for a DTM is $\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$, but for an NTM, it is $\delta : Q \times \Gamma \to \mathcal{P}(Q \times \Gamma \times \{L, R\})$, where $\mathcal{P}$ is the power set operator.

Henry Swanson
  • 12,972