COMS W3261 CS Theory
Lecture 15: The Diagonalization Language

1. Reducing One Problem to Another

• Suppose we have an algorithm A to transform instances of one problem P₁ to instances of another problem P₂ in such a way that a string w is in P₁ if and only if the transformed string A(w) is in P₂. What this implies is that we can solve instances of problem P₁ by converting them to instances of problem P₂ and then using the solution to problem P₂ to answer the original question. If we can do this, then we will say that A is a reduction of P₁ to P₂.
• Note that a reduction from P₁ to P₂ must turn every instance of P₁ with a yes answer to an instance of P₂ with a yes answer, and every instance of P₁ with a no answer to an instance of P₂ with a no answer.
• We will frequently use this technique to show that problem P₂ is as hard as problem P₁.
• The direction of the reduction is important.
• For example, if there is a reduction from P₁ to P₂ and if P₁ is not recursive, then P₂ cannot be recursive. (Why?)
• Similarly, if there is a reduction from P₁ to P₂ and if P₁ is not recursively enumerable, then P₂ cannot be recursively enumerable. (Why?)

2. Enumerating the Binary Strings

• In many proofs involving Turing machines, we need to enumerate the binary strings and encode Turing machines so that we can refer to the ith binary string as w_i and the ith Turing machine as M_i.
• The binary strings are easy to enumerate. If w is a binary string, we shall treat 1w as the binary integer i so we can call w the ith string.
• Using this encoding, the empty string is the first string, 0 the second, 1 the third, 00 the fourth, 01 the fifth, and so on. Henceforth we will refer to the ith string as w_i.

3. Codes for Turing machines

• We will now define a binary code for all Turing machines with the input alphabet {0, 1} so that each Turing machine can be represented by a binary string. This will allow us to talk about the ith Turing machine as M_i. We will adopt the following conventions:
• We assume the states are q₁, q₂, . . . , q_r for some r. We assume q₁ will always be the start state. We assume q₂ will be the only accepting state. We need only one accepting state if we assume the Turing machine halts whenever it enters an accepting state.
• We assume the tape symbols are X₁, X₂, . . . , X_s for some s. We assume X₁ is 0, X₂ is 1, and X₃ is the blank.
• We assign integers D₁ and D₂ to the tape head directions left and right.
• Now we can encode a transition rule δ(q_i, X_j) = (q_k, X_l, D_m) as a binary string C of the form
0ⁱ10^j10^k 10^l10^m
• Suppose there are n transition rules. The binary code for the entire Turing machine will be the concatenation of the codes for all of the transitions (in some order) separated by pairs of 1's:
C₁11C₂11 … C_n-111C_n
• Note that there can be many encodings for the same Turing machine.
• We can encode a pair (M_i, w) consisting of a Turing machine and a string by appending 111 to the encoding of the Turing machine and then appending the string w.

4. The Diagonalization Language L_d is not Recursively Enumerable

• We define L_d, the diagonalization language, as follows:
1. Let w₁, w₂, w₃, . . . be an enumeration of all binary strings.
2. Let M₁, M₂, M₃, . . . be an enumeration of all Turing machines.
3. Let L_d = { w_i | w_i is not in L(M_i) }.
• Theorem: L_d is not a recursively enumerable language.
  Proof:
• Suppose L_d = L(M_i) for some TM M_i.
• This gives rise to a contradiction. Consider what M_i will do on an input string w_i.
• If M_i accepts w_i, then by definition w_i cannot be in L_d.
• If M_i does not accepts w_i, then by definition w_i is in L_d.
• Since w_i can neither be in L_d nor not be in L_d, we must conclude there is no Turing machine that can define L_d.

5. Complements of Recursive and Recursively Enumerable Languages

• A recursive language is one that is accepted by a TM that halts on all inputs.
• The complement of a recursive language is recursive.
• If a language L and its complement are RE, then L is recursive.
• A language can be RE but its complement need not be RE.

6. Practice Problems

1. Prove that if there is a reduction from problem P₁ to problem P₂ and if P₁ is not recursive, then P₂ is not recursive.
2. Prove that if there is a reduction from P₁ to P₂ and if P₁ is not recursively enumerable, then P₂ is not recursively enumerable.
3. Show that the language L = { w_i | w_i is not accepted by M_2i } is not recursively enumerable.
4. Show that the language L = { w_i | w_2i is not accepted by M_i } is not recursively enumerable.

7. Reading

• HMU: Sections 8.1.3, 9.1, 9.2.1, 9.2.2, 9.3.1