October 18, 2017 Wednesday
Bedtime Story
How to Encode Recursion in Lambda Calculus
Last night I had told you that when writing
previously about Haskell Curry, I had given his famous Y combinator a miss.
There was a reason for it.
Since that night till tonight, all the nights
from then on I had devoted to building up the background and laying the ground
work to understand the concept of combinators in general.
Finally content that we are now fit to
understand it, I shall go into the Y Combinator.
Let me first write down the Y combinator to
show you how it looks like.
Then we will go on to talk about it.
Y = λf. (λx. f (x x)) (λx. f (x x))
This perhaps appears just a garble of
meaningless letters to you with no pattern nor any meaning.
I hope that by the time we complete this
story, this expression not only will become consequential and pithy but you
will also be able to write it down on your own on demand or request simply
because of its association with something else.
This is a very famous lambda calculus
expression, perhaps the most famous expression of lambda calculus.
As we had discussed earlier, lambda
calculus has almost nothing in it except for three things:
(1) Variables
(2) Way of building functions
(3) Way of applying functions
With just this much, how can you encode
recursion into the system of lambda calculus?
This expression, mon ami, that you are
seeing is the key to encoding recursion in the lambda calculus.
Now you may ask what the big deal about
recursion is.
Well, I did not know before but came to
know only very later in life that recursion is a big deal in computer science.
Why is it so?
This question needs some explanation.
First I shall just state why recursion is so
crucial to computer scientists and then following that I shall give a broader
explanation.
Computer science is essentially about
problem solving or perhaps even more fundamental than that.
Computer scientists are more interested in
knowing that given a problem, can it be solved in finite number of steps or
there is simply no solution that can be defined with an algorithm?
This essentially boils down to Hilbert’s
famous 1928 decision problem or the Entscheidungsproblem.
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