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.