What is the difference between non-determinism and randomness?

I recently heard this -
"A non-deterministic machine is not the same as a probabilistic machine. In crude terms, a non-deterministic machine is a probabilistic machine in which probabilities for transitions are not known".

I feel as if I get the point but I really don't. Could someone explain this to me (in the context of machines or in general)?

Edit 1:
Just to clarify, the quote was in context of finite automaton, but the question is meaningful for Turing machines too as others have answered.

Also, I hear people say - "... then I choose object x from the set non-deterministically". I used to think they mean - "randomly". Hence the confusion.

• In computer science, people occasionally use the term "deterministic" to emphasise that an algorithm is not randomised. Hence the confusion: deterministic means non-randomised, but non-deterministic does not mean randomised. Commented Aug 26, 2010 at 18:05
• Commented Oct 14, 2012 at 23:53
• This question leads me to this corner of SE... Commented Jun 19, 2015 at 17:49

It's important to understand that computer scientists use the term "nondeterministic" differently from how it's typically used in other sciences. A nondeterministic TM is actually deterministic in the physics sense--that is to say, an NTM always produces the same answer on a given input: it either always accepts, or always rejects. A probabilistic TM will accept or reject an input with a certain probability, so on one run it might accept and on another it might reject.

In more detail: At each step in the computation performed by an NTM, instead of having a single transition rule, there are multiple rules that can be invoked. To determine if the NTM accepts or rejects, you look at all possible branches of the computation. (So if there are, say, exactly 2 transitions to choose from at each step, and each computation branch has a total of N steps, then there will be $2^N$ total brances to consider.) For a standard NTM, an input is accepted if any of the computation branches accepts.

This last part of the definition can be modified to get other, related types of Turing machines. If you are interested in problems that have a unique solution, you can have the TM accept if exactly one branch accepts. If you are interested in majority behavior, you can define the TM to accept if more than half of the branches accept. And if you randomly (according to some probability distribution) choose one of the possible branches, and accept or reject based on what that branch does, then you've got a probabilistic TM.

• Kurt, can you please explain how the 2^N figure was arrived at. If for every branch there are 2 possibilities and there are N stages like that to reach the solution wouldn't that make it 2^(N+1)-1. I am trying to think of it like a graph and I could be wrong. Could you please explain how you arrived at the 2^N number. Thank you. Commented Aug 27, 2010 at 16:32
• Well, if you represent the computation as a tree, with the root representing the initial configuration as step 0, then after N steps you've got 2^N leaves, and what I'm calling a branch is a path from the root to a leaf. It's true that you'll have 2^(N+1)-1 total nodes, representing all the possible configurations at some point in the computation. I hope my terminology is okay!
– Kurt
Commented Aug 27, 2010 at 20:43
• All sciences use the same definition of nondeterminism unified on the concept of unbounded entropy. Unpredictable outcomes in all sciences are due to the inability to enumerate a priori all possible outputs of an algorithm (or system) because it accepts unbounded states, i.e. NP complexity class. Specifying a particular input to observe whether it halts and noting that the result is idempotent is equivalent in other sciences to holding the rest of the entropy of the universe constant while repeating the same state change. Computing allows this entropy isolation, while natural sciences don't. Commented Dec 11, 2015 at 20:07
• @ShelbyMooreIII No. You have misunderstood the concept of nondeterminism that appears in computer science. Commented Dec 11, 2015 at 22:51
• @DavidRicherby sorry David. Go to the other thread and see that I have resoundingly refuted you. You can try to refute the logic I have presented there. Just asserting without evidence and explanation doesn't win you any truth. Commented Dec 11, 2015 at 23:53

In the context of Turing Machines, "non-deterministic" really means "parallel". A randomized algorithm can randomly explore the branches of the computation tree of a non-deterministic Turing machine, but a non-deterministic Turing machine can explore them -all- at the same time, which is what gives it its power.

In other contexts (I can't tell from your quote if you are talking about Turing Machines), a randomized algorithm might intentionally be using randomness, whereas an algorithm that you wanted to be deterministic might end up exhibiting non-determinism because of a bug...

In response to your edit, when people say "choose an element from a set non-deterministically", its possible they might just mean "randomly". However, it is also possible that they mean "magically choose the -right- element from the set". A common way to view non-deterministic turing machines is that they first magically "guess" a solution, and then check its correctness. Of course, you can view this magic guess as just the result of checking all possibilities in parallel.

• Related to "magically choose the right element": When the word 'nondeterminism' is used in this sense people sometimes qualify it with 'angelic'. There's also 'demonic' nondeterminism. (Still, as you say, the essence is that stuff happens in parallel.) Commented Aug 26, 2010 at 13:45

There are several different contexts where “deterministic”, “random” and “non-deterministic” mean three different things. In contexts where there are multiple participants, such as security and concurrency, the intuition is often something like:

• deterministic means “I get to choose”

• non-deterministic means “someone else gets to choose”

• random means “no one gets to choose”

A few examples:

1. [concurrency, random] Consider a networking protocol such as Ethernet, where multiple nodes can send a message at any time. If two nodes send a message at very close intervals, there is a collision: the messages overlap and are unreadable. If a collision happens, both nodes must try sending the messages again later. Imagine you're writing the specification of Ethernet. How do you specify the delay between retries? (The delays had better be different or there'll be a collision again!)

• deterministic: define an algorithm that both nodes must use. This is not done for Ethernet because in order to give different results, the algorithm would have to privilege one node over the other (for any given message content), and Ethernet avoids doing that.

• non-deterministic: let each implementer decides. This is no good because the implementers on both nodes may choose the same algorithm.

• random: each node must select a delay value at random (with a specified distribution). That's how it works. There is a small probability that the two nodes choose the same delay and there's another collision, but the probability of success increases asymptotically towards 1 as the number of retries increases.

2. [concurrency, nondeterministic] You write a concurrent algorithm. In a specific situation, there can be a deadlock. How can you prevent the deadlock from occurring? That depends on what kind of scheduling your concurrency environment has.

• deterministic: the scheduler always switches between threads at certain well-defined points, e.g. only when the code yields explicitly. Then you simply arrange for the threads not to yield at bad times.

• random: the scheduler is guaranteed to switch threads randomly. Then a viable strategy can be to detect the deadlock if it occurs, and restart the algorithm from the start.

• non-deterministic (most schedulers are like this): you don't know when the scheduler will switch between threads. So you really have to avoid the deadlock. If you tried to detect and restart like in the random case, you run the risk that the scheduler will schedule your threads in exactly the same way again and again.

3. [security, random] You write an application with a password prompt. How do you model an attacker?

• deterministic: the attacker always tries the same passwords. That's not a useful model of an attacker at all — attackers are not predictable by definition.

• nondeterministic: the attacker knows your password somehow and enters it. This shows the limitation of passwords: they must be kept secret. If your password is secret, this attacker is unrealistic.

• random: the attacker tries passwords at random. In this case, this is a realistic model of attacker. You can study how long it would take for the attacker to guess your password depending on what random distribution he uses. A good password is one that takes long for any realistic distribution.

4. [security, nondeterministic] You write an application, and you worry that it may have a security hole. How do you model an attacker?

• deterministic: the attacker knows everything you know. Again, that's not a useful model of an attacker.

• random: the attacker throws random garbage and hopes to make your program crash. That can be useful sometimes (fuzzing), but the attacker might be more clever than that.

• non-deterministic: if there's a hole, the attacker will find it eventually. So you'd better harden your application (raise the intelligence requirement for the attacker; note that since it's an intelligence requirement rather than a computation requirement, this counts as non-deterministic until AI comes along), or better, prove that there is no security hole and therefore such an attacker doesn't exist.

• Correction revolves around the missing word prove in your statements: Deterministic is “I can prove I am choosing (i.e. fully specifying the result which terminates on my input in the P complexity class)”, Nondeterministic is “I can't prove I am choosing (i.e. proof of termination is undecideable in NP complexity class)”, and random is “I can prove that I get to choose ½ of the time (i.e. ZPP complexity class)”. Commented Dec 11, 2015 at 19:38
• @ShelbyMooreIII I don't understand where you're getting at. Determinism is not, in general, about proving that something is indeed deterministic, or about some problem being in a certain complexity class. Furthermore, complexity classes aren't about the system itself being able to prove something about its determinism (most problems don't even have a notion of proving inside the system!). Commented Dec 11, 2015 at 20:35
• Nondeterminism is always the result of unbounded entropy, thus another way of say this is that I can't prove I am choosing the result (because I can't prove my choice will terminate). All I can do is try, which means I must enumerate every choice I want to make before I know if it will terminate. Whereas with determinism, I can prove I choose the result bcz it must terminate. Randomization is where I can prove I only get to choose a random amount of the time because some of the entropy is not under my control. If I know the amount not under my control, I can prove precise the statistics of. Commented Dec 11, 2015 at 22:20
• Agreed it is not the complexity class NP that gives rise to nondeterminism, rather NP is a dependency. Turing-complete is an example of nondeterminism. Plz see my comment under Kurt's answer, as well my answer on the related thread. My point to you is about what precisely is proven & unpredictable for the terms deterministic, nondeterministic, & random. It is all about the entropy (& not about the bass) Commented Dec 11, 2015 at 22:27

An example to make things clearer:

Say you have to pick a door to open among 10000 doors (say there is a prize behind one of the doors). Choosing randomly means you would choose one out of the 10000 doors and enter it. If there is a prize behind only one door, you will most probably not find it. A non-deterministic machine would enter all 10000 doors simultaneously. If there is a prize anywhere, the non-deterministic machine will find it.

• Alternately, a non-deterministic machine would only open one door, but it would always be the right one. Commented Aug 26, 2010 at 20:21
• Yes, exactly. That would be the "luckiest possible guesser" characterization of non-deterministic machines. Commented Aug 27, 2010 at 2:30
• @RobinKothari:"Alternately, a non-deterministic machine would only open one door, but it would always be the right one".And "A non-deterministic machine would enter all 10000 doors simultaneously"?--Which one is correct? Commented Mar 21, 2014 at 16:09
• @tan: Both are correct interpretations. Unlike deterministic and randomized machines, which are physically realizable, a non-deterministic machine is an imaginary object. So you can imagine it however you like, the point is that it always finds the right door. Maybe it's the best guesser, maybe someone secretly told the machine where the prize was, maybe it just checks all doors magically, etc. Commented Mar 21, 2014 at 17:48

Definition of Non-Deterministic Turing Machine: A Turing machine which has more than one next state for some combinations of contents of the current cell and current state. An input is accepted if any move sequence leads to acceptance.

Definition of Probabilitistic Turing Machine: A nondeterministic Turing Machine (TM) which randomly chooses between available transitions at each point according to some probability distribution.

Probabilistic Turing Machine is a Non-Deterministic Turing Machine that can make mistakes.

I prefer the following definition:

There is no such thing as a probabilistic Turing machine! There are only deterministic machines (in every step a single possible follow-up state) and non-deterministic machines (in every step a constant number of possible follow-up states).

Non-determinism works as follows: Consider a non-deterministic machine which halts on each input (possible if problem is decidable), where each possible computation uses the same number of steps, and where each step has exactly 2 possible follow-up states (both not really a restriction). As in the definition of NP, a nondeterministic machine accepts an input if there exists at least one possible accepting computation, and it rejects the input if all computations reject.

Randomness comes into play as follows: You can choose uniformly at random a single path of computation from such a non-deterministic machine as stated above. You accept if and only if this randomly chosen path of computation accepts. This randomized approach "solves" your problem if, with overwhelming probability, this answer is correct.

So the difference between non-determinism and randomness is whether you are looking for the mere existence of a correct Yes-answer (and reliable No-answers), or whether you are interested in solving your problem "most of the time".

• -1 Errors in your first paragraph. Probabilistic Turing machines exist and sample a coin toss from external entropy, c.f. the ZPP complexity class. Non-determinism has an unbounded not a finite number of alternative states, c.f. the NP complexity class. Determinism is the P complexity class and you did get that correct. Commented Dec 11, 2015 at 19:44
• I think you are misreading my answer. I argue that you do not need any different machine (with coin-tossing or other capabilities) than an "ordinary" non-deterministic TM to define probabilistic complexity classes. You may just as well make use of an NTM and just use a different definition of acceptance, namely a definition where "most computational paths accept the input", as opposed to "there exists at least a single accepting path for the input".
– MRA
Commented Dec 16, 2015 at 16:30

To keep it simple: a non-deterministic machine can optimally choose the outcome of each coin flip (if you like the analogy with a probabilistic machine). You might also imagine that it executes the computation for each outcome of the coin flip in parallel.

Stepping backwards during debugging as a motivation for non-determinism

The notion of a non-deterministic machine suggests itself when you wish to step backward (in time) through a program while debugging. In a typical computer, each step modifies only a finite amount of memory. If you always save this information for the previous 10000 steps, then you can nicely step both forward and backward in the program, and this possibility is not limited to toy programs. If you try to remove the asymmetry between forward steps and backward steps, then you end up with the notion of a non-deterministic machine.

Similarities and differences between non-determinism and randomness

While probabilistic machines shares some characteristics with non-deterministic machines, this symmetry between forward steps and backward steps is not shared. To see this, let's model the steps or transitions of a deterministic machine by (total or partial) functions, the transitions of a non-deterministic machine by (finite) relations, and the transitions of a probabilistic machine by (sub)stochastic matrices. For example, here are corresponding definitions for finite automata

• a finite set of states $Q$
• a finite set of input symbols $\Sigma$
• deterministic: a transition function $\delta:Q\times \Sigma \to Q$
• non-deterministic: a transition function $\Delta:Q\times \Sigma \to P(Q)$
• non-deterministic: a transition relation $\Delta\subset Q\times \Sigma \times Q$
• non-deterministic: a function $\Delta: \Sigma \to P(Q \times Q)$
• probabilistic: a function $\delta: \Sigma \to ssM(Q)$

Here $P(Q)$ is the power set of $Q$ and $ssM(Q)$ is the space of substochatic matrices on $Q$. A right substochastic matrix is a nonnegative real matrix, with each row summing to at most 1.

There are many different reasonable acceptance conditions

The transitions are only one part of a machine, initial and final states, possible output and acceptance conditions are also important. However, there are only very few non-eqivalent acceptance conditions for deterministic machines, a number of reasonable acceptance conditions for non-deterministic machines (NP, coNP, #P, ...), and many possible acceptance conditions for probabilistic machines. Hence this answer focuses primarily on the transitions.

Reversibility is non-trivial for probabilistic machines

A partial function is reversible iff it is injective. A relation is always reversible in a certain sense, by taking the opposite relation (i.e. reversing the direction of the arrows). For a substochastic matrix, taking the transposed matrix is analogous to taking the opposite relation. In general, the transposed matrix is not a substochastic matrix. If it is, then the matrix is said to be doubly substochastic. In general $P P^T P\neq P$, even for a doubly substochastic matrix $P$, so one can wonder whether this is a reasonable notion of reversibility at all. It is reasonable, because the probability to reach state $B$ from state $A$ in $k$ forward steps is identical to the probability to reach state $A$ from state $B$ in $k$ backward steps. Each path from A to B has the same probability forward and backward. If suitable acceptance conditions (and other boundary conditions) are selected, then doubly substochastic matrices are an appropriate notion of reversibility for probabilistic machines.

Reversibility is tricky even for non-deterministic machines

Just like in general $P P^T P\neq P$, in general $R\circ R^{op}\circ R \neq R$ for a binary relation $R$. If $R$ describes a partial function, then $R\circ R^{op}\circ R = R$ and $R^{op}\circ R\circ R^{op} = R^{op}$. Even if relations $P$ and $Q$ should be strictly reversible in this sense, this doesn't imply that $P\circ Q$ will be strictly reversible too. So let's ignore strict reversibility now (even so it feels interesting), and focus on reversal by taking the opposite relation. A similar explanation like for the probabilistic case shows that this reversal works fine if suitable acceptance conditions are used.

These considerations also make sense for pushdown automata

This post suggests that one motivation for non-determinism is to remove that asymmetry between forward steps and backward steps. Is this symmetry of non-determinism limited to finite automata? Here are corresponding symmetric definitions for pushdown automata

• a finite set of states $Q$
• a finite set of input symbols $\Sigma$
• a finite set of stack symbols $\Gamma$
• deterministic: a partial transition function $\delta:Q\times\Gamma\times (\Sigma\cup\{\epsilon\}) \to Q\times\Gamma^{\{0,2\}}$ such that $\delta(q,\gamma,\epsilon)\neq\epsilon$ only if $\delta(q,\gamma,\sigma)=\epsilon$ for all $\sigma\in\Sigma$
• non-deterministic: a transition function $\Delta:Q\times\Gamma^{\{0,1\}}\times (\Sigma\cup\{\epsilon\}) \to P(Q\times\Gamma^{\{0,1\}})$
• non-deterministic: a transition relation $\Delta\subset Q\times\Gamma^{\{0,1\}}\times (\Sigma\cup\{\epsilon\}) \times Q\times\Gamma^{\{0,1\}}$
• non-deterministic: a function $\Delta: \Sigma\cup\{\epsilon\} \to P(Q\times\Gamma^{\{0,1\}}\ \times\ Q\times\Gamma^{\{0,1\}})$
• probabilistic: a function $\delta: \Sigma\cup\{\epsilon\} \to ssM(Q\times\Gamma^{\{0,1\}})$ such that $\delta(\epsilon)+\delta(\sigma)\in ssM(Q\times\Gamma^{\{0,1\}})$ for all $\sigma\in\Sigma$

Here $\epsilon$ is the empty string, $\Gamma^{\{0,2\}}=\{\epsilon\}\cup\Gamma\cup(\Gamma\times\Gamma)$ and $\Gamma^{\{0,1\}}=\{\epsilon\}\cup\Gamma$. This notation is used because it is similar to $\Gamma^*$, which is used in many definitions for pushdown automata.

Diagramed verification of reversal for (non)advancing input and stack operations

An advancing input operation with $b\in\Sigma\subset\Sigma\cup\{\epsilon\}$ gets reversed as follows

$a|bc \to a|\boxed{b}c \to ab|c$
$a|bc \leftarrow a\boxed{b}|c \leftarrow ab|c$
$c|ba \to c|\boxed{b}a \to cb|a$

A non advancing input operation with $\epsilon\in\Sigma\cup\{\epsilon\}$ that doesn't read any input can be reversed

$a|bc \to a|bc \to a|bc$
$a|bc \leftarrow a|bc \leftarrow a|bc$
$cb|a \to cb|a \to cb|a$

Here is a diagram of an advancing input operation whose reversal would look bad

$\require{cancel}\xcancel{\begin{matrix} a|bc \to \boxed{a}|bc \to ab|c\\ a|bc \leftarrow \boxed{a}b|c \leftarrow ab|c\\ c|ba \to c|b\boxed{a} \to cb|a \end{matrix}}$

For a stack operation $(s,t) \in \Gamma^{\{0,1\}}\times\Gamma^{\{0,1\}}$, there are the three cases $(s,t)=(a,\epsilon)$, $(s,t)=(\epsilon,a)$, and $(s,t)=(a,b)$. The stack operation $(a,\epsilon)$ gets reversed to $(\epsilon,a)$ as follows

$ab\ldots \to \boxed{a}b\ldots \to |b\ldots$
$\boxed{a}b\ldots \leftarrow |b\ldots \leftarrow b\ldots$
$b\ldots \to |b\ldots \to \boxed{a}b\ldots$

The stack operation $(a,b)$ gets reversed to $(b,a)$ as follows

$ac\ldots \to \boxed{a}c\ldots \to \boxed{b}c\ldots$
$\boxed{a}c\ldots \leftarrow \boxed{b}c\ldots \leftarrow bc\ldots$
$bc\ldots \to \boxed{b}c\ldots \to \boxed{a}c\ldots$

A generalized stack operation $(ab,cde)\in\Gamma^*\times\Gamma^*$ would be reversed to $(cde,ab)$

$abf\ldots \to \boxed{ab}f\ldots \to \boxed{cde}f\ldots$
$\boxed{ab}f\ldots \leftarrow \boxed{cde}f\ldots \leftarrow cdef\ldots$
$cdef\ldots \to \boxed{cde}f\ldots \to \boxed{ab}f\ldots$

Reversibility for Turing machines

A machine with more than one stack is equivalent to a Turing machine, and stack operations can easily be reversed. The motivation at the beginning also suggests that reversal (of a Turing machine) should not be difficult. A Turing machine with a typical instruction set is not so great for reversal, because the symbol under the head can influence whether the tape will move left or right. But if the instruction set is modified appropriately (without reducing the computational power of the machine), then reversal is nearly trivial again.

A reversal can also be constructed without modifying the instruction set, but it is not canonical and a bit ugly. It might seem that the existence of a reversal is just as difficult to decide as many other question pertaining to Turing machines, but a reversal is a local construction and the difficult questions often have a global flavor, so pessimism would probably be unjustified here.

The urge to switch to equivalent instruction sets (easier to reverse) shows that these questions are less obvious than they first appear. A more subtle switch happened in this post before, when total functions and stochastic matrices were replaced by partial functions and substochastic matrices. This switch is not strictly necessary, but the reversal is ugly otherwise. The switch to the substochastic matrices was actually the point where it became obvious that reversibility is not so trivial after all, and that one should write down details (as done above) instead of taking just a high level perspective (as presented in the motivation at the beginning). The questions raised by Niel de Beaudrap also contributed to the realization that the high level perspective is slightly shaky.

Conclusion

Non-deterministic machines allow a finite number of deterministic transitions at each step. For probabilistic machines, these transitions additionally have a probability. This post conveys a different perspective on non-determinism and randomness. Ignoring global acceptance conditions, it focuses on local reversibility (as a local symmetry) instead. Because randomness preserves some local symmetries which are not preserved by determinism, this perspective reveals non-trivial differences between non-deterministic and probabilistic machines.

• Are you assuming that non-deterministic transitions are one-to-many relations? What if two different configurations can transition to a common configuration, among others? — It seems to me that the difference between randomness and nondeterminism is not reversibility (neither are, without further constraint), but rather how one attributes significance to branches according to the result: perfectly democratic for randomness, or preferentially sensitive to "yes" or "no" answers for nondeterminism. Commented Jan 25, 2015 at 23:18
• @NieldeBeaudrap I assume that non-deterministic transitions are "arbitrary" relations (one for each symbol from the input alphabet). I can reverse them, swap start and end state, and get again a non-deterministic finite state machine, which accepts the reversed input string. This is what I call "run the machine backwards in time". (The machine accepts if there is at least one path from start to end state in the non-deterministic case, and this condition doesn't change when reversing time.) Please try to convince yourself that this works at least for a finite state machine. Commented Jan 25, 2015 at 23:48
• So, you refer to the dual of the machine. For NFAs this seems a meaningful notion of reversibility. It's also clear that the dual of an NTM (with a single accept state) is another NTM, but I would hesitate to say that it is the same machine being run in reverse. Does your answer amount just to "Nondeterminism allows you to obtain closure under duals, random (and deterministic) machines aren't"? Commented Jan 26, 2015 at 13:04
• @NieldeBeaudrap My idea is certainly to run backwards in time, but I know that this isn't satisfied perfectly (because the conditions for a generalized inverse of an inverse semigroup are not satisfied). But what I tried to convey is that random (and deterministic) machines don't always allow this sort of reversal. Commented Jan 26, 2015 at 13:55
• I wrote this answer in a blog post about Reversibility of binary relations, substochastic matrices, and partial functions. Commented May 12, 2015 at 6:25

In the context of Turing Machines (TMs) and automata theory, a non-deterministic machine is one in which any instantiation of the machine which accepts is fine. In this sense, it is like running multiple deterministic machines in parallel and take the output of any instances that accept the input. In fact there is a (deterministic) algorithm to transform any non-deterministic automaton (with $n$ states) into an equivalent deterministic one (with $2^n$ states, exponential) by considering equivalence classes of states, no matter if the algorithm implemented in the machine involves randomisation or probabilities (see below).

But if the algorithm implemented in the machine, involves randomisation or probabilities (intrinsic in the algorithm), then it is a randomised (or probabilistic) machine.

In general, it is always possible to remove non-determinism from a machine and construct a deterministic equivalent (see algorithm above), but the same cannot be done (in general) to remove randomisation (in the context of the above) because it is intrinsic to the algorithm implemented.

Note that in the light of the above, both a deterministic machine and a non-deterministic machine can be probabilistic if the algorithm (involved) uses randomisation (or probabilities) in this way.

To sum up, non-determinism in automata (in this context) refers to classes of similar automata, while randomisation or probabilistic machines refer to the (intrinsic application of randomisation in the) actual algorithms implemented by these automata.