patternMinor
How does a nondeterministic Turing machine work?
Viewed 0 times
howworkdoesmachineturingnondeterministic
Problem
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.
Solution
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:
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.
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.
Context
StackExchange Computer Science Q#80563, answer score: 9
Revisions (0)
No revisions yet.