2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.


Further reading on probabilistic classes:

Randomized polynomial time class

Bounded error polynomial time class

$\endgroup$
  • $\begingroup$ So a PTM and NTM are both non-deterministic. While a PTM is a realisable model of computing in reality, an NTM is not. Is it because this "guessing" in the NTM is kind of esoteric? It's still quite weird that the NTM just guesses the correct answer, let me will look for a more formal definition. $\endgroup$ – WeCanBeFriends Jun 19 at 21:37
  • $\begingroup$ @WeCanBeFriends Another way of looking at non-deterministic models like the NDTM is that when there is a choice the NDTM clones itself and its copies pursue all of the decision branches in parallel. In the maze analogy, you go left while your identical twin goes right. Remember this is only a model so we have unlimited resources. $\endgroup$ – gandalf61 Jun 20 at 8:29
  • $\begingroup$ @gandalf61 Got it, I was refraining from using words such as parallel because afaik, it's not related to anything like parallelism. I'm still looking into why this model is important, maybe just for classifying problems to be in NP? $\endgroup$ – WeCanBeFriends Jun 20 at 10:49

Your Answer

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

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