What's the difference between a non-deterministic turing machine and a deterministic turing machine?

5.4k Views Asked by At

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?

1

There are 1 best solutions below

0
On

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.