Nondeterministic Turing machine

A nondeterministic Turing machine ( NTM , NDTM ) in theoretical computer science is a Turing machine that uses a transition relation instead of a transition function .

Informal description

A deterministic Turing machine (hereinafter DTM ) has a transition function that specifies three things for a given state and symbol under the read head: the symbol to be written on the tape, the direction in which the read head is to be moved, and the state to be changed to.

An NTM differs from a DTM in that the current status and the current ribbon symbol no longer clearly define these three things, rather there are several possible transitions. The NTM does not have a unique run for each input, but many different possible runs. (This can be interpreted in such a way that it runs one of the possible runs randomly, or in such a way that it runs all possible runs in parallel.) It accepts the input if there is an accepting run.

Since this behavior cannot be easily implemented based on current knowledge, it is a theoretical machine model. Nevertheless, this model is of great importance for theoretical computer science, especially for the area of complexity theory , for various reasons .

Formal definition

A nondeterministic Turing machine ( NTM for short ) is a 7-tuple , where ${\ displaystyle M = (Q, \ Sigma, \ Gamma, \ delta, q_ {0}, \ square, F)}$

State quantity: ${\ displaystyle Q \ neq \ emptyset}$ is a finite non-empty set
Input alphabet: ${\ displaystyle \ Sigma \ neq \ emptyset}$ is a finite non-empty set
Ribbon alphabet: ${\ displaystyle \ Gamma \ neq \ emptyset, \ Gamma \ supset \ Sigma}$ is a finite non-empty set
Transition relation: ${\ displaystyle \ delta \ subseteq ((Q \ setminus F) \ times \ Gamma) \ times (Q \ times \ Gamma \ times \ {L, N, R \})}$
Starting state: ${\ displaystyle q_ {0} \ in Q}$
Blank icon: ${\ displaystyle \ square \ in \ Gamma \ setminus \ Sigma}$
Set of final states: ${\ displaystyle F \ subseteq Q}$

A configuration of the NTM is a 4-tuple , where , , and (for a definition of see Kleene shell ). Intuitively, a configuration means that the NTM is in the state in which the field on which the read / write head is located contains the symbol , the infinite band to the left of the read / write head has the content (with an infinite number of blank Symbols to the left of are not included) and to the right of the W / L head has the content (again, only the finite part is considered, which contains all non-blank symbols). The set of configurations of is denoted by. We define a binary relation on (called the configuration transition relation ) as follows: ${\ displaystyle M}$ ${\ displaystyle (u, q, a, v)}$ ${\ displaystyle u \ in \ Gamma ^ {\ star}}$ ${\ displaystyle q \ in Q}$ ${\ displaystyle a \ in \ Gamma}$ ${\ displaystyle v \ in \ Gamma ^ {\ star}}$ ${\ displaystyle \ Gamma ^ {\ star}}$ ${\ displaystyle (u, q, a, v)}$ ${\ displaystyle M}$ ${\ displaystyle q}$ ${\ displaystyle a}$ ${\ displaystyle u}$ ${\ displaystyle u}$ ${\ displaystyle v}$ ${\ displaystyle M}$ ${\ displaystyle \ operatorname {conf} (M)}$ ${\ displaystyle \ Rightarrow _ {M}}$ ${\ displaystyle \ operatorname {conf} (M)}$

For two configurations and applies if and only if one of the following conditions is met ( here stands for the empty word): ${\ displaystyle c_ {1} = (u_ {1}, q_ {1}, a_ {1}, v_ {1})}$ ${\ displaystyle c_ {2} = (u_ {2}, q_ {2}, a_ {2}, v_ {2})}$ ${\ displaystyle c_ {1} \ Rightarrow _ {M} c_ {2}}$ ${\ displaystyle \ varepsilon}$

${\ displaystyle u_ {1} = u_ {2}}$ , and or ${\ displaystyle v_ {1} = v_ {2}}$ ${\ displaystyle (q_ {1}, a_ {1}, q_ {2}, a_ {2}, N) \ in \ delta}$
there is so , , and or ${\ displaystyle a \ in \ Gamma}$ ${\ displaystyle u_ {1} = u_ {2} = \ varepsilon}$ ${\ displaystyle av_ {1} = v_ {2}}$ ${\ displaystyle a_ {2} = \ square}$ ${\ displaystyle (q_ {1}, a_ {1}, q_ {2}, a, L) \ in \ delta}$
there is a so that , and or ${\ displaystyle a \ in \ Gamma}$ ${\ displaystyle u_ {1} = u_ {2} a_ {2}}$ ${\ displaystyle av_ {1} = v_ {2}}$ ${\ displaystyle (q_ {1}, a_ {1}, q_ {2}, a, L) \ in \ delta}$
there is so , , and or ${\ displaystyle a \ in \ Gamma}$ ${\ displaystyle u_ {1} a = u_ {2}}$ ${\ displaystyle v_ {1} = v_ {2} = \ varepsilon}$ ${\ displaystyle a_ {2} = \ square}$ ${\ displaystyle (q_ {1}, a_ {1}, q_ {2}, a, R) \ in \ delta}$
there is a so that , and . ${\ displaystyle a \ in \ Gamma}$ ${\ displaystyle u_ {1} a = u_ {2}}$ ${\ displaystyle v_ {1} = a_ {2} v_ {2}}$ ${\ displaystyle (q_ {1}, a_ {1}, q_ {2}, a, R) \ in \ delta}$

The initial configuration of the input word is the configuration . A configuration is called final configuration if . If there is a final configuration, then it is called an accepting final configuration , if not , it is called a non-accepting final configuration. ${\ displaystyle M}$ ${\ displaystyle w \ in \ Sigma ^ {\ star}}$ ${\ displaystyle c_ {0} = (\ varepsilon, q_ {0}, \ square, w)}$ ${\ displaystyle c = (u, q, a, v)}$ ${\ displaystyle q \ in F}$ ${\ displaystyle c}$ ${\ displaystyle a \ neq \ square}$

A finite run of on the input word is a finite sequence of configurations, wherein the initial configuration is a final configuration and, for each natural number with the following applies: . A finite run on is called accepting if it is accepting, otherwise it is called non-accepting. ${\ displaystyle M}$ ${\ displaystyle w}$ ${\ displaystyle c_ {0}, c_ {1}, \ ldots, c_ {n}}$ ${\ displaystyle c_ {0}}$ ${\ displaystyle w}$ ${\ displaystyle c_ {n}}$ ${\ displaystyle i}$ ${\ displaystyle 1 \ leq i \ leq n}$ ${\ displaystyle c_ {i-1} \ Rightarrow _ {M} c_ {i}}$ ${\ displaystyle w}$ ${\ displaystyle c_ {n}}$

An infinite run of Command is an infinite sequence of configurations, wherein the initial configuration and for any natural number with valid: . ${\ displaystyle M}$ ${\ displaystyle w}$ ${\ displaystyle c_ {0}, c_ {1}, c_ {2}, \ ldots}$ ${\ displaystyle c_ {0}}$ ${\ displaystyle w}$ ${\ displaystyle i}$ ${\ displaystyle 1 \ leq i}$ ${\ displaystyle c_ {i-1} \ Rightarrow _ {M} c_ {i}}$

A decision maker is an NTM that does not have an infinite course. Be a decision maker. The language accepted by is defined as there is an accepting run of on . ${\ displaystyle M}$ ${\ displaystyle M}$ ${\ displaystyle L_ {M} \ subseteq \ Sigma ^ {\ star}}$ ${\ displaystyle L_ {M} = \ left \ {w \ in \ Sigma ^ {\ star} \ mid \ right.}$ ${\ displaystyle M}$ ${\ displaystyle \ left.w \ right \}}$

Equivalence to Deterministic Turing Machines

Since every (deterministic) transition function of a DTM can be understood as a transition relation of an NTM, NTMs are at least as powerful as DTMs, since they contain them completely. Conversely, any language recognized by an NTM can also be recognized by a DTM. The DTM simulates all transitions of the NTMs by creating multiple copies of the simulated state, provided that multiple transitions are possible; these are then simulated in parallel. Can e.g. For example, if a problem is solved by an NTM in polynomial time, it can be solved by a deterministic Turing machine in exponential time. There is then also a DTM that solves the problem with polynomial memory requirements ( Savitch's theorem ).

Significance in complexity theory

The meaning of nondeterministic Turing machines can be explained as follows: A problem can only be regarded as efficiently solvable if it can be decided in polynomial time. On deterministic Turing machine all the problems to which it applies, the class P attributed. However, there is a large number of problems that are very important in practice and for which it has not yet been possible to show whether they lie in P. As it turned out, many of these problems can be solved on a nondeterministic Turing machine in polynomial time; they lie in NP . The fact that so many important but deterministically inefficiently solvable problems lie in this class has nourished the hope that an investigation of the nondeterministic Turing machine type will provide clues to a more efficient solution to these problems. For example, if a general method could be found with which a nondeterministic Turing machine can be simulated by a deterministic one in polynomial time, then it would be shown for all of the problems mentioned that they lie in P and can thus be efficiently solved. The classes P and NP would then be identical. However, this has not yet succeeded. The question is also known as the P-NP problem .

By means of nondeterministic Turing machines, a number of significant complexity classes are defined in addition to NP . The set of all time complexity classes that can be traced back to nondeterministic Turing machines is called NTIME . Similarly, NSPACE is the set of all space complexity classes for this machine type.

literature

John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory. 3rd, updated edition. Pearson Studium, Munich 2011, ISBN 978-3-86894-082-4 , 8.4.4 Nondeterministic Turing Machines (English: Introduction to Automata Theory, Languages, and Computation . 2007. Translated by Sigrid Richter and Ingrid Tokar).
Ingo Wegener : Theoretical Computer Science . An algorithm-oriented introduction. BG Teubner, Stuttgart, ISBN 3-519-02123-4 , 3.2 Non-deterministic Turing machines and the class NP.

Source reference

This is a free, incomplete translation of the entry in English Wikipedia. For references cf. there.