CODEWITHSUNDEEP
lambda-calculus
user2243435
user2243435

Reputation: 11

Beta-Reduction of Lambda Calculus

I know this is probably really simple but I am having problems figuring out how to reduce this. The following is my equation. 

(λx λy . y x) z

I just need an idea of where to start with this because I am totally lost.

Upvotes: 1

Views: 1728

Answers (2)

bookmonkie
bookmonkie

Reputation: 449

Your lambda expression can take two input parameters, but is only given one input, z. Therefore, this leads to a partial application.

In your case, it means that the parameter x is given the value z. Thus all occurrences of x in that expression is replaced with z. However, the parameter y is not given any value as there is not any input left, so the parameter y remains bound.

λy.yz is the correct answer, as fsvieira said.

Upvotes: 0

fsvieira
fsvieira

Reputation: 31

That lambda-expression is not syntacticly correct, I think you meant to write:

(λx.λy.y x) z

Or 

(λxy.y x) z

This is important because a valid lambda-expession is at the form λx.M and not λx M, or using syntactic sugar you can write λxy.M but not λxλy.M and this (λx.λy.y x) is confusing because it seems like an application.

I will reduce both (λx.λy.y x) z and (λx.λy.yx) z

1) (λx.λy.y x) z
2) reduce (λx.λy.y x) by applying x to λx.λy.y, so (λx.λy.y x) z is reduced to λy.y z 3) reduce λy.y z by applying z to λy.y z, the result will be z.

And if you mean (λx.λy.yx) z

1) (λx.λy.yx) z 2) λx.(λy.yx) z 3) Apply z to first abstraction: λy.yz 4) Nothing else to reduce the result is: λy.yz

I recommend you to look at lambda-calculus definition and understand the difference between application, abstraction and variable.

Also in the early stages is better to make use of () and always write lambda-expressions in the extended way, so you will make less mistakes.

Upvotes: 3

Related Questions