A Tutorial Introduction to the Lambda Calculus
This article introduces the multiplication function
The multiplication of two numbers x and y can be computed using the following function:
(λxyz.x(yz))
The product of 2 by 2 is then:
(λxyz.x(yz))22
which reduces to
(λz.2(2z))
The reader can verify that by further reducing this expression, we can obtain the expected result 4.
I have no idea how can (λz.2(2z)) reduce to 4. Can anyone show me the process?
the 2 in lambda function is λsz.s(s(z)), and the 4 is λsz.s(s(s(s(z)))).
You can obtain formally the result by applying the substitution, like in the previous examples of the note that you have cited.
Since:
2 ≡ λsz.s(s(z))
we first substitute the second instance of it in (λz.2(2z)) (changing the variable names to avoid capture of free variables):
(λz.2((λxy.x(x(y)))z))
which becomes equal to (substituting x with z):
(λz.2(λy.z(z(y))))
then we apply again the definition of 2 (with a new renaming of the variables):
(λz.((λwu.w(w(u)))(λy.z(z(y))))))
which becomes equal to (substituting w with λy.z(z(y))):
(λz.(λu.(((λy.z(z(y)))((λy.z(z(y)))u)))))
now we can repeat the substitution in the rigthmost lambda, substituting y with u:
(λz.(λu.((λy.z(z(y)))(z(z(u))))))
and finally we can apply the last substitution, replacing y with z(z(u):
(λz.(λu.z(z(z(z(u))))))
which is 4.
As final remark, note that one could be convinced by the correctness of the definition by considering that a number n is a function with two arguments that applies the first argument n times to the second one. So, (λz.2(2z)), is the function that applies two times the function 2z, which is the function that applies two times z, so that the result is the function that applies four times z to its argument.