October 24, 2017 Tuesday
Bedtime Story
Encoding Recursion
The function ‘loop = (λx.x x) (λx.x x)’ is
unique.
It contains a self application function
within which is another self application function.
This function is sufficient to perform
looping or recursion.
We can verify it if it is really so.
Let us look at this function more carefully
(λx.x x) (λx.x x)
What will the function λx do if we feed to
it the input x?
It will take in input x and give the output
x x placing the two x side by side.
In our larger case the input is not x but
(λx.x x)
So in this instance (λx.x x) will be
substituted for x in the first part of (λx.x x).
Doing so will generate back (λx.x x) (λx.x
x)
You can carry this process on and on and it
will only return back the same value.
This was a very simple example of a loop in
lambda calculus.
Let us see if we can broaden our view a bit
and generalize the idea of recursion.
Let us define recursive function as
follows:
rec f = f (rec f)
Here is a function that will take recursive
function as input.
Note mon ami how this one differs from the
previous example that we had considered.
The previous example was Loop = Loop and
then we had applied lambda calculus to it.
So all it gave was same thing again and
again going around in loops.
But our current example is not a loop but a
recursion as there is a function f sitting between two rec f.
On “running” this function, we will get
this:
f (f (f (f (f…))))
This function will go on infinitely
forever.
This is the basis or the idea behind
general recursion in computer science.
If this function can be embedded into the
lambda calculus, then recursion will emerge in it.
One possible definition of recursion in
lambda calculus is this:
rec = λf. (λx. f (x x)) (λx. f (x x))
I will not go into its derivation as that
may not make for an engaging bedtime story for everyone though mon ami will
love it.
We shall work on it 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