The Lambda Calculus
The lambda calculus is a tool used by computer scientists and mathematicians to examine certain types of functions, recursion, and other fun things. It was developed in the 1930s by the Princeton logician Alonzo Church to work on undecidability.* He and Turing later proved that the lambda calculus is computationally equivalent to a Turing machine, which is pretty neat.
Most functional programming languages (Haskell, for example, and of course my beloved Lisp**) were heavily influenced by the lambda calculus, but ideas from it have crept into other languages (like Python) as well. So languages that use lambda expressions (which allow one to define an unnamed function on the fly) ultimately got the idea from Church.
* “There is no algorithm which takes as input two lambda expressions and outputs TRUE or FALSE depending on whether or not the two expressions are equivalent. This was historically the first problem for which undecidability could be proven. As is common for a proof of undecidability, the proof shows that no computable function can decide the equivalence. Church’s thesis is then invoked to show that no algorithm can do so.” — Wikipedia
** Lisp, it should be noted, is vigorously defended by its possibly-fictional protectors, the Knights of the Lambda Calculus. They’ve got an awesome coat of arms.
This entry was posted on Sunday, December 21st, 2008 at 11:00 pm and is filed under computer science, math. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.
Leave a Reply