4.5  Undecidability

      A Proof by a Generic Approach
      Proofs by Reduction

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 x_i will denote the ith string in the canonically ordered set of binary strings. Similarly, M_i 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 L_accept be the language { (M, x) | The turing machine M accepts the string x }. The language L_accept has a table representation T_accept in which the rows are indexed by M₁, M₂, M₃, . . . the columns are indexed by x₁, x₂, x₃, . . . and each entry at row M_i and column x_j holds either 1 or 0, depending on whether M_i accepts x_j 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 x_j is in L, and holds 0 at its jth entry if x_j is not in L. In particular, the language L(M_i) is represented by the ith row in T_accept.

The approach of the proof is to find a language that corresponds to no row in T_accept, and so cannot be accepted by any Turing machine. One such option is to construct the language from the diagonal of T_accept.

The diagonal of the table T_accept is a representation of L_{diagonal_accept} = { x | x = x_i and M_i accepts x_i }. Let L_{diagonal_reject} denote the complementation { x | x = x_i and M_i does not accept x_i } of L_{diagonal_accept}. Each Turing machine that accepts L_{diagonal_reject} implies some row M_k in T_accept that holds values complementing those in the diagonal at similar locations (see Figure 4.5.1(b)). In particular, the kth digit in row M_k must be the complementation of the kth digit in the diagonal. However, the kth digit in row M_k is also the kth digit in the diagonal, consequently implying that no Turing machine can accept the language L_{diagonal_reject}.

The discussion above can be formalized in the following way. For the sake of the proof assume that L_{diagonal_reject} is accepted by some Turing machine M. Then there exists an index k such that M = M_k. Now consider the string x_k. For x_k either of the following cases must hold.

Case 1

x_k is in L_{diagonal_reject}. In Case 1, the assumption that the Turing machine M_k accepts the language L_{diagonal_reject} implies that M_k accepts the string x_k. Alternatively, the definition of L_{diagonal_reject} implies that M_k does not accept x_k. Thus Case 1 cannot hold.

Case 2

x_k is not in L_{diagonal_reject}. Similarly, in Case 2, the assumption that M_k accepts L_{diagonal_reject} implies that M_k does not accept x_k. And alternatively, the definition of L_{diagonal_reject} implies that M_k accepts x_k. Hence, implying that Case 2 cannot hold either.

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 L_{diagonal_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.

The proof of the following theorem is an example of a proof that uses reduction between undecidable problems.

Theorem 4.5.3    The membership problem for Turing machines or, equivalently, for L_accept is undecidable.

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.

The algorithm B on a given input x uses a converter T_f to obtain a pair (M_i, x_i) such that x = x_i. T_f 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. T_f can find M_i 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 (M_i, x_i) of T_f is provided by B to A. Finally B employs T_g for determining that x is in L_{diagonal_reject} if A determines that x is not in L_accept, and that x is not in L_{diagonal_reject} if A determines that x is in L_accept.

The result follows from the undecidability of the membership problem for the language L_{diagonal_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 L_accept is partially decidable.

Proof     L_accept is accepted by a nondeterministic Turing machine similar to the universal Turing machine M₂ 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 T_f 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 T_f . T_f 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, b₁, . . . , b_m, q, 0, b₁, 0, . . . , b_m, 0) added for each nonaccepting state q, each input symbol a, and each combination of auxiliary work-tape symbols b₁, . . . , b_m 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 L_accept.

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.

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 M_x that accepts { aⁱbⁱ | i 0 } if M accepts x, and that accepts the empty set if M does not accept x.

Specifically, M_x on any given input w starts the computation by checking whether w = aⁱbⁱ for some i 0. If the equality w = aⁱbⁱ holds for no i 0, then M_x rejects w. Otherwise, M_x simulates the computation of M on input x. In the latter case, M_x accepts w if it determines that M accepts x, and M_x rejects w if it determines that M rejects x.

Consequently, M_x 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.

M₁ checks that the given input is of the form aⁱbⁱ for some i 0. M₂ stores the string x in the first auxiliary work tape. M₃ 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]