Google
 
Web unafbapune.blogspot.com

Tuesday, September 20, 2005

 

Addition gone mad with Lambda Calculus

In Lambda Calculus, natural numbers can be defined as:
0 ≡ λs.(λz.z) ≡ λsz.z
1 ≡ λsz.s(z)
2 ≡ λsz.s(s(z))
3 ≡ λsz.s(s(s(z))) and so on.
Given the successor function: S ≡ λwyx.y(wyx), what is 2S3 ?
2S3 = (λsz.s(sz))(λwyx.y(wyx))(λuv.u(u(uv)))
(λz.(λwyx.y(wyx))((λwyx.y(wyx))z))(λuv.u(u(uv)))
(λwyx.y(wyx))((λwyx.y(wyx))(λuv.u(u(uv)))) = S(S3)

S3 = (λwyx.y(wyx))(λuv.u(u(uv)))
λyx.y((λuv.u(u(uv)))yx)
λyx.y((λv.y(y(yv)))x)
λyx.y(y(y(yx))) = 4

S(S3) = S4 = (λwyx.y(wyx))(λuv.u(u(u(uv))))
λyx.y((λuv.u(u(u(uv))))yx)
λyx.y((λv.y(y(y(yv))))x)
λyx.y(y(y(y(yx)))) = 5
Hence 2S3 = S(S3) = S4 = 5

Comments: Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?