I tried to implement the lambda calculus successor function on my own, but it's different from the Wikipedia entry on Church encoding. The entry wraps the 'b' around the rest of the expression after injecting the 'c', whereas I tried injecting 'b's application on 'c'. Is there a fundamental difference between these two expressions, and what would be good practice when writing this stuff down?

Mine: increment = (λa.λb.λc.((a b) (b c)))

Wikipedia's: increment = (λa.λb.λc.(b ((a b) c)))

This is after I alpha-reduced to 'a', 'b', and 'c', so the article is different.

  • 3
    $\begingroup$ If I understand it right, your function adds 2, not 1, to the number given. Have you tested it out? $\endgroup$ – user6245072 Aug 18 '16 at 8:04
  • $\begingroup$ Yes, I have tested this out here: people.eecs.berkeley.edu/~gongliang13/lambda NEWLINE They appear to be functionally equivalent after some parenthesis modification and a find-replace. increment = (λa.(λb.(λc.((a b) (b c))))) NEWLINE increment = (λa.(λb.(λc.(b ((a b) c))))) $\endgroup$ – Mr. Minty Fresh Aug 19 '16 at 2:19

Your Answer

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

Browse other questions tagged or ask your own question.