2

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))$

MJD
  • 65,394
  • 39
  • 298
  • 580
dfasdfsda
  • 35
  • 1
  • 6

1 Answers1

1

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.

Kolmin
  • 4,083
Tac-Tics
  • 2,203
  • Thanks for replying, I prefer writing in the manner you described just wasn't sure if I was missing something. My Prof. for his own preferences writes it out like I did in my post. I updated my initial post to reflect proper syntax. I still came to a similar result, does that appear to be beta-normal form? edit I did one more beta-redex but not sure if it's legal – dfasdfsda Oct 03 '13 at 21:12
  • 2
    Just briefly looking over your edit, you have a line: (Kx)=(λxy.x)x =λy.z <-(αsub). That is an illegal use of α-conversion. There's also no need to α-convert at all. Try it using the more correct expansion: K x = (λxy.x)x = λy.x. Note that x is a free variable now. – Tac-Tics Oct 04 '13 at 15:53
  • Also, mind your parentheses! (λgh.(h(gf)))λy.z will cause you trauma later on. Try (λgh.(h(gf)))(λy.z) instead (with the parens around the argument. – Tac-Tics Oct 04 '13 at 15:54