Construct · 1 fields · 3 citations

lambda calculus: a standalone construct

One name. One construct. A landmark on the map.

● anchor · a standalone construct Nearest construct by meaningChurch-Turing thesiscompare the meanings
How to read this

Every construct on the map is compared with every other by the meaning of its definitions, and the closest one is surfaced here. The nearest construct to lambda calculus is Church-Turing thesis.

Hold this as a prompt, not a verdict. Two constructs sitting close in meaning is a reason to read them side by side and decide for yourself whether they are one idea under two names. It is not proof that they are. Compare the meanings in the Collider.

lambdacalculus1 CONSTRUCTLambda calculusCHURCH · λ-CALCULUS

A single standalone construct; nearby constructs are located against it in the Collider. Tap a field for its definition, unit, and measures.

Logic and theory of computation

A formal calculus of function abstraction and application

Alonzo Church introduced the lambda calculus in his 1932 paper A set of postulates for the foundation of logic, where the symbol lambda marks a variable being bound to build an anonymous function, and a function is applied to an argument by writing the two side by side. The system has only three kinds of term, a variable, an abstraction that defines a function, and an application that feeds a function its input, together with a single rewrite rule, beta reduction, that substitutes the argument into the body of the function. In his 1936 paper An unsolvable problem of elementary number theory Church used this calculus to exhibit a question that no procedure can decide, the first proof that a well posed mathematical problem can be algorithmically unsolvable. Barendregt's 1984 treatise settled the modern syntax and semantics along with the confluence and normalisation results that organise the field today. The lambda calculus is a landmark because it is provably equal in computing power to the Turing machine, so it serves both as a minimal foundation for defining what is computable and as the direct ancestor of the functional programming languages.[1][2][3]

Unit
A formal rewriting system whose terms are functions built from variables, abstraction, and application
Recovery means
Not applicable
Measured by
Identified by its three term forms and the beta reduction rule; equivalence of two expressions is checked by reducing them to a common normal form where one exists

Next

Run it through the Collider, or take the citations with you.

See how lambda calculus sits against neighbouring constructs in the Collider, or export every reference on this page in one click.

Open in ColliderExport BibTeXReport this entry

Nearby constructs

function5 fields · 6 citationsjingle · one word, five constructsabstraction4 fields · 4 citationsjingle · one word, four constructsrecursion4 fields · 8 citationsjingle · one word, four self-referring constructs

References

  1. Church, A. (1932). A set of postulates for the foundation of logic. Annals of Mathematics, 33(2), 346–366. https://doi.org/10.2307/1968337
  2. Church, A. (1936). An unsolvable problem of elementary number theory. American Journal of Mathematics, 58(2), 345–363. https://doi.org/10.2307/2371045
  3. Barendregt, H. P. (1984). The lambda calculus: Its syntax and semantics (Studies in Logic and the Foundations of Mathematics, Vol. 103). North-Holland.

Cited on this page?

Confirm your construct, or correct us.

If your work is cited behind one of these entries, you know better than we do whether we captured the meaning right. Confirm it, suggest an edit, or dispute it, and your name goes on the entry as an author who has checked it, linked to your ORCID.

Claim your construct