Non-deterministic Turing machine
A nondeterministic Turing machine (NTM, NDTM ) in theoretical computer science is a Turing machine that uses instead a transition function a transition relation.
Informal Description
A deterministic Turing machine (the DTM ) has a transition function that specifies for a given state and symbol under the read head three things: the symbol that is to be written to the tape, the direction in which the reading head to be moved, and the condition in the target to be changed.
A NTM is different from a DTM by the fact that the current state and the current tape symbol is no longer set these three things clearly, but there are several possible transitions. The NTM is perfect for any input rather than a clear run, but many different possible runs. (This can be interpreted to mean that they randomly performs one of the possible runs, or so that it performs all possible runs in parallel. ) It accepts the input if there is an accepting run.
Because this behavior is not feasible on current knowledge, readily, it is a theoretical machine model. Nonetheless, this model has various reasons of great importance for theoretical computer science, particularly in the area of complexity theory.
Formal definition
A non-deterministic Turing machine ( shortly: NTM ) is a 7- tuple, where
A configuration of the NTM is a 4 -tuple, where, , and ( for a definition of Kleene see envelope). Intuitively, a configuration that the NTM is in the state, the field in which there is the read / write head that contains the icon to the left of the infinite tape read / write head has the content (with an infinite number of blank are left not included by symbols) and the right of the S / L- head has the content (again, only the finite part is again considered, which includes all non -blank symbols). The set of configurations is denoted by. We define a binary relation on ( called configuration transition relation ) as follows:
For two configurations and holds if and only if one of the following conditions is met ( here stands for the empty word ):
- And or
- There is a, so, and or
- There is a such that and or
- There is a, so, and or
- There is a, so that and.
The initial configuration of the input word on the configuration. A configuration is called final configuration, though. If a final configuration, then it means accepting final configuration, when, otherwise it is called non -accepting final configuration.
A finite run of on the input word is a finite sequence of configurations, where the initial configuration is on, a final configuration and is true for any natural number. A finite run on means accepting when accepting, otherwise it is called non- accepting.
An infinite run of Command is an infinite sequence of configurations, where the initial configuration is set and is true for any natural number.
A decision is an NTM that has no infinite run. Be a decision maker. The accepted language is defined by as there is an accepting run of on.
Equivalent to Deterministic Turing Machines
Since each ( deterministic) transition function of a DTM can be interpreted as a transition relation of a NTM, NTM are at least as powerful as DTM, as they contain this completely. Conversely, can be recognized by a DTM also each recognized by a NTM language. The DTM simulates all the transitions of NTMs by creating multiple copies of the simulated state, if multiple transitions are possible; these are then simulated in parallel. Can, for example, a problem of a NTM be solved in polynomial time, so it can be solved by a deterministic Turing machine in exponential time. There is then also a DTM that solves the problem with polynomiellem memory overhead ( set of Savitch ).
Importance in complexity theory
The importance of non-deterministic Turing machine can be explained as follows: It is considered a problem only considered efficiently solvable, if it can be decided in polynomial time. On deterministic Turing machines all problems for which this is true, the class P are attributed. However, there are quite a large number of very significant practical problems for which has yet to be shown whether they lie in P. As has been found, a number of these problems on a non-deterministic Turing machine in polynomial time can decide they are in NP. The fact that so many important, but deterministic been efficiently solvable problems are not in this class, has nurtured the hope to get through an investigation of non-deterministic Turing machine type hints at a more efficient solution to these problems. Could we find such a general method, with which a non- deterministic Turing machine can be simulated by a deterministic polynomial-time, so problems would be shown that they lie in P and thus are efficiently solvable for all of the above. The classes P and NP would then be identical. But this is still not succeeded. The question is known as P- NP problem.
Using non-deterministic Turing machines are next to NP defines a number of significant complexity classes. The set of all time complexity classes that are attributed to non-deterministic Turing machines, ie NTIME. NSPACE analog is the set of all space complexity classes of this type of machine.