# Non-Deterministic Turing machine vs Probabilistic Turing Machine vs Deterministic Turing Machine

What is the difference between a Non-Deterministic Turing machine, Probabilistic Turing Machine and a Deterministic Turing Machine ?

A Turing machine is a computation model in theory only, able to simulate any computer algorithm. By formally defining this model mathematically, Its possible to draw conclusions and limits regarding the abilities of our computers.

There are many more models, and much more literature about each of them, but below is a short review of the three mentioned in your question

Deterministic Turing Machine (DTM):

For any given state $$Q_i$$ the machine is presently at, and for any given symbol under the input alphabet $$\Sigma$$ the head is at, there is exactly one action the machine can perform.

It means in every step, the transition (and write operation) is well established, or deterministic, under a certain set of rules predefined into the machine.

Non-Deterministic Turing Machine (NTM):

A machine like the DTM, with the important exception that in every step, it may make more than one transition. So for input symbol $$s$$ and state $$Q_i$$, it may transition to to $$Q_j$$, but it may also transition to $$Q_k$$ and so forth.

Since in no step is the transition well established, we say the NTM "guesses" the best transition that eventually leads to an accepting state $$Q_{F}$$ (if such a transition path exists).

Imagine being in a maze, and constantly having to decide whether to turn left, or right. If you always guessed the correct choice, then you will find the find the quickest way out possible (if there was one).

Probabilistic Turing Machine (PTM):

A machine like the NTM, only its transition is subject to a probabiliy function (that is well established) and not "guess" like the NTM. For example, suppose the current input symbol is $$s$$ and state $$Q_i$$, a transition can be defined as follows:

Flip 2 coins.

• If the result is ($$head$$, $$head$$), move to state $$Q_j$$
• Else, move to state $$Q_k$$

Unlike the DTM, we cannot say we know how the machine will act given the situation, since we don't know what the coin flip will show. However, its also not as "lucky" as the NTM, and we can often measure accurately the probability of a mistake.