Editing Lambda calculus (section)

== History ==
Lambda calculus was introduced by mathematician [[Alonzo Church]] in the 1930s as part of an investigation into the [[foundations of mathematics]].<ref>{{cite journal|first1=Alonzo|last1=Church|author1-link=Alonzo Church|title=A set of postulates for the foundation of logic|journal=Annals of Mathematics|series=Series 2|volume=33|issue=2|pages=346–366|year=1932|doi=10.2307/1968337|jstor=1968337}}</ref>{{efn|For a full history, see Cardone and Hindley's "History of Lambda-calculus and Combinatory Logic" (2006).}} The original system was shown to be [[Consistency|logically inconsistent]] in 1935 when [[Stephen Kleene]] and [[J. B. Rosser]] developed the [[Kleene–Rosser paradox]].<ref>{{cite journal|last1=Kleene|first1=Stephen C.|author-link1=Stephen Kleene|last2=Rosser|first2=J. B.|author-link2=J. B. Rosser|title=The Inconsistency of Certain Formal Logics|journal=The Annals of Mathematics|date=July 1935|volume=36|issue=3|pages=630|doi=10.2307/1968646|jstor=1968646}}</ref><ref>{{cite journal|last1=Church|first1=Alonzo|author1-link=Alonzo Church|title=Review of Haskell B. Curry, ''The Inconsistency of Certain Formal Logics''|journal=The Journal of Symbolic Logic|date=December 1942|volume=7|issue=4|pages=170–171|doi=10.2307/2268117|jstor=2268117}}</ref>

Subsequently, in 1936 Church isolated and published just the portion relevant to computation, what is now called the untyped lambda calculus.<ref name="Church1936">{{cite journal|first1=Alonzo|last1=Church|author1-link=Alonzo Church|title=An unsolvable problem of elementary number theory|journal=American Journal of Mathematics|volume=58|number=2|year=1936|pages=345–363|doi=10.2307/2371045|jstor=2371045}}</ref> In 1940, he also introduced a computationally weaker, but logically consistent system, known as the [[simply typed lambda calculus]].<ref>{{cite journal|last1=Church|author1-link=Alonzo Church|first1=Alonzo|year=1940|title=A Formulation of the Simple Theory of Types|journal=Journal of Symbolic Logic|volume=5|issue=2|pages=56–68|doi=10.2307/2266170|jstor=2266170|s2cid=15889861}}</ref>

Until the 1960s when its relation to programming languages was clarified, the lambda calculus was only a formalism. Thanks to [[Richard Montague]] and other linguists' applications in the semantics of natural language, the lambda calculus has begun to enjoy a respectable place in both linguistics<ref name='mm-linguistics'>{{cite book|last1=Partee|first1=B. B. H.|last2=ter Meulen|first2=A.|author2-link=Alice ter Meulen|last3=Wall|first3=R. E.|title=Mathematical Methods in Linguistics |url=https://books.google.com/books?id=qV7TUuaYcUIC&pg=PA317 |access-date=29 Dec 2016|year=1990|publisher=Springer|isbn=9789027722454}}</ref> and computer science.<ref>{{cite web|first1=Jesse|last1=Alama|title=The Lambda Calculus|website=The Stanford Encyclopedia of Philosophy|url=http://plato.stanford.edu/entries/lambda-calculus/|editor1-first=Edward N.|editor1-last=Zalta|edition=Summer 2013|access-date=November 17, 2020}}</ref>

=== Origin of the ''λ'' symbol ===
{{anchor|Origin of the lambda symbol}}
There is some uncertainty over the reason for Church's use of the Greek letter [[lambda]] (λ) as the notation for function-abstraction in the lambda calculus, perhaps in part due to conflicting explanations by Church himself. According to Cardone and Hindley (2006):
<blockquote>
By the way, why did Church choose the notation "λ"? In [an unpublished 1964 letter to Harald Dickson] he stated clearly that it came from the notation "<math>\hat{x}</math>" used for class-abstraction by [[Principia Mathematica|Whitehead and Russell]], by first modifying "<math>\hat{x}</math>" to "<math>\land x</math>" to distinguish function-abstraction from class-abstraction, and then changing "<math>\land</math>" to "λ" for ease of printing.

This origin was also reported in [Rosser, 1984, p.338]. On the other hand, in his later years Church told two enquirers that the choice was more accidental: a symbol was needed and λ just happened to be chosen.
</blockquote>
[[Dana Scott]] has also addressed this question in various public lectures.<ref>Dana Scott, "[https://www.youtube.com/embed/uS9InrmPIoc Looking Backward; Looking Forward]", Invited Talk at the Workshop in honour of Dana Scott's 85th birthday and 50 years of domain theory, 7–8 July, FLoC 2018 (talk 7 July 2018). The relevant passage begins at [https://www.youtube.com/embed/uS9InrmPIoc?start=1970 32:50]. (See also this [https://www.youtube.com/watch?time_continue=1&v=juXwu0Nqc3I extract of a May 2016 talk] at the University of Birmingham, UK.)</ref>
Scott recounts that he once posed a question about the origin of the lambda symbol to Church's former student and son-in-law John W. Addison Jr., who then wrote his father-in-law a postcard:
<blockquote>
Dear Professor Church,

Russell had the [[iota operator]], Hilbert had the [[epsilon operator]]. Why did you choose lambda for your operator?
</blockquote>
According to Scott, Church's entire response consisted of returning the postcard with the following annotation: "[[eeny, meeny, miny, moe]]".