\documentclass[12pt]{report}
\topmargin=-0.5in
\oddsidemargin=-0.5in
\textwidth=6.5in
\textheight=9in
\begin{document}
\begin{center}
        {\bf CS 319---The Lambda Calculus}\\
        {\bf Assignment 1, Winter 2000}\\
        Due Monday, 24 January\\
\end{center}
\begin{enumerate}

\item Show that application is not associative, {\it 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.
  
\item Show that there is no selector function $\sigma$ such that, for
  all $\alpha$, $\beta$, $$\sigma(\alpha\beta)=_\beta \alpha$$
 
\item 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.
  
\item Prove that, if beta-conversion is interpreted with naive
  substitution, then $\alpha=_\beta \beta$ for all $\alpha$, $\beta$.

\end{enumerate}
\end{document}
