Question

Reduce the following lambda-calculus term to the normal form. Show all intermediate steps, with one beta reduction at a time. In the reduction, assume that you are supplied with extra rules that allow you to reduce the multiplication of two natural numbers into the corresponding result.

(λf. λx. f (f x)) (λy. Y * 3) 2

Answer 1

Explanation:

Reduction to normal from using lambda-reduction:

The given lambda - calculus terms is, (λf. λx. f (f x)) (λy. Y * 3) 2

For the term, (λy. Y * 3) 2, we can substitute the value to the function.

Therefore, applying beta- reduction on "(λy. Y * 3) 2" will return 2*3= 6

So the term becomes,(λf. λx. f (f x)) 6

The first term, (λf. λx. f (f x)) takes a function and an argument, and substitute the argument in the function.

Here it is given that it is possible to substitute the resulting multiplication in the result.

Therefore by applying next level beta - reduction, the term becomes f(f(f(6)) (f x)) which is in normal form.