Lambda Identity

Computer Science Level 1

Which of the folowing expressions can be simplified to

( λ x . x ) x ? (\lambda x.x)x?

Do you know what λ \lambda calculus is?

( λ y 1 . y 1 ) ( λ x . ( x x ) ) ( \lambda y_1 . y_1 ) \big( \lambda x . (x x) \big) λ y 1 . ( λ x . ( x x ) ) \lambda y_1 . \big(\lambda x . (x x)\big) λ z . ( λ y . ( z ( + y z ) ) ) \lambda z . \Big( \lambda y . \big( z (+ y z) \big) \Big) ( λ y 1 . y 1 ) x (\lambda y_1 . y_1) x

Precision Graph by Precision Graph , 20, Singapore

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Relevant wiki: Lambda Calculus

We can transform the expression in the answer to that in the question using an α \alpha reduction

( λ y 1 . y 1 ) x ⟶ α ( λ x . x ) x (\lambda y_1 . y_1) x \mathrel{\mathop{\longrightarrow}^{\mathrm{\alpha}}} (\lambda x . x) x

Informally, this means that since y 1 y_1 is a place holder, it can be replaced with anything. This is equivalent to the following in haskell 

1
 
(\ x -> x) x

12 Helpful 1 Interesting 0 Brilliant 2 Confused
Haohan Zeng
Sep 16, 2018

smallest programming language

0 Helpful 0 Interesting 1 Brilliant 0 Confused

why this shit says im incorrect when my solutions is the same as its pointed out? Does this website work properly??

asdasd dsad - 1 year, 11 months ago

Think of the bound variable as a dummy variable as in calculus.

0 Helpful 0 Interesting 0 Brilliant 0 Confused

Some kind of algebra.

0 Helpful 0 Interesting 0 Brilliant 2 Confused

basically magic

Mitchell Pon - 2 years, 2 months ago

It's actually a type of calculus, not a type of algebra.

Daniel Tinsley - 9 months, 2 weeks ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...