CS 319--The Lambda Calculus
Assignment 1, Winter 2000
Due Monday, 24 January

1. Show that application is not associative, i.e., there exist $\alpha$, $\beta$, $\gamma$ such that
   
   $$(\alpha\beta)\gamma\neq_\beta \alpha(\beta\gamma)$$
   
   
   To make the problem slightly more interesting, do it with closed terms.

2. Show that there is no selector function $\sigma$ such that, for all $\alpha$, $\beta$,
   
   $$\sigma(\alpha\beta)=_\beta \alpha$$
   
   

3. Let each symbol be 0.5 cm wide. Construct a lambda term less than 20 cm long, whose normal form is at least $10^{10^{10}}$ light years long. The speed of light is $3\times 10^{10}$ cm/sec. Make the ratio between the length of the normal form of your term, and the length of the term itself, as big as you can. Count $\lambda$, variables, and parentheses, but not the period that we sometimes use to separate a lambda-bound variable from the body of the lambda term.

4. Prove that, if beta-conversion is interpreted with naive substitution, then $\alpha=_\beta \beta$ for all $\alpha$, $\beta$.