Admin: I'll return the midterm today! Raw marks are written on the exam, curved marks are posted to Canvas. Formula (strong curve!): Curved = 100 * (Raw/59)^0.35 Lecture: Today we continue with Chapter 5. Suppose A and B are languages. We will define what we mean by "computable functions" (from strings to strings). Given two languages A and B, we can define what is a "many-one" or "mapping" reduction from A to B (see book/slides). We write "A <=_m B" to assert the existence of such a reduction. Note the subscript "m" (later we have some other subscripts). We claim that such reductions are transitive: If A <=_m B and B <=_m C then A <=_m C. Let co(A) denote "complement of A". Notice that "A <=_m B" and "co(A) <=_m co(B)" are equivalent. Similarly, "co(A) <=_m B" and "A <=_m co(B)" are equivalent. Recall: REC = recognizable DEC = decidable Supposing "A <=_m B" is true. We claim: A is REC if B is REC. A is co-REC if B is co-REC. A is DEC if B is DEC. So essentially, the reduction says "A is no harder than B". Of course we also can turn this around: If A is not REC then B is not REC. If A is not co-REC then B is not co-REC. If A is not DEC then B is not DEC. This is all a bit more precise (about REC and co-REC) than our old arguments which simply said: "If A is DEC then B is DEC." In particular, we pay more attention to complements (negation) now. We'll go back over many of the reductions that we saw earlier in Chapter 5, and try to restate them as mapping reductions. For example, we had these first few reductions: A_TM <=_m HALT_TM HALT_TM <=_m A_TM A_TM <=_m co(E_TM) E_TM <=_m EQ_TM A_TM <=_m co(E_LBA) A_TM <=_m co(ALL_CFG) A_TM <=_m MPCP MPCP <=_m PCP (skipped details, see book) We can also finish some things we left unfinished before: 1. Show that EQ_TM is neither REC nor co-REC How? We already have A_TM <=_m co(EQ_TM) (from above), we need to also show A_TM <=_m EQ_TM (without complement). 2. Show that REGULAR_TM is neither REC nor co-REC. The book shows one reduction (implicitly, which one?), we need to cook up the other.