Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [lambda-calculus]

For questions on the formal system in mathematical logic for expressing computation using abstract notions of functions and combining them through binding and substitution.

Lambda calculus (also written as λ-calculus) is a formal system in mathematical and theoretical for expressing computation based on function abstraction and application using variable binding and substitution. Its namesake, the Greek letter lambda (λ), is used in lambda expressions and lambda terms to denote binding a variable in a function.

It was first introduced by mathematician Alonzo Church in the 1930s as part of his research of the of mathematics. The original system was shown to be logically inconsistent because of the Kleene–Rosser paradox. Subsequently, in 1936 Church isolated and published just the portion relevant to computation, what is now called the untyped lambda calculus.

Untyped lambda calculus is Turing complete, that is, it is a universal model of computation that can be used to simulate any (see ). It may be used to model booleans, arithmetic, data structures and recursion.

Lambda calculus may be untyped or typed. In typed lambda calculus (see ), functions can be applied only if they are capable of accepting the given input's "type" of data. Typed lambda calculi are weaker than the untyped lambda calculus, in the sense that typed lambda calculi can express less than the untyped calculus can, but on the other hand typed lambda calculi allow more things to be proved; in the simply typed lambda calculus it is for example a theorem that every evaluation strategy terminates for every simply typed lambda-term, whereas evaluation of untyped lambda-terms need not terminate. One reason there are many different typed lambda calculi has been the desire to do more (of what the untyped calculus can do) without giving up on being able to prove strong theorems about the calculus.

Typed lambda calculi are closely related to mathematical and via the Curry–Howard isomorphism: types correspond to logic formulas, lambda-terms correspond to derivations in a logic system (depending on the kind of typed lambda calculus) and computation steps in the lambda calculus correspond to normalization (i.e. cut-elimination) steps for derivations.

Lambda calculus has applications in many different areas in mathematics, philosophy, linguistics, and computer science. Lambda calculus has played an important role in the development of the theory of languages, since functional programming languages implement the lambda calculus. Lambda calculus also is a current research topic in .

655 questions
1
vote
2 answers

Using Combinators in Lambda Calculus

K $\equiv$ $\lambda$xy.x S $\equiv$ $\lambda$xyz.((xz)(yz)) Prove that the identify function I $\equiv$ $\lambda$x.x is equivalent to ((S K) K) I have no clue where to even start for this problem, could someone possibly guide me into solving this…
petrov
  • 335
  • 2
  • 5
  • 12
1
vote
1 answer

Beta reduction exercise question

I am trying to reduce the following $\lambda$-expression: $$(\lambda x.x x) (\lambda y.y x) z$$ So I am reducing to $$(\lambda y.y x) (\lambda y.y x) z$$ That reduces to $$(\lambda y.y x)xz$$ Now comes trouble. According to the solution given here…
Vitaly Olegovitch
  • 586
1
vote
1 answer

Prove that $[x/x] M \equiv M$

I just started reading the book Lambda-Calculus and Combinators An Introduction. Using this definition of Substitution in Page 7. I want to prove that if $M$ is any term $[x/x] M \equiv M$. In the book it is given that proof follows by checking…
Ramana Venkata
  • 2,076
1
vote
1 answer

Lambda Calculus: Reduction to Normal Form

I'm working on some problems where I'm supposed to reduce lamda terms to normal form. I'm not sure if I'm doing it right so if someone could let me know, that would be awesome. $$(\lambda x.\lambda y.x*2+y*3)\; 5 \;4 $$ $$\rightarrow(\lambda…
user2869231
  • 135
1
vote
1 answer

$\alpha$-equivalence and the substititution operation over equivalence classes

This post is divided in two parts, viz. Definitions and Question. Definitons The following definitions are adapted from Lecture notes on the Curry-Howard Isomorphism (by Sorensen and Urzyczyn), pp. 2-5. Definition. (Pre-terms) Let $V$ be an…
Alistair -L.
  • 163
  • 4
1
vote
1 answer

Does the opposite direction of alpha congruence in applications hold?

The forward direction is: if $s \equiv_\alpha s' \land t \equiv_\alpha t'$, then $st \equiv_\alpha s't'$. I'm wondering if this holds: if $st \equiv_\alpha s' t'$ then $s \equiv_\alpha s' \land t \equiv_\alpha t'$. I was trying to come up with a…
Kleon
  • 11
  • 2
1
vote
1 answer

How do interpret $x \lambda y . \lambda z . x$?

I am not sure how to interpret this term. My first thought is that it is this an application of $x$ to $\lambda y.\lambda z.x$ Is that the correct interpretation or is it not reducible?
mcmapple
  • 121
1
vote
0 answers

Lambda calculus: "succ expressions" are all polynomial functions on Church numerals?

The specific definition of $\mathsf{succ}$ for Church numerals $$ \mathsf{succ} = \lambda n f x. f (n f x) $$ seems to have an interesting property when applied to itself: (here, all expressions on $n$ mean the Church numeral that represents the…
Bubbler
  • 291
1
vote
0 answers

Encode λ-terms in λ-calculus

One may represent λ-terms in the λ-calculus using the following data type: data LTerm a = Var a | App (LTerm a) (LTerm a) | Abs a (LTerm a) Describe the encoding of the constructors, the fold, the map and the case for this datatype. The way I…
Zhijie Xia
  • 11
1
vote
1 answer

How is KMI an application and not abstraction with MI in body in lambda calculus?

Let $K = \lambda zy.z$ (kestrel), $M = \lambda f.ff$ (mockingbird), $I = \lambda x.x$ (identity). Now I believe $M$, I should be subsumed inside $K$'s function body but my lecture notes say that $K M I = M$. Can anyone explain how? Another example…
learner
  • 31
  • 4
1
vote
0 answers

Prove that exponent is primitive recursive

I'm trying to answer the following: Show that $f(x,y)=x^y$ is primitive recursive. Here's my try: We can derive exponent thus: $ f(x,0)=1, \ \ f(x,1)=f(x,0) \times x, \ \ f(x,2)=f(x,1) \times x, \ ... \ \ f(x,n+1)=f(x,n) \times x $ Then we can…
Logan Lee
  • 249
1
vote
0 answers

Deriving suc iszero pre functions from alternative definition of natural number

Here I am given an alternative definition for natural numbers. Like this $$ LET \ \widehat{\underline{0}} = \lambda x. x $$ $$ LET \ \widehat{\underline{1}} = (\underline{false}, \ \widehat{\underline{0}}) $$ $$ LET \ \widehat{\underline{2}} =…
Logan Lee
  • 249
1
vote
0 answers

Evaluating conditional expression

I want to show that $$ (\lambda fgx. fx(gx)) (\lambda xy. x) (\lambda xy.x) = \lambda x. x $$ Here's my try: $$ (\lambda fgx. fx(gx)) (\lambda xy. x) (\lambda xy.x) = (\lambda fgx. fx(gx)) \underline{true} \ \underline{true} = \lambda x.…
Logan Lee
  • 249
1
vote
0 answers

Evaluating iszero function

$\underline{iszero}$ function is defined as $$ \underline{iszero} = \lambda n. n(\lambda x. \underline{false})\underline{true} $$ I want to show that $\underline{iszero} \ \underline{5} = \underline{false}$. Here's my try: $$ \underline{iszero} \…
Logan Lee
  • 249
1
vote
1 answer

Lambda calculus reductions

I encountered an example in lambda calculus: $$(\lambda x.(\lambda y.(xy))x)(\lambda z.w)$$ Now, can I apply the second parenthesis to $\lambda x$? Then $$(\lambda x.(\lambda y.(xy))x)(\lambda z.w) \rightarrow^{\beta} (\lambda y.(xy))(\lambda z.w)$$…
Awerde
  • 299
1 2 3
…
15 16