Lambda Calculus

Note: You may use the backslash character for writing lambda instead of using the whole word.

Problem 1 [2.5 + 2.5 + 2.5 + 2.5 Points]. What are the types of the following functions? [Use Z for a value of unknowable type, and -> to show a function from one type to another (e.g., Z -> Z)]

a) lambda x . x*2

b) lambda x . lambda y . x (x y)

c) lambda x . lambda y . lambda z . (z x) y

d) lambda x . lambda y . lambda z . (z x) y 3

Problem 2 [5 + 5 Points]. Beta reduce the following lambda expressions, if possible:

a) (lambda x . lambda y. (x y) (y w))

b) (lambda x . (x x) lambda x . (x x))