4 ms·
"For example, in [6] the lambda calculus is defined in 86 lines distributed over ten definitions. It seems clear in this compact definition that lambda calculus
by mcguire 12y ago
"For example, in [6] the lambda calculus is defined in 86 lines distributed over ten definitions. It seems clear in this compact definition that lambda calculus does not allow recursive function definitions. Yet already by 1935 at least two versions had been discovered of the Y combinator, an expression of the lambda calculus. And this combinator makes recursive function definitions possible in lambda calculus."
My understanding was that without recursion the lambda calculus is not Turing-complete. Is that correct?
It should also be noted that recursion is a close relative of induction, an indispensable tool that is not without its own problematic history.
- groovy2shoes 12y agoThat is correct, but recursion in the lambda calculus is emergent from the rules, not a rule in itself.
- andreasvc 12y agoMathematical induction is not controversial, it is a formally correct method of proof. You may be thinking of the unrelated concept of empirical induction: generalizing from finite data (black & white swans etc).