October 23, 2017 Monday
Bedtime story
Decision Making and Loops
Last night we were recapitulating the
basics of lambda calculus and recalling how we had constructed the true and
false function in it.
True = λx.λy.x
False = λx.λy.y
The True function takes in two variables
and gives as output the first variable whereas the False function takes in two
variables and gives as output the second variable.
With these two function then, one can go on
to define other higher logical functions or gates such as NOT, AND or OR.
These True and False functions are very
critical to programming as they are fundamental to decision making and problem
solving activities.
With just these two simple lambda calculus
expressions, True = λx.λy.x and False = λx.λy.y , you already have a powerful
mechanism to make decisions given two choices.
Decision making and problem solving is not
only required by simple machines such as air conditioners or a refrigerators or
calculators but even living organisms.
The next question that we have to deal with
is how to encode recursion into lambda calculus using such simple expressions.
One way is to simplify things and reduce
the problem.
Let us see what can be the simplest
definition for a recursive function.
Well, the simplest recursion would be a
program that loops.
Just look at the following single line
program.
Loop = Loop
It hardly needs any explanation that this
program will continue to go round and round in loops in a single place.
It is perhaps the simplest recursive
program that can be written down.
Now can this simplest loop be encoded into
the lambda calculus?
Perhaps yes and the technique that can be
used is self application.
In self application, a function is applied
to itself.
Let us first define our loop.
loop = (λx.x x) (λx.x x)
We have placed copies of two functions side
by side.
In lambda calculus placing a function side
by side means a function is being applied to itself.
Now look at each function itself.
(λx.x x) implies that the function λx takes
in x and applies it to x.
So this function too is a self application.
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