\documentstyle[12pt,twoside]{article}

\input{macros-course}

\begin{document}

\tutprobn{1}{2/5/99}{February 5, 1999}

\begin{problems}

\problem Scheme, and many other programming languages, allows procedures to
take themselves as arguments.  For example, in Scheme we can define
a \texttt{perverse} procedure:
\begin{verbatim}
    (define (perverse f)
       (if   (and (number? (f f)) (zero? (f f)))   1   0)))
\end{verbatim}
Then evaluating
\begin{verbatim}
    (perverse (lambda (proc) 0))
\end{verbatim}
returns 1, while evaluatng
\begin{verbatim}
    (perverse (lambda (proc) proc))
\end{verbatim}
returns 0.
\bparts

\ppart What happens when Scheme evaluates \texttt{(perverse +)}?

\ppart What happens when Scheme evaluates \texttt{(perverse perverse)}?

\ppart Now let's get away from Scheme procedures --- which are
mathematically a little murky --- and define a real \emph{mathematical}
function, $p$, which can be applied to any function of one variable.  The
function $p$ is defined as follows:
\[p(f) = \left\{\begin{array}{ll}
               1 & \mbox{if $f(f)$ is defined and it equals 0,}\\
               0 &  \mbox{otherwise.}
               \end{array} \right. \]

Now by this definition, $p(f)$ is defined to be either 1 or 0 for all
functions $f$.  Also, whenever $f(f)$ happens to be defined,
\[p(f) \neq f(f).\]

In particular, we can choose $f$ to be $p$, and reach the nonsensical
conclusion that 
\[p(p) \mbox{ is defined and } p(p) \neq p(p)!\]

Carefully explain where this argument goes wrong.
\eparts

\problem You are given 12 identical looking balls, and told that one of
them is of different weight from the other 11, but you don't know in
advance whether it is heavier or lighter.  Can you find the ball that is of
different weight using only 3 weighings on a balance scale?

\end{problems}

\end{document}

