Lambda Calculus Homework 1
			
		            Due 


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 y) u y]

 Remember: whether a term is free or bound is always relative to a given
 term.  What are the free and bound variables for just the term inside the
 []'s ?


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 possible clash, but never free variables.  Also, application
associates to the left: a b c is the same as (a b) c, but not the
same as a (b c).

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

3. given S, K, I as they are in the handout, find the normal forms
   of KII, SIK, SK(KI), and S(KI).  Application associates to the left, 
   and the order is important.

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

   ( T is the "Church representation" of the number 2, and A represents
     Addition - Church originally formulated the lambda calculus as a
     symbolic foundation for all of mathematics.)

4b. (NEW - OPTIONAL CHALLENGE)
   Church exponentiation, m to the nth power, is lambda m.lambda n.(n m).
   Show that 2 to 3rd power = 8 using the Church representation.


5. Given T = lambda x. lambda y. x
         F = lambda x. lambda y. y
         D = lambda p.lambda q. (p T q)   (where T is as above)
    
   Find the normal forms of:
      
      a. (D F F)
      b. (D F T)
      c. (D T F)
      d. (D 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 T))

 ( he he he ... )