4.3  Nondeterminism versus Determinism

      From Nondeterminism to Determinism
      Deterministic Turing Transducers with Two AuxiliaryWork Tapes

Nondeterministic finite-state transducers can compute some functions that no deterministic finite-state transducer can. Similarly, nondeterministic pushdown automata can accept some languages that no deterministic pushdown automaton can. However, every language that is accepted by a nondeterministic finite-state automaton is also accepted by a deterministic finite-state automaton.

 From Nondeterminism to Determinism

The following theorem relates nondeterminism to determinism in Turing transducers.

Theorem 4.3.1    Every Turing transducer M₁ has a corresponding deterministic Turing transducer M₂ such that

1.  M₂ accepts the same inputs as M₁, that is, L(M₂) = L(M₁).
2.  M₂ halts on exactly the same inputs as M₁.
3.  M₂ has an output y on a given input only if M₁ can output y on such an input, that is, R(M₂) R(M₁).

Proof     Consider any m auxiliary-work-tape Turing transducer M₁ and any input x for M₁. Let ₁, . . . , _r denote the transition rules of M₁. Let C_{i1 it} denote the configuration that M₁ reaches on input x from its initial configuration, through a sequence of moves that uses the sequence of transition rules _{i1 it}. If no such sequence of moves is possible, then C_{i1 it} is assumed to denote an undefined configuration. The desired Turing transducer M₂ can be a deterministic m + 1 auxiliary-work-tape Turing transducer of the following form.

M₂ on the given input x searches along the sequence C, C₁, C₂, . . . , C_r, C₁₁, C₁₂, . . . , C_rr, C₁₁₁, C₁₁₂, . . . , C_rrr, . . . for an accepting configuration of M₁ on input x.

M₂ halts in an accepting configuration upon reaching an accepting configuration of M₁. M₂ halts in a rejecting configuration upon reaching a t, such that all the configurations C_{i1 it} of M₁ are undefined. In an accepting computation, M₂ provides the output associated with the accepting configuration of M₁.

A computation of M₂ on input x proceeds as follows. M₂ lists the strings = i₁ i_t in {1, . . . , r}* on its first auxiliary work tape, one at a time, in canonical order until either of the following two conditions holds (see the flowchart in Figure 4.3.1).

Figure 4.3.1 "Simulation" of a nondeterministic Turing transducer M1 by a deterministic Turing transducer M2.

1.  M₂ determines a string = i₁ i_t in {1, . . . , r}*, such that C_{i1 it} is an accepting configuration of M₁ on input x. Such a configuration corresponds to the accepting computation C C_i1 C_{i1 it} of M₁ on input x. In such a case, M₂ has the same output as the accepting computation of M₁, and it halts in an accepting configuration.

   M₂ finds out whether a given C_{i1 it} is a defined configuration by scanning over the string i₁ i_t while trying to trace a sequence of moves C C_i1 C_{i1 it} of M₁ on input x. During the tracing M₂ ignores the output of M₁.

   M₂ uses its input head to trace the input head movements of M₁. M₂ uses its finite-state control to record the states of M₁. M₂ uses m of its auxiliary work tapes to trace the changes in the corresponding auxiliary work tapes of M₁.

   M₂ determines the output of M₁ that corresponds to a given string i₁ i_t by scanning the string and extracting the output associated with the corresponding sequence of transition rules _{i1 it}.

2.  M₂ determines a t, such that C_{i1 it} is an undefined configuration for all the strings = i₁ i_t in {1, . . . , r}*. In such a case, M₂ halts in a nonaccepting configuration.

   M₂ determines that a given string i₁ i_t corresponds to an undefined configuration C_{i1 it} by verifying that M₁ has no sequence of moves of the form C C_i1 C_{i1 it} on input x. The verification is made by a tracing similar to the one described in (a).

   M₂ uses a flag in its finite-state control for determining the existence of a t, such that C_{i1 it} are undefined configurations for all i₁ i_t in {1, . . . , r}*. M₂ sets the flag to 1 whenever t is increased by 1. M₂ sets the flag to 0 whenever a string i₁ i_t is determined, such that C_{i1 it} is a defined configuration. M₂ determines that the property holds whenever t is to be increased on a flag that contains the value of 1.

Example 4.3.1    Let M₁ be the nondeterministic, one auxiliary-work-tape Turing transducer given in Figure 4.3.2(a).

Figure 4.3.2 (a) A nondeterministic Turing transducer M. (b) A deterministic Turing transducer that computes the same function as M. (The asterisk * stands for the current symbol under the corresponding head.)

Let M₂ be the deterministic Turing transducer in Figure 4.3.2(b). M₂ computes the same function as M₁ and is similar to the Turing transducer in the proof of Theorem 4.3.1. The main difference is that here M₂ halts only in its accepting computations.

On input abba the Turing transducer M₂ lists the strings in {1, . . . , 7}* on its first auxiliary work tape, one at a time, in canonical order. The Turing transducer M₂ checks whether each of those strings = i₁ i_t defines an accepting computation C C_i1 C_{i1 it} of M₁.

The Turing transducer M₂ detects that none of the strings " ", "1", . . . , "7", "1 1", . . . , "7 7", . . . , "1 1 1 1 1 1", . . . , "1 2 4 6 5 6", representing the sequences , ₁, . . . , ₇, ₁₁, . . . , ₇₇, . . . , ₁₁₁₁₁₁, . . . , ₁₂₄₆₅₆, respectively, corresponds to an accepting computation of M₁ on input abba. Then M₂ determines that the string "1 2 4 6 5 7", which represents the sequence ₁₂₄₆₅₇, corresponds to an accepting computation of M₁ on input abba. With this determination, the Turing transducer M₂ writes the output of this computation, and halts in an accepting configuration.

M₂ uses the component "Trace on " to check, by tracing on the given input, that there exists a sequence of moves of M₁ of the form C C_i1 C_{i1 it}, for the = i₁ i_t that is stored in the first auxiliary work tape of M₂. Such a sequence of moves corresponds to an accepting computation of M₁ if and only if _it = ₇. The component "Trace on " is essentially M₁ modified to follow the sequence of transition rules dictated by the content of the first auxiliary work tape of M₂.

M₂ uses the components "Find the end of ," "Determine the next ," "Find the blank before ," "Find ¢ on the input tape," and "Erase the second auxiliary work tape" to prepare itself for the consideration of the next from the canonically ordered set {1, . . . , 7}*.

 Deterministic Turing Transducers with Two Auxiliary
Work Tapes

The following proposition implies that Theorem 4.3.1 also holds when M₂ is a deterministic, two auxiliary-work-tape Turing transducer.

Proposition 4.3.1    Each deterministic Turing transducer M₁ has an equivalent deterministic Turing transducer M₂ with two auxiliary work tapes.

Proof     Consider any deterministic, m auxiliary-work-tape Turing transducer M₁. On a given input x, the Turing transducer M₂ simulates the computation C₀ C₁ C₂ that M₁ has on input x.

M₂ starts by recording the initial configuration C₀ = (¢q₀x$, q₀, . . . , q₀, ) of M₁ on input x. Then M₂ repeatedly replaces the recorded configuration C_i of M₁, with the next configuration C_i+1 of the simulated computation.

M₂ halts upon reaching a halting configuration of M₁. M₂ halts in an accepting configuration if and only if it determines that M₁ does so.

M₂ records a configuration C_i = (uqv, u₁qv₁, . . . , u_mqv_m, w) of M₁ in the following manner. The state q is stored in the finite-state control of M₂. The input head location of M₁ is recorded by the location of the input head of M₂. The output w of M₁ is recorded on the output tape of M₂. The tuple (u₁, v₁, . . . , u_m, v_m) is stored as a string of the form #u₁#v₁# #u_m#v_m# on an auxiliary work tape of M₂, where # is assumed to be a new symbol. The tuple is stored on the first auxiliary work tape of M₂ when i is even and on the second auxiliary work tape when i is odd.

The Turing transducer M₂ starts a computation by laying a string of (2m + 1) symbols # in the first auxiliary work tape. Such a string represents the situation in which u₁ = v₁ = = u_m = v_m = . M₂ determines the transition rule (q, a, b₁, b₂, . . . , b_m, p, d₀, c₁, d₁, c₂, d₂, . . . , c_m, d_m, ) to be used in a given move by getting q from the finite-state control, a from the input tape, and b₁, . . . , b_m from the auxiliary work tape that records #u₁#v₁# #u_m#v_m#.

Example 4.3.2    Let M₁ be the Turing transducer whose transition diagram is given in Figure 4.3.3(a).

Figure 4.3.3 The segment of the Turing transducer in part (b) determines the transition rule used by the Turing transducer in part (a) from state q1.

D assumes that M₁ is in configuration (uq₁v, u₁q₁v₁, . . . , u_mq₁v_m, w), that M₂ is in state q₁, that #u₁#v₁# #u_m#v_m# is stored on the first auxiliary work tape of M₂, and that the head of the first auxiliary work tape is placed on the first symbol of #u₁#v₁# #u_m#v_m#.

Since Turing transducers can compute relations that are not functions, it follows that nondeterministic Turing transducers have more definition power than deterministic Turing transducers. However, Theorem 4.3.1 implies that such is not the case for Turing machines. In fact, Theorem 4.3.1 together with Proposition 4.3.1 imply the following corollary.

Corollary 4.3.1    A function is computable (or, respectively, partially computable) by a Turing transducer if and only if it is computable (or, respectively, partially computable) by a deterministic, two auxiliary-work-tape Turing transducer.

[next] [prev] [prev-tail] [front] [up]