Nondeterministic Turing machine

2020 Mathematics Subject Classification: Primary: 68Q05 [MSN][ZBL]

A nondeterministic Turing machine generalizes the concept of the (deterministic) Turing machine from a uniquely determined sequence of computation steps to serveral possible sequences. The set of Turing-computable functions is not changed by this modification, but the computational complexity, i.e. the necessary effort to calculate a function, may differ for deterministic and nondeterministic Turing machines. One of the most famous (unsolved) problems in this context is the question, whether the classes of functions calculated with polynomial effort coincide for deterministic and nondeterministic functions (P=NP).

Definition of Nondeterministic Turing Machines

A (deterministic) Turing machine is equipped with a partially defined transition function $\delta\colon Q\setminus\{q_f\} \times\Sigma \longrightarrow Q \times\Sigma \times\{L,R,N\}$. A nondeterministic Turing machine $T=(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ generalizes this concept to a transition relation $\delta\subseteq Q\setminus\{q_f\} \times\Sigma \longrightarrow Q \times\Sigma \times\{L,R,N\}$. This means that for a given state $q\in Q$ and for a given symbol $a\in\Gamma$ on the tape, $T$ may proceed in different ways. Put in another way, $\delta$ may be considered as a function $\delta\colon Q\times\Sigma \times Q \times\Sigma \times\{L,R,N\} \longrightarrow \{\text{\tt true},\text{\tt false}\}$ or as a function $\delta\colon Q\times\Sigma \longrightarrow {\mathcal{P}}(Q \times\Sigma \times\{L,R,N\})$. Here, $\mathcal{P}$ designates the power set operator. Using this notation, the degree of nondeterminism is defined as $$\max\limits_{q\in Q,a\in\Gamma} |\delta(q,a)|.$$ A nondeterministic Turing machine with a degree of nondeterminism equal to 1 is behaving like a deterministic Turing machine.

The computation steps of a (deterministic) Turing machine are a linear sequence. For a nondeterministic Turing machine $T$, the computation sequence may split up in several branches. Thus, the computation steps of a nondeterministic Turing machine are arranged as a tree with the starting configuration of $T$ as its root node. Based on the computation tree, one can define:

• The machine $T$ accepts an input $x\in\Sigma^\ast$, if it exists a path in the computation tree with a leaf representing the state $q_f\in Q$. In other words, if a nondeterministic Turing machine $T$ accepts an input $x\in\Sigma^\ast$, it can 'guess' a path leading to the accepting state.
• The machine $T$ rejects an input $x\in\Sigma^\ast$, if $x$ is not accepted, i.e. if no path in the computation tree exists with $q_f\in Q$ as final state.
• The machine $T$ semidecides a language $L\subseteq \Sigma^\ast$, if $T$ accepts all $x\in L$ and rejects all $x\in\Sigma^\ast$ with $x\notin L$.
• The machine $T$ decides a language $L\subseteq \Sigma^\ast$, if for all $x\in L$ it holds
  • $x\in L\Longleftrightarrow$ $T$ accepts $x$
  • All paths in the computation tree of $x\in L$ are finite
  • The number of paths in the computation tree of $x\in L$ is finite

Since the automaton controlling the Turing machine is finite, the branching factor of the computation tree is finte, too. The tree may be infinite, however, because the Turing machine may not halt in some branches.

Properties of Nondeterministic Turing Machines

The computation process of a nondeterministic Turing machine can be interpreted as a (deterministic) Turing machine with the capability to create and start other Turing machines processing alternative branches of the calculation. Thus a Turing machine $T'$ can simulate a nondeterministic Turing machine $T$ by iterating all branches of the calculation of $T$ up to a certain depth $d$. Then $d$ is incremented and the iteration repeated. This is done until an accepting branch is found or no branch can be continued. The simulation process may continue forever, because the paths of the computation tree are not necessarily finite. From an algorithmic point of view, $T'$ executes a breadth-first search in this way. The approach assures, that paths with an infinite length can be handled successfully by the search process. Other search strategies like a depth first search will not necessarily succeed.

The nondeterministic Turing machine is one of many possible modifications of the classical definition of a Turing machine. Their discussion was aiming at the construction of a computation model with higher computational power than the deterministical Turing machine. From the simulation concept above it follows, however, that a nondeterministic Turing machines can not compute more functions than the (deterministic) Turing machine. The computational complexity of a task processed by a nondeterministic Turing machine may be smaller than the complexity for the corresponding task processed by a (deterministic) Turing machine on the other hand.

Complexity of Nondeterministic Turing Machines

For a given language $L\subseteq\Sigma^\ast$, the time $t(x)$ required by a nondeterministic Turing machine to process an input $x\in\Sigma^\ast$ is determined in the following way. We will distinguish two cases. In the case $x\in L$, it is defined as the length of the shortest path in the computation tree accepting $x$. In the case $x\notin L$, the value of $t(x)$ is defined as the length of the shortest path in the computation tree.

The time $t(n)$ required by $T$ for processing an input $x\in\Sigma^\ast$ of length $|x|=n\in\mathbb{N}$ is defined as the maximum of all finite $t(x)$ for $x\in\Sigma^\ast$ with $|x|=n$.

Now, a language $L\subseteq \Sigma^\ast$ belongs to the complexity class NP, it it exists a nondeterministic Turing machine $T$ and a polynom $p$ such that $T$ accepts $L$ with $O(p(|x|))$ computation steps for all $x\in L$.

The corresponding complexity class for deterministic Turing machines is designated as P. Since deterministic Turing machines are a special case of nondeterministic ones, it obviously holds P $\subseteq$ NP. Whether this statement can be strengthened to P $=$ NP, is an open problem up to now (2013).

Some Caveats

If a deterministic Turing machine $T'=(Q',\Sigma',\Gamma',\sqcup',q_0',q_f',\delta')$ accepts a language $L\subseteq \Sigma^{\prime\ast}$, the machine $T'$ can be easily modified to a machine $\bar T'$ accepting the complementary language $\Sigma^{\prime\ast}\setminus L$. In principle, the corresponding modification consists in changing the accepting end state $q_f'$ to a nonaccepting one and vice versa. This approach can not be applied to a nondeterministic Turing machine $T=(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ as well. According to the definition, the machine $T$ accepts an input $x\in \Sigma^\ast$, if the resulting computation tree contains a path with an accepting state as final state. Other paths of this computation tree may end in nonaccepting states. Exchanging acceptance and non-acceptance as described above does not change the result in such a case, i.e. the modified machine will still accept $x$.

Another complication has to be taken into account for the different operational views of the nondeterministic Turing machine. For a language acceptor, 'different' results for different paths in the computation tree are tolerated by definition (see above): An input $x\in \Sigma^\ast$ is accepted, if $x$ is accepted in at least one paths. Such a behavior can not be transferred to a nondeterministic Turing machine evaluating a function. If different results $y,y'\in\Sigma^\ast$ are computed in different paths, which one should we take as final result of the computation? Thus, additional restrictions are necessary in the computation mode. Usually it is required that all values computed in different paths are equal to each other.

References

[H77]	F. Hennie, "Introduction to Computability", Addison-Wesley 1977
[HU79]	J. Hopcroft, J. Ullman, "Introduction to Automata Theory, Languages and Computation", Addison-Wesley 1979
[P81]	C. Papdimitriou, "Elements of the Theory of Computation", Prentice-Hall 1981