I'm taking one of my last graduate classes but have been struggling with some reductions in lambda calculus. On our last assignment one of the problems was the following:
This question is on defining the predecessor function $pred$ on the Church numerals.
Let $G = \lambda xgh.(h (g x))$.
Recall that the combinators:
$$\begin{align}K &= \lambda xy.x\\
I &= \lambda x.x\end{align}$$
(a) Reduce $(G f)(K x)$ to its
$\beta$-normal form.
(b) Reduce $(G f)((G f)(K x))$ to its
$\beta$-normal form.
(c) $pred$ is defined as:
$\lambda nfx.(n (G f) (K x) I)$
Show that $$pred\ 3 \stackrel{\alpha\beta}= 2.$$
I really just want to make sure I'm heading in the right direction for (a).
Edit updated work with proper syntax
$(G f) = (\lambda xgh.(h (g x))) f$
$= \lambda gh.(h(gf))$
$(K x) = (\lambda xy.x) x$
$= \lambda y.z$ <-$(\alpha sub)$
$(G f)(K x) = (\lambda gh.(h(g f))) \lambda y.z$
$= \lambda h.(h((\lambda y.z) f))$
edit can the above be simplified to this?
$= \lambda h.(h (z))$
Best Answer
Go through it again. I caught at least one mistake:
You wrote $G f = \lambda x g h. (h (g x)) f$, which is incorrect. You are missing parentheses. It should be: $G f = (\lambda x g h. (h (g x))) f$, which then reduces to $\lambda g h. (h (g f)))$.
It might help if you didn't put the frivolous parentheses around each of the variables. The syntax is not
λ(x). <stuff>. It should be written "λx. <stuff>".Also, by convention, you can group together multiple binders. Instead of $λx. λg. λh. h(gx)$, write it as $λxgh.h(gx)$. The more dots and parentheses in your expression, the more likely you'll screw up a tedious calculation.