I've been reading "The Emperor's New Mind" by Roger Penrose. He briefly introduces lambda calculus (pp. 86-92) and gives this formula for addition:

$A = \lambda fgxy.[((fx)(gx))y]$

This was my attempt at using it:

$$ A = \lambda fgxy.[((fx)(gx))y] \\ 1 = \lambda an.an \\ 2 = \lambda bm.b(bm) \\ A12 = \lambda xy.( ( ((\lambda an.an)x) ((\lambda bm.b(bm))x) ) y) \\ = \lambda xy.[ ( ((\lambda an.an)x) (\lambda m.x(xm)) ) y] \\ = \lambda xy.[ ( (\lambda n.xn) (\lambda m.x(xm)) ) y] \\ = \lambda xy.[ ( x((\lambda m.x(xm))) ) y] \\ = \lambda xy.[ ( x(\lambda m.x(xm)) ) y] \\ $$

Is it legal to transform the last step into $= \lambda xy.[x(x(x(y)))]$? I guess it might be (by some informal reasoning), but this seems to go beyond the scope of what Penrose gave an introduction of. Alternative definitions (for example here, slides 27 and 28) don't seem to be problematic.



$A=\lambda fgxy.[((fx)(gx))y]$ must be a typo in the book. (It's in my copy too).

The definition that actually works is $A=\lambda fgxy.[(fx)((gx)y)]$.

Usually this would be written as just $\lambda fgxy.fx(gxy)$, but it seems like Penrose doesn't bother to explain the usual rules for omitting parentheses (basically that $MNK$ means $(MN)K$), and instead writes everything fully parenthesized.

  • $\begingroup$ Thanks! Btw, does f(lambda x.gx) have any meaning? Is that the same as fg? $\endgroup$ – Luka Mikec Dec 26 '13 at 0:34
  • 2
    $\begingroup$ @LukaMikec: $f(\lambda x.gx)$ and $fx$ "behave the same", in a sense that can be made technically precise. In general $(\lambda x.Mx)$ "behaves the same" as $M$ whenever $x$ does not appear free in $M$ -- this is known as the eta-conversion rule (which Penrose doesn't seem to describe). $\endgroup$ – hmakholm left over Monica Dec 26 '13 at 0:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.