October 25, 2017 Wednesday
Bedtime Story
Last night I had left you with one possible
definition of recursion in lambda calculus:
rec = λf. (λx. f (x x)) (λx. f (x x))
This specific definition of recursion
function in lambda calculus is known as the Y combinator which was the eventual
target from the very beginning.
This was discovered by Haskell Curry and I
have no idea why he or anybody else gave this function the name of Y
combinator.
This definition of recursion very
understandably looks to be daunting and intimidating, but I beg you to place it
next to our initial definition of loop and compare them.
rec = λf. (λx. f (x x)) (λx. f (x x))
loop = (λx.x x) (λx.x x)
Do you see that uncanny resemblance?
In both the formulations, there are exact
two functions placed next to each other.
In the original looping case the function
is (λx.x x) and in the case of Y combinator it is (λx. f (x x).
In both the instances, the idea of self
application is being applied.
The only significant difference is that in
the case of Y combinator there exists that additional function f within the
function.
That f is needed to make the Y combinator
fit the definition of recursion as recursion demands that a function be defined
in its own terms as we saw in the case of factorials.
This Y combinator encodes recursion into
lambda calculus.
It may look benign and simple but it is a
powerful idea, an idea as powerful as elementary logic gates or in biology that
cells are the fundamental units of structure and function in all living
organisms.
Strangely enough, that last sentence is one
of the three tenets that go under the rubric of cell theory.
The word “theory” very often leads to unnecessary
debates and proclaimed by deniers of fact with great gusto as “only a theory”.
Evolution of life is heatedly debated in
the same manner which only demonstrates lack of knowledge on that subject.
Anyway, let us not get into silly debates
and return back to the Y combinator and its power to encode recursion into
lambda calculus.
This simple idea is deployed in all
functional programming languages in computer science.
I think I am almost done with Y combinator,
buy hey wait a second!
There is something very interesting about Y
combinator that even many computer science guys probably will find novel and
noteworthy and that I shall take up in the nights to come.
Stay tuned to the voice of an average story storytelling
chimpanzee or login at http://panarrans.blogspot.com
Good night mon ami and my fellow cousin ape.
Advertisements
Another great educator and a teacher that I am aware of is
Professor Subhashish Chattopadhyay in Bangalore, India.
While I narrate stories, Professor Subhashish an electronic
engineer and a former professor at BARC, does and teaches real mathematics and
physics.
He started the participation of Indian students at the
International Physics Olympiad.
Do visit him here:
All his books can be downloaded for free through this link:
For edutainment and English education of your children, I
recommend this large collection of Halloween Songs for Kids:
No comments:
Post a Comment