Turing machine with additional input

A Turing machine with additional input is a computational model of theoretical computer science that is equivalent to nondeterministic Turing machines .

Informal description

A Turing machine with additional input is an extension of the deterministic Turing machine by an additional input . So it is still a machine that works on a string tape and can read and change the content character by character with a read / write head. Different states are run through depending on the character on the read head and the current state of the machine. Every Turing machine can assume two distinct states and . When a Turing machine changes to the state , the calculation ends and the input has been accepted. If the Turing machine changes to the state , the calculation also ends and the input is rejected. ${\displaystyle y}$ ${\displaystyle +}$ ${\displaystyle -}$ ${\displaystyle +}$ ${\displaystyle -}$

A Turing machine with additional input receives a string tuple as input. accepted if there is an additional input so that the input is accepted. The idea behind this construction is that it is viewed as an input to a problem and as a solution. The Turing machine can then try to verify whether there really is a solution for . In this sense, it is accepted if there is a solution to the ( concrete) problem. ${\displaystyle M}$ ${\displaystyle (x,y)}$ ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle M}$ ${\displaystyle (x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle M}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$

definition

Turing machine with additional input

A Turing machine with additional input is a 5-tuple , where ${\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,s)}$

State quantity

${\displaystyle Q\not =\emptyset }$ a finite non-empty set of states,

Working alphabet

${\displaystyle \Gamma }$the working alphabet with the blank character , the left margin and the separator symbol , ${\displaystyle \sqcup \in \Gamma }$ ${\displaystyle \triangleright \in \Gamma }$ ${\displaystyle \#}$

Input alphabet

${\displaystyle \Sigma \subseteq \Gamma \setminus \{\triangleright ,\sqcup ,\#\}}$ the input alphabet,

Transfer function

${\displaystyle \delta :Q\times \Gamma \rightarrow (Q\cup \{+,-\})\times \Gamma \times \{\leftarrow ,\downarrow ,\rightarrow \}}$ the transfer function and

Starting state

${\displaystyle s\in Q}$ is an excellent starting condition.

The transfer function is restricted so that the left margin cannot be overwritten. So it applies to everyone with and . ${\displaystyle q\in Q:\delta (q,\triangleright )=(q',\triangleright ,d)}$ ${\displaystyle q'\in Q}$ ${\displaystyle d\in \{\downarrow ,\rightarrow \}}$

configuration

A configuration of is a 4-tuple with the current state, the string to the left of the head, the character at the head and the string to the right of the head. ${\displaystyle M}$ ${\displaystyle (q,u,\sigma ,v)}$ ${\displaystyle q\in Q\cup \{+,-\}}$ ${\displaystyle u\in \Gamma ^{*}}$ ${\displaystyle \sigma \in \Gamma }$ ${\displaystyle v\in \Gamma ^{*}}$

Successor configuration

If and are two configurations, then the subsequent configuration of (write ) is if and only if with ${\displaystyle K=(q,u,\sigma ,v)}$ ${\displaystyle K'=(q',u',\sigma ',v')}$ ${\displaystyle K'}$ ${\displaystyle K}$ ${\displaystyle K\vdash K'}$ ${\displaystyle \delta (q,\sigma )=(q',\tau ,d)}$

• ${\displaystyle d=\downarrow ,u'=u,v'=v,\sigma '=\tau }$, or
• ${\displaystyle d=\leftarrow ,u'\sigma '=u,v'=\tau v}$, or
• ${\displaystyle d=\rightarrow ,u'=u\tau ,\sigma 'v'=v}$, or
• ${\displaystyle d=\rightarrow ,u'=u\tau ,v=v'=\epsilon }$and . ${\displaystyle \sigma '=\sqcup }$

Write for configurations and if there is a sequence of configurations with . ${\displaystyle K\vdash ^{*}K'}$ ${\displaystyle K}$ ${\displaystyle K'}$ ${\displaystyle K_{1},\ldots ,K_{m}}$ ${\displaystyle K\vdash K_{1}\vdash \ldots \vdash K_{m}\vdash K'}$

calculation

The start configuration of when entered is . A configuration is called a hold configuration , if . Then the sequence of configurations is called computation of , if for all . accepts the input if and rejects it if . ${\displaystyle M}$ ${\displaystyle (x,y)\in \Sigma ^{*}}$ ${\displaystyle K_{0}=(s,\epsilon ,\triangleright ,x\#y)}$ ${\displaystyle K_{m}=(q,u,\sigma ,v)}$ ${\displaystyle q\in \{+,-\}}$ ${\displaystyle K_{0},\ldots ,K_{m}}$ ${\displaystyle M}$ ${\displaystyle K_{i}\vdash K_{i+1}}$ ${\displaystyle i\in \{0,\ldots ,m-1\}}$ ${\displaystyle M}$ ${\displaystyle K_{m}=(+,u,\sigma ,v)}$ ${\displaystyle K_{m}=(-,u,\sigma ,v)}$

running time

Let be a calculation of at input , then the running time is . If there is no calculation for the input (i.e. the Turing machine does not hold), then applies . ${\displaystyle K_{0},\ldots ,K_{m}}$ ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle t_{M}(x)=m}$ ${\displaystyle x}$ ${\displaystyle t_{M}(x)=\bot }$

In Turing machines, the length of the input string is viewed as the input variable. A function is then called the time limit of if applies to all . ${\displaystyle T:\mathbb {N} \rightarrow \mathbb {N} }$ ${\displaystyle M}$ ${\displaystyle t_{M}(x)\in {\mathcal {O}}(T(|x|))}$ ${\displaystyle x\in \Sigma ^{*}}$

Generated language

Every Turing machine with additional input generates a language - the set of inputs accepted by. ${\displaystyle M}$ ${\displaystyle L(M)=\{x\in \Sigma ^{*}\mid M{\text{ akzeptiert }}x\}}$ ${\displaystyle M}$

Multi-string Turing machine

The Turing machine with additional input can be expanded by allowing the use of several string bands. The machine then has its own read / write head for each tape. The definition of a -String Turing machine with additional input differs from the Turing machine with additional input in the following terms: ${\displaystyle k}$ ${\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,s)}$

Transfer function

${\displaystyle \delta :Q\times \Gamma ^{k}\rightarrow (Q\cup \{+,-\})\times \Gamma ^{k}\times \{\leftarrow ,\downarrow ,\rightarrow \}^{k}}$ The next state depends on the current state and the current character of all bands.

String pointer description

${\displaystyle (u,\sigma ,v),u,v\in \Gamma ^{*},\sigma \in \Gamma }$is an auxiliary term and indicates that the read / write head is on the character , the string to the left and the string to the right . ${\displaystyle \sigma }$ ${\displaystyle u}$ ${\displaystyle v}$

configuration

${\displaystyle (q,s_{1},\ldots ,s_{k})}$consists of a state and a string pointer description for each band with . ${\displaystyle q\in Q}$ ${\displaystyle s_{1},\ldots ,s_{k}}$ ${\displaystyle s_{i}=(u_{i},\sigma _{i},v_{i})}$

Start configuration

${\displaystyle K_{0}=(s,(\varepsilon ,\triangleright ,x\#y),(\varepsilon ,\triangleright ,\varepsilon ),\ldots ,(\varepsilon ,\triangleright ,\varepsilon ))}$when entering . ${\displaystyle x\#y}$

Successor configuration

${\displaystyle K'=(q',s_{1}',\ldots ,s_{k}')}$is successor configuration of , if and for all applies: ${\displaystyle K=(q,s_{1},\ldots ,s_{k})}$ ${\displaystyle \delta (q,\sigma _{1},\ldots ,\sigma _{k})=(q',\tau _{1},\ldots ,\tau _{k},d_{1},\ldots ,d_{k})}$ ${\displaystyle i}$

• ${\displaystyle d_{i}=\downarrow ,u_{i}'=u_{i},v_{i}'=v_{i},\sigma _{i}'=\tau _{i}}$, or
• ${\displaystyle d_{i}=\leftarrow ,u_{i}'\sigma _{i}'=u_{i},v_{i}'=\tau _{i}v_{i}}$, or
• ${\displaystyle d_{i}=\rightarrow ,u_{i}'=u_{i}\tau _{i},\sigma _{i}'v_{i}'=v_{i}}$, or
• ${\displaystyle d_{i}=\rightarrow ,u_{i}'=u_{i}\tau _{i},v_{i}=v_{i}'=\epsilon }$and . ${\displaystyle \sigma _{i}'=\sqcup }$

Equivalence to the 1-string Turing machine with additional input

In keeping with the Church-Turing thesis , or its extended version, there is every string Turing machine with auxiliary input and time bound , a one-string Turing machine with auxiliary input, with time bound decides. So you can convert any multi-string Turing machine with additional input with polynomial extra effort into a single-string Turing machine. ${\displaystyle k}$ ${\displaystyle M}$ ${\displaystyle T}$ ${\displaystyle L(M)}$ ${\displaystyle {\mathcal {O}}(T^{2})}$

When designing Turing machines with additional input and polynomial runtime, it does not matter whether you define them as a multi-string or single-string Turing machine. In this case, the multi-string Turing machine can be defined so that the input is on the first tape and the additional input on the second, which simplifies the description of the Turing machine.

Space barrier

With multi-string Turing machines, a space limit can also be defined in addition to the time limit. In order to be able to define space barriers that are smaller than the input length, the model must be restricted in such a way that the input (and the additional input) cannot be used as a calculation place.

Read-only input tape

A -String Turing machine with additional input and read-only input tape is a -String Turing machine with additional input and the restriction by: is , so is (the input tape is not changed) and if , then is (the Turing machine cannot go beyond the right margin the input). ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,s)}$ ${\displaystyle \delta }$ ${\displaystyle \delta (q,\sigma _{1},\ldots ,\sigma _{k})=(q',\sigma _{1}',\ldots ,\sigma _{k}',d_{1},\ldots ,d_{k})}$ ${\displaystyle \sigma _{1}=\sigma _{1}'}$ ${\displaystyle \sigma _{1}=\sqcup }$ ${\displaystyle d_{1}=\leftarrow }$

Storage space requirements

The storage space required by a string Turing machine with additional input and read-only input tape for input and hold configuration is . ${\displaystyle k}$ ${\displaystyle M}$ ${\displaystyle x\#y}$ ${\displaystyle (q,(u_{1},\sigma _{1},v_{1}),\ldots ,(u_{k},\sigma _{k},v_{k}))}$ ${\displaystyle s_{M}(x\#y)=\Sigma _{i=2}^{k}|u_{i}\sigma _{i}v_{i}|}$

A function is then a space barrier for , if . ${\displaystyle S:\mathbb {N} \rightarrow \mathbb {R} }$ ${\displaystyle M}$ ${\displaystyle s_{M}(x)\in {\mathcal {O}}(S(|x|))}$

Guessing solutions

Often one speaks of “guessing” in connection with nondeterminism. Since this is also a form of nondeterminism (the freedom to choose the additional input), we often speak of guessing the solution as an additional input. What is meant is that the Turing machine with additional input can interpret the additional input as a solution candidate and rejects it if it is not a solution. The Turing machine is constructed in such a way that correctly guessed solutions are accepted and everything else is rejected. In this sense, the additional entry / solution can be advised. ${\displaystyle M}$ ${\displaystyle x}$

Equivalence to the nondeterministic Turing machine

The Turing machine with additional input is equivalent to the nondeterministic Turing machine , in which the deterministic Turing machine is extended by a transition relation instead of an exercise function. As a result, there can be several valid successor states from a configuration of the nondeterministic Turing machine. This model accepts an input if and only if there is an accepting computation on input . ${\displaystyle x}$ ${\displaystyle x}$

To a certain extent, with the Turing machine with additional input there is freedom of choice in the additional input and with the nondeterministic Turing machine in the choice of the successor configuration. For the simulation of the nondeterministic Turing machine by the Turing machine with additional input, the characters of the additional input can be used to clearly determine the next configuration of the nondeterministic Turing machine (based on the specific additional input). To simulate the Turing machine with additional input by the nondeterministic Turing machine, the characters of the additional input can be determined by the possible successor configurations (there is a possible successor configuration for every possible character of the additional input).

Advantage over the nondeterministic Turing machine

The description and formalization of nondeterministic Turing machines is simplified by this model, since one can explicitly fall back on a solution candidate (the additional input).

The importance of this model becomes particularly clear when characterizing NP: Intuitively speaking, the set NP is the set of problems whose solution (given by the additional input) can be verified in polynomial time.

Significance in complexity theory

NTIME

The non-deterministic time classes NTIME for time limits are formed by the Turing machine with additional input and the associated term of the runtime . ${\displaystyle (f)}$ ${\displaystyle f}$

This also defines NP , the set of all languages for which there is a Turing machine with additional input and a polynomial runtime limit, so that ( decides ). ${\displaystyle L}$ ${\displaystyle M}$ ${\displaystyle L=L(M)}$ ${\displaystyle M}$ ${\displaystyle L}$

${\displaystyle {\mbox{NP}}=\bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}\left(n^{k}\right)}$

Also nexptime is defined in this way. The set of all languages for which there is a Turing machine with additional input and exponential runtime bound, so that . ${\displaystyle L}$ ${\displaystyle M}$ ${\displaystyle L=L(M)}$

${\displaystyle {\mbox{NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}\left(2^{n^{k}}\right).}$

NSPACE

The NSPACE classes can be defined with the extension to multi-string Turing machines with additional input and read-only input tape .

${\displaystyle {\text{NSPACE}}_{k}(S)}$is the set of all languages for which there is a k-string Turing machine with additional input and read-only input tape, which decides with a space limit and is then formed. ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle S}$ ${\displaystyle {\mbox{NSPACE}}(S)=\bigcup _{k\geq 2}{\mbox{NSPACE}}_{k}(S)}$

Above are the classes

• NL , logarithmic space, with , ${\displaystyle {\mbox{NL}}={\mbox{NSPACE}}(\log n)}$
• NPSPACE , polynomial space, with and ${\displaystyle {\mbox{NPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}\left(n^{k}\right)}$
• NEXPTIME , exponential space, formed with . ${\displaystyle {\mbox{NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}\left(2^{n^{k}}\right)}$

literature

• Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach . 1st edition. Cambridge University Press, 2009, ISBN 0-521-42426-7 .
• Lecture Complexity Theory WS 09/10, Prof. Dr. Thomas Schwentick