November 5 * Closure Properties of TM * Recursive languages are closed under complement Proof. Let L recursive be defined by M (always halts). _ _ Consider M that always halts and accepts L: _ M +--------------------------+ | | | "yes" | | +-+---------+\ /+---------> "yes" w ------->|M| "no" X | | +-+---------+/ \+---------> "no" | | | | +--------------------------+ * False Theorem. Recursively enumerable languages are closed under complement. Proof. Same as previous machine. This fails because M only needs to halt if w in L(M) - doesn't have to say "no". +-----> yes if w in L(M) / +-+/ w-->|M| +-+ * Recursive languages are closed under union and intersection. Proof. Let L1, L2 be recursive, decided by M1, M2. Then M_{1 v 2} accepts L1 v L2. +----------------------------------------+ | "yes" +------------------->+--+ | | / |OR|------------> "yes" | +-+/ +--->+--+ | w---->|M| | | | +-+\ "yes"| | | \ start +--+---+ | | +------->|M2| "no" | | +--+------------------------> "no" | | +----------------------------------------+ Intersection follows from DeMorgan's Law or from suitable picture. For recursively enumerable languages, M_{1v2} fails to prove closure under union. M1 may not halt, and so M2 may not be run by M_{1v2} on w. However, consider +-------------------------------------------+ | | | +--+ "yes" | | +->|M1|------+ | | / +--+ \ | | / ------>+--+ | w----- |OR|--------------------> "yes" | \ ------>+--+ | | \ +--+ "yes" / | | +->|M2|------+ | | +--+ | | | +-------------------------------------------+ This machine runs M1(w), M2(w) in parallel (alternate 1 step each), and accepts as soon as either of them accepts. This proves Recursively enumerable languages are closed under union. A similar picture proves Recursively enumerable languages are closed under intersection. _ * L recursive <=> L and L are both recursively enumerable. => L recursive => L recursively enumerable by definition _ _ L recursive => L recursive (closure) => L recursively enumerable <= Consider +------------------+ | +---> "yes" | +--+ "yes" /| | +->|M1|------+ | | / +--+ | | / | w----- | | \ +---> "no" | \ +--+ "yes" /| | +->|M2|------+ | | | +--+ | | | +------------------+ Since L, L complement are recursively enumerable, there exist M_L, M_{L complement} accepting them (these machines need not halt when rejecting). Forall w, either w in L or w in L complement, so at least one of M_L, M_{L complement} accepts w. Thus M' always halts and decides whether w in L correctly; thus L is recursive. Note that this theorem implies L complement not recursively enumerable => L not recursive Note also that if we exhibit a recursively enumerable L such that L is not recursive, this shows that L complement is not recursively enumerable, and thus recursively enumerable languages are not closed under complementation.