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 finitestate automaton. From Nondeterminism to Determinism The following theorem relates nondeterminism to determinism in Turing transducers. Theorem 4.3.1 Every Turing transducer M1 has a corresponding deterministic Turing transducer M2 such that a. M2 accepts the same inputs as M1, that is, L(M2) = L(M1). b. M2 halts on exactly the same inputs as M1. c. M2 has an output y on a given input only if M1 can output y on such an input, that is, R(M2) R(M1). Proof Consider any m auxiliary-work-tape Turing transducer M1 and any input x for M1. Let 1, . . . , r denote the transition rules of M1. Let Ci1 it denote the configuration that M1 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 Ci1 it is assumed to denote an undefined configuration. The desired Turing transducer M2 can be a deterministic m + 1 auxiliary-work-tape Turing transducer of the following form. M2 on the given input x searches along the sequence C , C1, C2, . . . , Cr, C11, C12, . . . , Crr, C111, C112, . . . , Crrr, . . . for an accepting configuration of M1 on input x. M2 halts in an accepting configuration upon reaching an accepting configuration of M1. M2 halts in a rejecting configuration upon reaching a t, such that all the configurations Ci1 it of M1 are undefined. In an accepting computation, M2 provides the output associated with the accepting configuration of M1. A computation of M2 on input x proceeds as follows. M2 lists the strings = i1 it 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.

a.

M2 determines a string = i1 it in {1, . . . , r}*, such that Ci1 it is an accepting configuration of M1 on input x. Such a configuration corresponds to the accepting computation C Ci1 Ci1 it of M1 on input x. In such a case, M2 has the same output as the accepting computation of M1, and it halts in an accepting configuration. M2 finds out whether a given Ci1 it is a defined configuration by scanning over the string i1 it while trying to trace a sequence of moves C Ci1 Ci1 it of M1 on input x. During the tracing M2 ignores the output of M1. M2 uses its input head to trace the input head movements of M1. M2 uses its finite-state control to record the states of M1. M2 uses m of its auxiliary work tapes to trace the changes in the corresponding auxiliary work tapes of M1. M2 determines the output of M1 that corresponds to a given string i1 it by scanning the string and extracting the output associated with the corresponding sequence of transition rules i1 it.

b. M2 determines a t, such that Ci1 it is an undefined configuration for all the strings = i1 it in {1, . . . , r}*. In such a case, M2 halts in a nonaccepting configuration. M2 determines that a given string i1 it corresponds to an undefined configuration Ci1 it by verifying that M1 has no sequence of moves of the form C Ci1 Ci1 it on input x. The verification is made by a tracing similar to the one described in (a).

M2 uses a flag in its finite-state control for determining the existence of a t, such that Ci1 it in {1, . . . , r}*. M2 sets the flag to 1 it are undefined configurations for all i1 whenever t is increased by 1. M2 sets the flag to 0 whenever a string i1 it is determined, such that Ci1 it is a defined configuration. M2 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 M1 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.)

M1 computes the relation { (wwrev, wrev) | w is in {a, b}+ }. On input abba the Turing transducer M1 has an accepting computation C C1 C12 C124 C1246 C12465 C124657 that corresponds to the sequence of transition rules 1 2 4 6 5 7. Let M2 be the deterministic Turing transducer in Figure 4.3.2(b). M2 computes the same function as M1 and is similar to the Turing transducer in the proof of Theorem 4.3.1. The main difference is that here M2 halts only in its accepting computations. On input abba the Turing transducer M2 lists the strings in {1, . . . , 7}* on its first auxiliary work tape, one at a time, in canonical order. The Turing transducer M2 checks whether each of those strings = i1 it defines an accepting computation C Ci1 Ci1 it of M1.

The Turing transducer M2 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 , 1, . . . , 7, 1 1, . . . , 7 7, . . . , 1 1 1 1 1 1, . . . , 1 2 4 6 5 6, respectively, corresponds to an accepting computation of M1 on input abba. Then M2 determines that the string "1 2 4 6 5 7", which represents the sequence 1 2 4 6 5 7, corresponds to an accepting computation of M1 on input abba. With this determination, the Turing transducer M2 writes the output of this computation, and halts in an accepting configuration. M2 uses the component "Trace on " to check, by tracing on the given input, that there exists a sequence of moves of M1 of the form C Ci1 Ci1 it, for the = i1 it that is stored in the first auxiliary work tape of M2. Such a sequence of moves corresponds to an accepting computation of M1 if and only if it = 7. The component "Trace on " is essentially M1 modified to follow the sequence of transition rules dictated by the content of the first auxiliary work tape of M2. M2 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 M2 is a deterministic, two auxiliary-work-tape Turing transducer. Proposition 4.3.1 Each deterministic Turing transducer M1 has an equivalent deterministic Turing transducer M2 with two auxiliary work tapes. Proof Consider any deterministic, m auxiliary-work-tape Turing transducer M1. On a given input x, the Turing transducer M2 simulates the computation C0 C1 C2 that M1 has on input x. M2 starts by recording the initial configuration C0 = (q0x$, q0, . . . , q0, ) of M1 on input x. Then M2 repeatedly replaces the recorded configuration Ci of M1, with the next configuration Ci+1 of the simulated computation. M2 halts upon reaching a halting configuration of M1. M2 halts in an accepting configuration if and only if it determines that M1 does so. M2 records a configuration Ci = (uqv, u1qv1, . . . , umqvm, w) of M1 in the following manner. The state q is stored in the finite-state control of M2. The input head location of M1 is recorded by the location of the input head of M2. The output w of M1 is recorded on the output tape of M2. The tuple (u1, v1, . . . , um, vm) is stored as a string of the form #u1#v1# #um#vm# on an auxiliary work tape of M2, where # is assumed to be a new symbol. The tuple is stored on the first auxiliary work tape of M2 when i is even and on the second auxiliary work tape when i is odd.

The Turing transducer M2 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 u1 = v1 = = um = vm = . M2 determines the transition rule (q, a, b1, b2, . . . , bm, p, d0, c1, d1, c2, d2, . . . , cm, dm, ) to be used in a given move by getting q from the finite-state control, a from the input tape, and b1, . . . , bm from the auxiliary work tape that records #u1#v1# #um#vm#. Example 4.3.2 Let M1 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.

The Turing transducer M2 in the proof of Proposition 4.3.1 can use a segment D as in Figure 4.3.3(b) to determine the transition rule that M1 uses on moving from state q1. D assumes that M1 is in configuration (uq1v, u1q1v1, . . . , umq1vm, w), that M2 is in state q1, that #u1#v1# #um#vm# is stored on the first auxiliary work tape of M2, and that the head of the first auxiliary work tape is placed on the first symbol of #u1#v1# #um#vm#. 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] The finiteness of memory and the restricted access to it, respectively, constrain the capabilities of finite-state transducers and pushdown transducers. In the case of Turing transducers, however, none of the constraints made on memory is significant, because they can all be removed and still the transducers acquire no more definition power. Yet there are languages that Turing transducers cannot decide or even accept. The intuitive explanation for this phenomenon is that each Turing transducer is a description of a language (i.e., a set of strings), which itself has a description by a string. Consequently, there are more languages than Turing transducers. Specifically, each language over an alphabet is a subset of *. The set of all the languages over is the power set , which is uncountably infinite. On the other hand, the number of Turing transducers that specify languages over is countably infinite, because they are all representable by strings from *. A Proof by a Generic Approach The proof of the following theorem implicitly uses the previous observation. As with the limitations of the finite-memory programs in Section 2.4 and the limitations of the recursive finite-domain programs in Section 3.4, we here use a proof by reduction to contradiction. The variant of the technique used here is called a proof by diagonalization , owing to the employment of the diagonal of a table for choosing the language that provides the contradiction. Convention In this chapter xi will denote the ith string in the canonically ordered set of binary strings. Similarly, Mi will denote the Turing machine that has a standard binary representation equal to the ith string, in the canonically ordered set of the standard binary representations of

Turing machines. (With no loss of generality it is assumed that isomorphic Turing machines are equal.) Theorem 4.5.1 There are nonrecursively enumerable languages, that is, languages that cannot be accepted by any Turing machine. Proof Let Laccept be the language { (M, x) | The turing machine M accepts the string x }. The language Laccept has a table representation Taccept in which the rows are indexed by M1, M2, M3, . . . the columns are indexed by x1, x2, x3, . . . and each entry at row Mi and column xj holds either 1 or 0, depending on whether Mi accepts xj or not (see Figure 4.5.1(a)).

Figure 4.5.1

(a) Hypothetical table Taccept indicating acceptance of word xj by Turing machine Mi. (b) Representations of Ldiagonal_accept and Ldiagonal_reject in Taccept.

Each language L can be represented by a vector that holds 1 at its jth entry if xj is in L, and holds 0 at its jth entry if xj is not in L. In particular, the language L(Mi) is represented by the ith row in Taccept. The approach of the proof is to find a language that corresponds to no row in Taccept, and so cannot be accepted by any Turing machine. One such option is to construct the language from the diagonal of Taccept. The diagonal of the table Taccept is a representation of Ldiagonal_accept = { x | x = xi and Mi accepts xi }. Let Ldiagonal_reject denote the complementation { x | x = xi and Mi does not accept xi } of Ldiagonal_accept. Each Turing machine that accepts Ldiagonal_reject implies some row Mk in Taccept that holds values complementing those in the diagonal at similar locations (see Figure 4.5.1(b)). In particular, the kth digit in row Mk must be the complementation of the kth digit in the diagonal.

However, the kth digit in row Mk is also the kth digit in the diagonal, consequently implying that no Turing machine can accept the language Ldiagonal_reject. The discussion above can be formalized in the following way. For the sake of the proof assume that Ldiagonal_reject is accepted by some Turing machine M. Then there exists an index k such that M = Mk. Now consider the string xk. For xk either of the following cases must hold. Case 1 xk is in Ldiagonal_reject. In Case 1, the assumption that the Turing machine Mk accepts the language Ldiagonal_reject implies that Mk accepts the string xk. Alternatively, the definition of Ldiagonal_reject implies that Mk does not accept xk. Thus Case 1 cannot hold. Case 2 xk is not in Ldiagonal_reject. Similarly, in Case 2, the assumption that Mk accepts Ldiagonal_reject implies that Mk does not accept xk. And alternatively, the definition of Ldiagonal_reject implies that Mk accepts xk. Hence, implying that Case 2 cannot hold either. The result follows because for the assumption that there is a Turing machine M that accepts Ldiagonal_reject to hold, either Case 1 or Case 2 must hold. By Church's thesis a decision problem is partially decidable if and only if there is a Turing machine that accepts exactly those instances of the problem that have the answer yes. Similarly, the problem is decidable if and only if there is a Turing machine that accepts exactly those instances that have the answer yes and that also halts on all instances of answer no. The proof of Theorem 4.5.1 together with Church's thesis imply the following theorem. The importance of this theorem stems from its exhibiting the existence of an undecidable problem, and from its usefulness for showing the undecidability of other problems by means of reducibility. Theorem 4.5.2 The membership problem is undecidable, and, in fact, not even partially decidable for Ldiagonal_reject. Proofs by Reduction A proof of the undecidability of a given problem by means of reducibility runs as follows (see Figure 4.5.2

Figure 4.5.2 Reduction of KB to KA. and recall Section 1.5). For the purpose of the proof assume that the given problem KA is decidable by some algorithm A. Find algorithms Tf and Tg that together with A provide an algorithm B, for solving a known undecidable problem KB in the following manner. B, when given an instance I, uses Tf to obtain an instance I' of KA, employs A on I' to obtain the output S' that A provides for I', and then introduces S' to Tg to obtain the output S of B. The undecidability of KA then follows, because otherwise the decidability of a problem KB that is known to be undecidable would have been implied. The proof of the following theorem is an example of a proof that uses reduction between undecidable problems. Theorem 4.5.3 undecidable. The membership problem for Turing machines or, equivalently, for Laccept is

Proof For the purpose of the proof assume that the given problem is decidable by a hypothetical algorithm A (see Figure 4.5.3).

Figure 4.5.3

Reduction of the membership problem for Ldiagonal_reject to the membership problem for Laccept.

Then the membership problem for Ldiagonal_reject can be decided by an algorithm B of the following form. The algorithm B on a given input x uses a converter Tf to obtain a pair (Mi, xi) such that x = xi. Tf can find the index i for x by listing the binary strings , 0, 00, . . . , x in canonical order, and determining the index of x in the list. Tf can find Mi by listing the binary strings , 0, 1, 00, . . . in canonical order until the ith standard binary representation of a Turing machine is reached. The output (Mi, xi) of Tf is provided by B to A. Finally B employs Tg for determining that x is in Ldiagonal_reject if A determines that x is not in Laccept, and that x is not in Ldiagonal_reject if A determines that x is in Laccept. The result follows from the undecidability of the membership problem for the language Ldiagonal_reject (see Theorem 4.5.2).

The previous theorem and the next one imply that there are nonrecursive languages that are recursively enumerable. Theorem 4.5.4 The membership problem for Turing machines or, equivalently, for Laccept is partially decidable. Proof Laccept is accepted by a nondeterministic Turing machine similar to the universal Turing machine M2 in the proof of Theorem 4.4.1. Many problems, including the one in the following theorem, can be shown to be undecidable by reduction from the membership problem for Turing machines. Theorem 4.5.5 The halting problem for Turing machines is undecidable.

Proof A Turing machine M does not halt on a given input x if and only if M does not accept x and on such an input M can have an infinite sequence of moves. An answer no to the halting problem for an instance (M, x) implies the same answer to the membership problem for the instance (M, x). However, an answer yes to the halting problem for an instance (M, x) can correspond to either an answer yes or an answer no to the membership problem for the instance (M, x). The proof of the theorem relies on the observation that each Turing machine M can be modified to avoid the rejection of an input in a halting configuration. With such a modification, an answer yes to the halting problem at (M, x) also implies the same answer to the membership problem at (M, x). For the purpose of the proof assume that the halting problem for Turing machines is decidable by a hypothetical algorithm A. Then an algorithm B, which decides the membership problem for Turing machines, can be constructed employing a translator Tf and the hypothetical algorithm A in the following manner (see Figure 4.5.4).

Figure 4.5.4

Reduction of the membership problem for Turing machines to the halting problem for Turing machines.

B provides any given instance (M, x) to Tf . Tf constructs from the given m auxiliary-work-tape Turing machine M an equivalent Turing machine M , that halts on a given input if and only if

M accepts the input. Specifically, M is just the Turing machine M with a "looping" transition rule of the form (q, a, b1, . . . , bm, q, 0, b1, 0, . . . , bm, 0) added for each nonaccepting state q, each input symbol a, and each combination of auxiliary work-tape symbols b1, . . . , bm on which M has no next move. B feeds (M , x) to A and assumes the output of A. The result follows from Theorem 4.5.3, showing that the membership problem is undecidable for Laccept. Example 4.5.1 Let M be the Turing machine in Figure 4.5.5(a).

Figure 4.5.5 (a) A Turing machine M. (b) A Turing machine M

that is equivalent to M.

Upon reaching state q0 the Turing machine M enters a nonaccepting halting configuration if both the input head and the auxiliary work-tape head scan the symbol a. M can be modified to enter an infinite loop in such a configuration by forcing the Turing machine to make a move that does not change the configuration, that is, by introducing a transition rule of the form (q0, a, a, q0, 0, a, 0). Using the notations in the proof of Theorem 4.5.5, M is the Turing machine in Figure 4.5.5(b).

The next theorem provides another example of a proof of undecidability by means of reduction. Theorem 4.5.6 The problem of deciding for any given Turing machine whether the machine accepts a regular language is undecidable. Proof Consider any instance (M, x) of the membership problem for Turing machines. From (M, x) construct a Turing machine Mx that accepts { aibi | i 0 } if M accepts x, and that accepts the empty set if M does not accept x. Specifically, Mx on any given input w starts the computation by checking whether w = aibi for some i 0. If the equality w = aibi holds for no i 0, then Mx rejects w. Otherwise, Mx simulates the computation of M on input x. In the latter case, Mx accepts w if it determines that M accepts x, and Mx rejects w if it determines that M rejects x.

Consequently, Mx accepts a regular language (which is the empty set) if and only if M does not accept x. The result follows from the undecidability of the membership problem for Turing machines (see Theorem 4.5.3). Example 4.5.2 Let M be the Turing machine given in Figure 4.5.6(a).

Figure 4.5.6

(a) A Turing machine M. (b) A corresponding Turing machine Mababc that accepts { aibi | i 0 } if and only if M accepts ababc.

Let x = ababc. Then Mx in the proof of Theorem 4.5.6 can be as in Figure 4.5.6(b). Mx has one more auxiliary work tape than M and consists of three subcomponents M1, M2, and M3. M1 checks that the given input is of the form aibi for some i 0. M2 stores the string x in the first auxiliary work tape. M3 is just M modified to read its input from the first auxiliary work tape. and are the symbols used in the first auxiliary work tape representing the endmarkers and $, respectively. The universe of the undecidable problems includes numerous examples. For many of these problems the proof of undecidability is quite involved. The selection that has been made here should be appreciated at least for the simplification that it allows in introducing the concepts under consideration. [next] [prev] [prev-tail] [front] [up]