What is the difference between non-determinism and randomness?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

PPT I found helpful.

Answer 6

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".

Answer 7

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.

Answer 8

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.

Answer 9

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.