```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.
```