News for hackers. Stuff that matters.
Re:How recursion got into programming: a comedy of errors by mcguire on Wednesday July 23, 2014 @01:57PM (#8075817)
"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.

Re:How recursion got into programming: a comedy of errors by groovy2shoes on Wednesday July 23, 2014 @02:01PM (#8075853)
That is correct, but recursion in the lambda calculus is emergent from the rules, not a rule in itself.
Re:How recursion got into programming: a comedy of errors by andreasvc on Thursday July 24, 2014 @06:57AM (#8078958)
Mathematical 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).