MA/CSSE 474 Theory of Computation D, SD, and non-SD languages Enumerability Reduction Decidable and Semidecidable Languages Recap: Dovetailing Dovetailing: Run an infinite number of computations "in parallel". S[i, j] represents step j of computation i.

S[1, 1] S[2, 1] S[1, 2] S[3, 1] S[2, 2] S[1, 3] S[4, 1] S[3, 2] S[2, 3] S[1, 4 ] ... For every i and j, step S[i, j] will eventually happen. Recap: The Language H Theorem: The language: H = { : TM M halts on input string w} is

semidecidable, but is not decidable. We proved this last time. Questions about the proof? If H were in D, then SD would equal D Recall: H = { : TM M halts on input string w} We know that HSD. If H were also in D, then there would exist a TM O that decides it. (O is for Oracle) Theorem: If H were in D then every SD language would be in D. Proof: Let L be any SD language. There exists a TM ML that semidecides it. The following machine M' decides whether w is in

L(ML): M'(w: string) = 1. Run O on . (O will always halt) 2. If O accepts (i.e., ML will halt on input w), then: 2.1. Run ML on w. 2.2. If it accepts, accept. 2.3 Else reject. 3. Else reject. Every CF Language is in D

Theorem: The set of context-free languages is a proper subset of D. Proof: Every context-free language is decidable, so the contextfree languages are a subset of D. There is at least one language, AnBnCn, that is decidable but not context-free. So the context-free languages are a proper subset of D. Decidable and Semidecidable Languages Almost every obvious language that is in SD is also in D: AnBnCn = {anbncn, n 0} {wcw, w {a, b}*}}

{ww, w {a, b}*}} {xy=z: x,y,z {0, 1}*} and, when x, y, and z are viewed as binary numbers, xy = z} But there are languages that are in SD but not in D: H = { : M halts on input w}

D and SD 1. 2. 3. D is a subset of SD. In other words, every decidable language is also semidecidable. There exists at least one language that is in SD-D, the donut in the picture. What about languages that are not in SD? Is the gray area of the figure empty?

Subset Relationships between D and SD 1. There exists at least one SD language that is not D. 2. Every language that is in D is also in SD: If L is in D, then there is a Turing machine M that decides it (by definition). But M also semidecides it. Languages That Are Not in SD Theorem: There are languages that are not in SD.

Proof: Assume any nonempty alphabet . Lemma: There is a countably infinite number of SD languages over . Lemma: There is an uncountably infinite number of languages over . So there are more languages than there are languages in SD. Thus there must exist at least one language that is in SD. Closure of D Under Complement Theorem: The set D is closed under complement. Proof: (by construction) If L is in D, then there is a deterministic Turing machine M that decides it.

M: y n From M, we construct M to decide L: Closure of D Under Complement Theorem: The set D is closed under complement. Proof: (by construction) M:

M': y n n This works because, by definition, M is: deterministic complete

Since M' decides L, L is in D. y SD is Not Closed Under Complement Can we use the same technique? M: M': y

SD is Not Closed Under Complement Suppose we had: ML: ML: Accepts if input is in L. Accepts if input not in L. Then we could decide L. How? So every language in SD would also be in D. But we know that there is at least one language (H) that is in SD but not in D. Contradiction.

D and SD Languages Theorem: A language is in D iff both it and its complement are in SD. Proof: L in D implies L and L are in SD: L is in SD because D SD. D is closed under complement So L is also in D and thus in SD. L and L are in SD implies L is in D: M1 semidecides L. M2 semidecides L.

To decide L: Run M1 and M2 in parallel on w. Exactly one of them will eventually accept. A Particular Language that is Not in SD Theorem: The language H = { : TM M does not halt on input string w} is not in SD. Proof: H is in SD. If H were also in SD then H would be in D. But H is not in D. So H is not in SD.

Note that this is our "special" definition of complement for languages that involve TM descriptions. Enumeration Enumerate means "list, in such a way that for any element, it appears in the list within a finite amount of time." We say that Turing machine M enumerates the language L iff, for some fixed state p of M: L = {w : (s, ) |-M*} (p, w)}. "p" stands for "print" A language is Turing-enumerable iff there is a Turing

machine that enumerates it. Another term that is often used is recursively enumerable. A Printing Subroutine Let P be a Turing machine that enters state p and then halts: Examples of Enumeration What languages do M1 and M2 enumerate?

SD and Turing Enumerable Theorem: A language is SD iff it is Turing-enumerable. Proof that Turing-enumerable implies SD: Let M be the Turing machine that enumerates L. We convert M to a machine M' that semidecides L: 1. Save input w on another tape. 2. Begin enumerating L. Each time an element of L is enumerated, compare it to w. If they match, accept. The Other Way Proof that SD implies Turing-enumerable: If L *} is in SD, then there is a Turing machine M that semidecides L.

A procedure E to enumerate all elements of L: 1. Enumerate all w *} lexicographically. e.g., , a, b, aa, ab, ba, bb, 2. As each is enumerated, use M to check it. w3, w2, w1 L? E M M'

Problem? yes w The Other Way Proof that SD implies Turing-enumerable: If L *} is in SD, then there is a Turing machine M that semidecides L. A procedure to enumerate all elements of L: 1. Enumerate all w *} lexicographically.

2. As each string wi is enumerated: 1. Start up a copy of M with wi as its input. 2. Execute one step of each Mi initiated so far, excluding those that have previously halted. 3. Whenever an Mi accepts, output wi. Lexicographic Enumeration M lexicographically enumerates L iff M enumerates the elements of L in lexicographic order. A language L is lexicographically Turing-enumerable iff there is a Turing machine that lexicographically enumerates it.

Example: AnBnCn = {anbncn : n 0} Lexicographic enumeration: Lexicographically Enumerable = D Theorem: A language is in D iff it is lexicographically Turingenumerable. Proof that D implies lexicographically TE: Let M be a Turing machine that decides L. M' lexicographically generates the strings in *} and tests each using M. It outputs those that are accepted by M. Thus M' lexicographically enumerates L. Proof, Continued Proof that lexicographically Turing Enumerable implies D:

Let M be a Turing machine that lexicographically enumerates L. Then, on input w, M' starts up M and waits until: M generates w (so M' accepts), M generates a string that comes after w (so M' rejects), or M halts (so M' rejects). Thus M' decides L. Language Summary IN SD OUT Semideciding TM

H Reduction Enumerable Unrestricted grammar D Deciding TM AnBnCn Diagonalize Lexic. enum Reduction L and L in SD CF grammar

PDA Closure Context-Free AnBn Pumping Closure Regular Regular Expression FSM

a*}b*} Closure Pumping OVERVIEW OF REDUCTION Reducing Decision Problem P1 to another Decision Problem P2 We say that P1 is reducible to P2 (written P1 P2) if there is a Turing-computable function f that finds, for an arbitrary instance I of P1, an instance f(I) of

P2, and f is defined such that for every instance I of P1, I is a yes-instance of P1 if and only if f(I) is a yes-instance of P2. So P1 P2 means "if we have a TM that decides P2, then there is a TM that decides P1. Example of Turing Reducibility Let P1(n) = "Is the decimal integer n divisible by 4?" P2(n) = "Is the decimal integer n divisible by 2?" f(n) = n/2 (integer division, which is clearly

Turing computable) Then P1(n) is "yes" iff P2(n) is "yes" and P2(f(n)) is "yes" . Thus P1 is reducible to P2, and we write P1 P2. P2 is clearly decidable (is the last digit an element of {0, 2, 4, 6, 8} ?), so P1 is decidable Reducing Language L1 to L2 Language L1 (over alphabet 1) is reducible to language L2 (over alphabet 2) and we write L1 L2 if there is a Turing-computable function

f : 1*} 2*} such that x 1*}, x L1 if and only if f(x) L2 Using reducibility If P1 is reducible to P2, then If P2 is decidable, so is P1. If P1 is not decidable, neither is P2. The second part is the one that we will use most. Example of Reduction Computing

a function (where x and y are unary representations of integers) multiply(x, y) = 1. answer := . 2. For i := 1 to |y| do: answer = concat (answer, x) . 3. Return answer. So we reduce multiplication to addition. (concatenation) Reduction example: Nim

At each turn, a player chooses one pile and removes some sticks from it. The player who takes the last stick wins. Problem: Is there a move that guarantees a win for the current player? Nim Obvious approach: search the space of possible moves. Reduction to an XOR computation problem:

100 101 010 011 1 1 0 10 01 11

XOR them together: 0+ means state is losing for current player otherwise current player can win by making a move that makes the XOR 0. Using Reduction for Undecidability Theorem: There exists no general procedure to solve the following problem: Given an angle A, divide A into sixths using only a straightedge and a compass. Proof: Suppose that there were such a procedure, which well call

sixth. Then we could trisect an arbitrary angle: trisect(a: angle) = 1. Divide a into six equal parts by invoking sixth(a). 2. Ignore every other line, thus dividing a into thirds. trisect(a) sixth(a) ignore lines sixth exists trisect exists. But we know that trisect does not exist. So:

http://en.wikipedia.org/wiki/Angle_trisection Using Reduction for Undecidability A reduction R from language L1 to language L2 is one or more Turing machines such that: If there exists a Turing machine Oracle that decides (or semidecides) L2, then the TMs in R can be composed with Oracle to build a deciding (or semideciding) TM for L1. P P means that P is reducible to P. Using Reduction for Undecidability

(R is a reduction from L1 to L2) (L2 is in D) (L1 is in D) If (L1 is in D) is false, then at least one of the two antecedents of that implication must be false. So: If (R is a reduction from L1 to L2) is true and (L1 is in D) is false, then (L2 is in D) must be false. Application: If L1 is a language that is known to not be in D, and we can find a reduction from L1 to L2, then L2 is also not in D.

Using Reduction for Undecidability Showing that L2 is not in D: L1 (known not to be in D) L1 in D But L1 not in D R L2

(a new language whose if L2 in D decidability we are trying to determine) So L2 not in D To Use Reduction for Undecidability 1. Choose a language L1: that is already known not to be in D, and show that L1 can be reduced to L2. 2. Define the reduction R.

3. Describe the composition C of R with Oracle. 4. Show that C does correctly decide L1 iff Oracle exists. We do this by showing: R can be implemented by Turing machines, Follow this outline in C is correct: If x L1, then C(x) accepts, and proofs that you submit.. We will see If x L1, then C(x) rejects. Example: H = { : TM M halts on } many examples in the

next few sessions. Mapping Reductions L1 is mapping reducible to L2 (L1 M L2) iff there exists some computable function f such that: x*} (x L1 f(x) L2). To decide whether x is in L1, we transform it, using f, into a new object and ask whether that object is in L2. Example: DecideNIM(x) = XOR-solve(transform(x))