Lambda Calculus Homework.
			
			     Due Monday 9/15


No more than two people can collaborate on this assignment.  Show work.


0. Identify the free and bound variables in the following term:

   lambda u. lambda x. x (lambda y.x u) y u


1. Determine if the following pairs of terms are alpha-equivalent.

   a.  lambda x.lambda y. (x y x)  and
       lambda x.lambda y. (y x y)

   b.  lambda x. lambda y. x (lambda y.x) y   and 
       lambda a. lambda b. a (lambda u.a) b


For the rest of the problems, find the beta-normal forms of the
following terms.  Remember: you can rename bound variables to
avoid clash, but never free variables.

2. (lambda x.lambda y. (x y)) (lambda x.x) u

3. given S, K, I as they are in the handout, find the normal forms
   of KIK and SIK

4. given A = lambda m.lambda n.lambda f.lambda x. m f (n f x),
         T = lambda f.lambda x.f (f x)

   find the normal form of (A T T).
   Conjecture what would happen if T = lambda f.lambda x.f (f (f x)).


5. Given T = lambda x. lambda y. x
         F = lambda x. lambda y. y
         A = lambda p.lambda q. (p q F)   (where F is as above)
    
   Find the normal forms of:
      
      a. (A F F)
      b. (A F T)
      c. (A T F)
      d. (A T T)

Does anything about the behavior of these lambda terms look familiar? 

(pretend you're all excited now and want to know more!)


6. Let T and F be as they were in the above problem, and let
   N = lambda x. (x F T)

   what are the normal forms of 

      a. (N F)
      b. (N T)
      c. (N (N F))

 ( he he he ... )