## Thursday, 5 September 2013

### Nondeterministic Turing Machines

One kind of variant of the deterministic Turing machine is the nondeterministic Turing machine. A deterministic TM has only one unique action at any step of the computation, and therefore the entire computation is completely determined by the input and program. The nondeterministic TM differs from its deterministic counterpart in that there may exist more than one way the machine can behave at any step of the computation. One can think of a nondeterministic TM as having the ability of performing different actions in parallel or simultaneously. Although the deterministic TM can compute anything a nondeterministic TM can compute, the latter may have the ability to perform certain computations more efficiently than the former.

For a deterministic Turing machine the transition function was of the form
$\delta : Q\times\Gamma \longrightarrow Q\times\Gamma\times\{L, R\},$
which yielded one triple $(q',s',d')\in Q\times\Gamma\times \{L, R\}$ for each defined pair $(q,s) \in Q\times \Gamma$. A nondeterminsitic Turing machine (abbreviated NTM) allows for the possibility of multiple actions for a single pair $(q,s)$ that the NTM may encounter. More formally, the transition function for a NTM takes the form
$\delta : Q\times\Gamma \longrightarrow \mathcal{P}(Q\times\Gamma\times\{L, R\}).$
Here, the notation $\mathcal{P}(S)$ of some set $S$ is defined to be the power set of $S$, which is the set of all subsets of $S$. Thus, $\mathcal{P}(Q\times\Gamma\times\{L, R\})$ represents the set of all possible sets of triples $(q',s',d') \in Q\times\Gamma\times\{L, R\}$. The transition function of a NTM will then assign a state and symbol $(q,s)$ to a collection of triples $\delta(q,s) \in \mathcal{P}(Q\times\Gamma\times\{L, R\})$, which represent all possible actions the NTM will carry out when encountering $(q,s)$. Of course, the image for a particular configuration $\delta(q,s)$ may just be a set which contains one element, say $(q',s',d')$, and so that step alone will be uniquely determined by $(q,s)$. Consider the possibility that every possible action of $\delta$ for any configuration of a \emph{nondeterministic} TM is simply a single element set of the form ${(q',s',d')}\in\mathcal{P}(Q\times\Gamma\times\{L, R\})$. In this case, the NTM corresponds to an equivalent deterministic TM. Therefore, deterministic TMs are just special cases of the more general nondeterministic TMs.

As a consequence of having multiple transitions, each of the different possible sequence of configurations that a NTM can take can each be thought of as a computational branch. All of these branches considered together define the NTM's computational tree for a given input. The NTM is considered to have reached an accepting state if at least one branch of the tree reaches a configuration that ends in the accept state regardless of any other branches  having reached the reject state. The essence of the NTM lies in its ability to execute these multiple branches simultaneously as if there were multiple deterministic TMs performing these different actions in parallel.

As mentioned, a deterministic TMs can simulate the action of a NTM by computing the action defined by all the different branches individually either consecutively or in parallel  provided there are multiple deterministic TMs each performing the computation specified by a single branch. Similarly, this simulation with deterministic TMs would accept a particular input if at least one of the TMs reached an accepting state, and reject otherwise.

There is one important issue that ought to be treated more carefully in this simulation. This is the possibility of  their existing computational branches that may not halt on certain inputs--that is,  they  may not eventually end in an accepting or rejecting state. Non-halting computations of this sort may be troublesome when attempting to simulate the action of a NTM using a  single deterministic TM that computes each branch individually. For instance,  the TM may get stuck indefinitely on a branch that may never reach an accepting state and then be unable to move on to another branch that may end in an accepting state. A priori, there is no way of necessarily knowing which branches to simulate first or which ones to avoid.

In order to successfully simulate a computation on a deterministic TM, and avoid complications like the ones described above, the TM can proceed using the method of breadth-first search. Previously, the method described above to simulate the action of a NTM was to simulate each entire branch before simulating another. This method could be referred to as depth-first search. On the contrary, in breadth-first search, all possible branches of the tree are progressively simulated together by simulating a single step in each branch first, then simulating the next step for each branch, and then consecutive steps as they exist for each branch. Proceeding in this way ensures that an accepting state will eventually be reached if one does indeed exist.

It can be shown that for any finite set $S$ of size $n$, the size of the power set $\mathcal{P}(S)$ is $2^n$. For some NTM, suppose the set $Q\times\Gamma\times\{L, R\}$ is of size $n$. Then the maximum number of possible actions that this NTM may take in a particular configuration is given by $2^n$. The point here is that, though this number is finite, it is exponential in $n$. Hence, when a deterministic TM attempts to simulate the action of a NTM it may have to simulate exponentially many steps. In general, even though the deterministic TM can accurately simulate the NTM in principle, it may take exponentially more steps to complete the task. Taking into consideration these extra steps as a resource is what could make the NTM a more efficient computational model when compared to deterministic TMs.