How does a nondeterministic Turing machine work?

Question

What is differences between deterministic and nondeterministic Turing machines? Different but equivalent models of NDTM. In particular, what is this frequently used phrase "nondeterministically guess"? How to use it right, and examples of wrong usage. My goal is to create a reference question.

Answer 1

Here are several ways of thinking about non-determinism (copied from this answer).

The genie. Whenever the machine has a choice, a genie tells it which way to go. If the input is in the language, then the genie can direct the machine in such a way that it eventually accepts. Conversely, if the input is not in the language, whatever the genie tells the machine to do, it will always reject.

Hints. The machine computes a bivariate function. The first input is a word $w$, and the second input is a "hint" $x$. Whenever the machine faces a non-deterministic choice, it consults the next hint symbol, and operates accordingly. We are promised the following:

• Completeness: if $w \in L$ then there is some hint $x$ which causes the machine to accept.
• Soundness: if $w \notin L$ then the machine rejects on all hints.

Accepting computations. An accepting computation is a legal computation (one in which the machine always operates according to one of the choices it is faced with) which ends at an accepting state. A word is in the language iff it has an accepting computation.

We can formalize the notion of accepting computation using configurations. A configuration is an instantaneous description of the entire state of the machine. We can define a relation $\sigma \vdash \sigma'$, where $\sigma,\sigma'$ are configurations, which holds when $\sigma$ can lead to $\sigma'$ in one step. In a deterministic machine, there is at most one $\sigma'$ per each $\sigma$, whereas in a nondeterministic machine, there could be more than one. An accepting computation for a word $w$ is one which starts at the initial configuration (the tape contains $w$, the head points at the start of $w$, the state is the initial state) and ends at an accepting configuration.

Another equivalent description is in terms of reachability. Consider a directed graph in which vertices are configurations and there is an edge from $\sigma$ to $\sigma'$ if $\sigma \vdash \sigma'$. An accepting computation is a path from the initial configuration to an accepting configuration.

Answer 2

Acceptance of input string in NTM

let me add more about deterministic and non-deterministic Turing machines. Let us consider that for some language $L$, we design a deterministic and non-deterministic Turing machine respectively. On some input $x$, there is going to be only one path of configurations in the case of deterministic Turing machine, i.e $c_0 \longrightarrow c_1 \longrightarrow \cdots \longrightarrow c_k$ (where each $c_i$ represents a configuration at $i$th step) . Now on the basis of configuration $c_k$, we can easily accept and reject the input string $x$.

See the image below for better understanding :

In the case of NTM, we need to be careful, because it may happen that on some configuration paths, we get into rejecting state. So for non-deterministic Turing machines, we say a string is accepted if at least one of the configuration path leads to accepting state. We will reject the input string if all configuration paths lead to rejecting state.

For example, consider the configuration tree given above for non-deterministic Turing machine on say some input string $x$, In this case we will accept the input string because there is an one accepting path.

Reference : http://cs.umw.edu/~finlayson/class/fall14/cpsc326/notes/24-complexity2.html

Answer 3

The difference between deterministic and non-deterministic Turing machines lies in the transition function. In deterministic Turing machines $\delta$ the transition function is a partial function:

$\delta: Q \times B \to Q \times B \times \{left, right\} $

which means that given a state and a tape symbol you have one or none state, input symbol to right and direction to move. However in non-deterministic Turing machines this looks like (here $\mathcal{P}$ is the set of subsets of a set):

$\delta: Q \times B \to \mathcal{P}(Q \times B \times \{left, right\})$

meaning that you have none or several states, tape symbols to write or direction to move to. This gives to your machine the possibility to effectively choose in such a state and tape symbol between the different "branches" of computation possible.

In practice, this means that we can compute different outputs for the same input. Therefore, the language of a non-deterministic Turing machine is the set of words for which we find a derivation in the defined transitions. An specific run may not find such derivation but the important thing is that it may occur. So when you "guess" you're just choosing one of the possible branches of computation.

Example of use

$L = \{(M_1,M_2):\text{there exists at least one word accepted by both TM at the same time}\}$

In this case one could just "guess" a word $w$ and execute $M_1$ and $M_2$ on $w$ checking that if both accept, they accept at the same time. The guessing could work by introducing a state $q$ with transitions that write on some tape $0$s and/or $1$s and that exits by reading any symbol to the general machine.

To be honest I haven't come across any example of bad use of this "guess" but checking that each time this phrase is used is done correctly, reduces to verify that you could build an automata with this structure that simulated the guessing.

Answer 4

Augmentation with a guessing module.

I found this model in "Computers and Intractability" by M.R. Garey and D.S. Johnson.

The NDTM has exactly the same structure as a DTM, except that it is augmented with a guessing module having it own write-only head. The guessing module provides the means for writing down the "guess" and is used solely for this purpose.

How it works.

The first stage is the guessing stage. Initially, the input string $x$ is written in tape squares $1$ through $|x|$ (while all other squares are blank), the read-write head is scanning square $1$, the write-only head is scanning square $-1$, and the finite state control is "inactive". The guessing module then directs the write-only head, one step at a time, either to write some symbol from the tape alphabet $\Gamma$ in the tape square being scanned and move one square to the left, or to stop, at which point the guessing module becomes inactive and the finite state control is activated in state $q_0$. The choice of whether to remain active, and, if so, which symbol from $\Gamma$ to write, is made by the guessing module in a totally arbitrary manner. Thus the guessing module can write any string from $\Gamma^*$ before it halts and, indeed, need never halt.

The "checking" stage begins when the finite state control is activated in state $q_0$. From this point on, the computation proceeds solely under the direction of the NDTM program according to exactly the same rules as for a DTM. The guessing module and its write-only head are no longer involved, having fulfilled their role by writing the guessed string on the tape. Of course, the guessed string can (and usually will) be examined during the checking stage. The computation ceases when and if the finite state state control enters one of two halts states (either $q_Y$ or $q_N$) and is said to be accepting computation if it halts in state $q_Y$. All other computations, halting or not, are classed together simply as non-accepting computations.
Notice that any NDTM program $M$ will have an infinite number of possible computations for a given input string $x$, one for each possible guessed string from $\Gamma^*$. We say that the NDTM program $M$ accepts $x$ if at least one of these is an accepting computation.

The time required by an NDTM program $M$ to accept the string $x\in L_M$ is defined to be the minimum, over all accepting computations of $M$ for $x$ , of the number of steps occurring in the guessing and checking stages up until the halt state $q_Y$ is entered.

The only point deserving special special mention is that, wheres we usually envision a nondeterministic algorithm as guessing a structure $S$ that in some way depends on the given [problem] instance $I$, the guessing module of an NDTM entirely disregards the given input. However, since every string from $\Gamma^*$ is a possible guess, we can always design our NDTM program so that the checking stage begins by checking whether ot not the guessed string corresponds (under the implicit interpretation our program places on strings) to an appropriate guess for the given input. If not, the program can immediately enter the halt state $q_N$.

. . .

The class $NP$ is defined informally to be the class of all decision problems $\Pi$ that, under reasonable encoding schemes, can be solved by polynomial time nondeterministic algorithms.

The use of term "solve" in these informal definition should, of course, be taken with a grain of salt. It should be evident that a "polynomial time nondeterministic algorithm" is basically a definitional device for capturing the notion of polynomial time verifiability, rather than a realistic method of solving decision problems. Instead of having just one possible computation on a given input, it has many different ones, one for each possible guess.

It is this notion of polynomial time "verifiability" that the class $NP$ is intended to isolate. Notice that polynomial time verifiability does not imply polynomial solvability.