4

For a Uni project I try to build complex lambda expressions with combinators that use only two (bound) variables.

For example I managed to create IF-THEN-ELSE $(λp.λa.λb.p a b)$ by using three combinators:

$(λx.λy. x y) (λx.λy. x y)$

Now I try the same approach for the SUCCESSOR expression $(λn.λf.λx.f ((n f) x))$ but I tried different approaches. But none worked.

Any hints? Is it even possible? How can I show that it's possible or not. Of course if I have an example that works it is possible. But how could I show that it's not possible?

woodtluk
  • 143
  • I didn't manage to find a solution. And I'm quite sure it's not possible. But I have no proove. – woodtluk Jun 13 '16 at 11:40
  • What exactly are you trying to do? Your question doesn't make sense. You example for 2 bound variables clearly has 4 bound variables, and though you say it has 3 combinators, it clearly has zero combinators. – DanielV Jun 15 '16 at 06:29

0 Answers0