September 30, 2017 Saturday

Bedtime Story 

What Makes Lambda Calculus so Invaluable 

Tonight we shall consider the other two arguments on what makes lambda calculus, in spite of its simplicity, so powerful.

The first was its universality in the area of coding.

[b] The second important point that makes lambda calculus so fundamental in modern times is that in can be considered as the basis for all functional programming languages like Haskell, Python, Elixir and so on.

Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions.

It avoids changing-state and mutable data.

This means that the output value of a function will solely depend in the argument fed into it unlike say in the case of Turing machine concept where the state of the machine has a crucial role in deciding the output.  

Programming paradigm is a way of classifying programming languages depending upon its style, structure and elements.

Lambda calculus despite being a mathematical abstraction forms the basis of almost all functional programming languages used today.

It is said that the origin of functional programming lies in the lambda calculus which was originally developed to study computability of a given function, Entscheidungsproblem, function definition, functional application and recursion.

Lambda calculus provides a theoretical framework for describing functions and their evaluations.

[c] The third important aspect of lambda calculus is that it is now present in most major programming languages.

Earlier this was not the case bit it is today.

Programming languages such as Java, C# (C Sharp), Visual Basic, F# (F Sharp) and so on, they all either encode lambda calculus or have it as their fundamental component.

Hence it becomes a subject of great importance for computer scientists.

The odd thing is visibly lambda calculus is profoundly simple and has nothing much in it.

It lacks numbers, logical values, recursion and other such elements.

Yet with such simplicity can arise great complexity.

Just like few simple atoms of elements can form very complex biological molecules and these not co-complex molecules can form chain which can ultimately encode life itself.

Same it is with lambda calculus; simple as it may be yet everything including numbers, logical values, recursion and so on can be encoded into it.    

In fact they actively have to be encoded into lambda calculus.

So let us see how one can encode logical values True and False into lambda calculus.

We shall consider this encoding 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:

http://skmclasses.weebly.com/

All his books can be downloaded for free through this link:

https://zookeepersblog.wordpress.com/science-tuition-chemistry-physics-mathematics-for-iit-jee-aieee-std-11-12-pu-isc-cbse/

For edutainment and English education of your children, I recommend this large collection of Halloween Songs for Kids:

https://www.youtube.com/channel/UCd14DRdYKj454znayUIfcAg

September 29, 2017 Friday

Bedtime Story 

What Makes Lambda-Calculus so Formidable?

Kleene-Rosser Paradox showed that certain systems of formal logic are inconsistent.

This specially referred to the system of combinatory logic invented by Haskell Curry in 1930s which we will go through in some future night.

In fact Kleene and Rosser found some inconsistency even in the original lambda calculus of Church.

This forced Church to isolate a portion of his original work and publish just a portion that is relevant to computation.

He did so in 1936 and this is now called untyped lambda calculus.   

You should know that if there is an untyped something then there also got to be its counterpart types something.

So in this case, there is also something known as typed lambda calculus.

Typed lambda calculus was the original version and they are characterized by the fact that the function can be applied only if the given input “type” is compatible with the functionality of the lambda calculus.

We need go into the details of types, untyped and simply typed lambda calculus as that is too technical for a bedtime story and may even bring you to sleep much faster that I would want to.

The point that I wanted to raise was is what makes lambda calculus so important for computing in spite of the fact that at its heart, its premises or its syntax are almost childishly simple.

   

There can be made three arguments for it:

[a] For one, there is a kind of universality to it.

It was later discovered (meaning it was not intended so in the initial publication) that lambda calculus can encode any computation.

Any program in any programming language that has ever been invented or will be invented can be coded in lambda calculus no matter how tedious or convoluted it may be.

Now as it is known to all computer scientists and programmers that Turing machine too can program or encode any computation that is possible by any machine.

I will take up the concept of Turing machine and its origins in more detail later.

It is a fascinating story that has its origins once again in the foundations of mathematics crisis of late nineteenth century.

The universality of Turing machine is far better known but what is less well known is that both lambda calculus and Turing machine are exactly compatible.

What can be programmed in Turing machine can be programmed into equivalent lambda calculus program and vice versa. 

Hence these two systems are formally equivalent.

We shall take up the other two arguments in the nights to come.

I like to keep my bedtime stories short, sweet and engaging so that I don’t get burnt out in writing it and my reader doesn’t get fed up reading it.

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:

http://skmclasses.weebly.com/

All his books can be downloaded for free through this link:

https://zookeepersblog.wordpress.com/science-tuition-chemistry-physics-mathematics-for-iit-jee-aieee-std-11-12-pu-isc-cbse/

For edutainment and English education of your children, I recommend this large collection of Halloween Songs for Kids:

https://www.youtube.com/channel/UCd14DRdYKj454znayUIfcAg

September 28, 2017 Thursday

Bedtime Story 

The Syntax and Essence of Lambda Calculus

Now having this much knowledge, let us go directly into the syntax of lambda calculus.

Please do not get scared by the word syntax.

Syntax simply means notations and the set of rules that are made which will govern a mathematical system or a language.

After all, even sports are governed by rules and regulations.

Using this syntax devised by Church, you can define a function which after all was the whole point.

The first symbol that comes in the syntax of lambda calculus is of the small case Greek letter lambda or λ.

So how can you write down the function that we took as our first example where any input x would come as x + 10.

This is how.

λx.x+10

This is read out as lambda x dot x plus ten.

Doesn’t seem to very difficult, does it?

Now I am sure you can easily figure out how to write down the second function that we considered in the syntax of lambda calculus.

λx.λy.x+y

This is read out as lambda x dot lambda y dot x plus y.

So what can we do with a function so created with this weird lambda notation?

We can perform operation on specific numbers which are substituted into the variables like x and y.

So if we take the first incremental function and feed in the value of 10 in the black box, we get the output of 20.

This is in essence is the gist of lambda calculus.

So lambda calculus comprises of three things:

(1) Variables such as x or y

(2) A way of building function using λ notation

(3) A way of applying function       

When you see how simple it is, you must be wondering what is so great about it and why to make a big fuss of it.

What was the whole point in simply devising a new notion to the idea of function?

To begin with, Church was not motivated by the idea of computing, programming or even computable functions.

Being a student of David Hilbert at Gottingen, he was purely interested in attacking the foundations of mathematics as the existing system of Curry’s combinatory logic which we will come to later was shown to have inconsistencies.

This was demonstrated by Stephen Kleene and J. B Rosser (both students of Alonzo Church) through now what is famously known as the Kleene-Rosser paradox.

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:

http://skmclasses.weebly.com/

All his books can be downloaded for free through this link:

https://zookeepersblog.wordpress.com/science-tuition-chemistry-physics-mathematics-for-iit-jee-aieee-std-11-12-pu-isc-cbse/

For edutainment and English education of your children, I recommend this large collection of Halloween Songs for Kids:

https://www.youtube.com/channel/UCd14DRdYKj454znayUIfcAg

September 27, 2017 Wednesday

Bedtime Story 

Consider Lambda Calculus as a Black Box

As I said last night, whatever little I do know on these subjects (mathematics, formal logic and computer science) is largely inspired by mon ami’s fascination for these subjects and my fascination for his fascination.

Hence there is an element of recursion in my interest on these subjects.

Yet even for an average ape lambda calculus in principle is not a very difficult idea to grasp.

Church was studying notion of a function from computational perspective.

From the way Church considered function, pictorially you can consider function as a black box.

This black box is so black that you are not allowed to look what is going on inside.

You may wonder what this box does.

Well, the box acts like a function.

It takes in an input, processes it and gives an output.

This is all that a function does.

For instance, it can take as input any variable x, process it and give an output of say x + 10.

This is a simple function that adds 10 to any number that goes as input.

So in this case, we have a single input and a single output.

Consider this second case where there are two inputs x and y.

The black box takes in two inputs, processes them and gives the output as x + y which just means the function is summing of the two inputs.

There are two important things about this box that Church considered it worth noting:

(a) The Box is black, really black in the sense that it is opaque.

You are not allowed to see what’s going on inside which essentially means you have no idea how the black box is processing the data that is being fed as inputs.

(b) The function is pure.

Now what do I mean by pure?

Here the word “pure” comes in a highly technical sense wherein a comparison is being made with Turing machine concept.    

The so called purity in this case is that this box has no internal state, a concept that was of critical importance in Turing machine that contains a state register which stores the state of the Turing machine.

We will come to that later.

So suffice to say that the black box of lambda calculus has no internal state; it is a pure mathematical function.

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:

http://skmclasses.weebly.com/

All his books can be downloaded for free through this link:

https://zookeepersblog.wordpress.com/science-tuition-chemistry-physics-mathematics-for-iit-jee-aieee-std-11-12-pu-isc-cbse/

For edutainment and English education of your children, I recommend this large collection of Halloween Songs for Kids:

https://www.youtube.com/channel/UCd14DRdYKj454znayUIfcAg

September 26, 2017 Tuesday

Bedtime Story 

A Set of Postulates for the Foundation of Logic 1932

As mon ami says, in the name of atheism I was carrying out my own jihad on disbelief which in a way is no different from any other religion.

So let us leave aside the religious beliefs of Church and return back to our primary theme of the story, which is the Entscheidungsproblem and the contribution of Alonzo Church to it.

Church too began to ponder over the problem that Hilbert and Ackermann had posed: Is there a decision procedure to determine if any particular statement of first-order logic is true or false?

Church too was interested in the foundations of mathematics.

In 1932 Church published a paper in the journal Annals of Mathematics titled “A set of postulates for the foundation of logic”.

He republished this paper in 1933 with further refinements.

It was in these papers that Church first introduced lambda-calculus or λ-calculus.   

You might think from the name that this lambda calculus must be that formidable calculus that so scared you in high school or maybe even worse than calculus since it has that dreadful lambda added along to calculus.

You will be surprised to know that the calculus of Church has nothing to do with mathematical analysis that involves differentiation and integration.

What is common to both the calculi though is the notion of functions albeit considered in totally different ways.

I discussed a lot about functions in my previous bedtime stories.

The function that Church was dealing with is specifically known as computable function.

Computable function has a direct bearing on the problem that was posed by Hilbert and Ackermann.

And on the other side, computable functions have a deep-seated link with algorithm that in the modern world forms the basis of computer programming.

Computable functions are formalized analog of the intuitive notion of algorithm that we all very familiar with even if we have never been programmers in any serious sense.

To put it most simply, a function is computable if there is an algorithm for it.

Or in other words, if there is a certain input, using certain finite number of steps, its output can be worked out for that function.

Let me try to explain lambda calculus in as simple way as it is possible.

I am no computer scientist without any formal training either in mathematics, or in formal logic or in computer science.

Whatever little I do know on these subjects is largely inspired by mon ami’s fascination for these subjects and my fascination for his fascination.

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:

http://skmclasses.weebly.com/

All his books can be downloaded for free through this link:

https://zookeepersblog.wordpress.com/science-tuition-chemistry-physics-mathematics-for-iit-jee-aieee-std-11-12-pu-isc-cbse/

For edutainment and English education of your children, I recommend this large collection of Halloween Songs for Kids:

https://www.youtube.com/channel/UCd14DRdYKj454znayUIfcAg

September 25, 2017 Monday

Bedtime Story 

A Deeply Religious Logician

Mathematics is pure logic and since most of us find mathematics not only difficult but even scary should indicate that human brain is anything but logical.

In that case, one ought to be forced to come to the conclusions that since original mathematicians are extremely logical in their reasoning they are bound to be irreligious. 

Here my assumption was that religion will be rendered meaningless to any mind that follows reason and logic. 

Yet again I proved to be wrong.

I was fascinated to know that such a brilliant logician like Church was deeply religious (Presbyterian Church) till the very end of his life until his death in 1995.  

It is true that many great mathematicians of the past have too been very religious including the greatest of them.

Gottfried Wilhelm Leibniz, Leonhard Euler, Carl Friedrich Gauss, Bernhard Riemann, and of course Srinivasa Ramanujan were all deeply religious even though they may not have been demonstratively so.

I had excused all of them since they were either pre-Darwinian or during their times the idea of Evolution by Natural Selection had yet to sink in.

Ramanujan could not be given the luxury of this doubt but I had considered him to be just an anomaly, as absolute poverty and religious upbringing can account for it.

None of the above mentioned excuses fit for Alonzo Church; he came into this planet in the twentieth century that too in Washington DC obtaining his PhD in mathematics at Princeton under Oswald Veblen - one of the founding fathers of the Institute for Advanced Study at Princeton.

An exceptional student with his very first paper being on Lorentz transformations I could simply find no reason for him to being a religious man.

(The story of Hendrik Lorentz is an immensely engaging one and perhaps someday I will go into it.)

Yet there he was; devoutly religious.

What else is there left to say or argue.

With so many truly great and exceptional men being religious, now finally I have settled down to reconcile with the fact that religion is there to stay and will remain a vital part of any culture or civilization no matter how advanced they are as long as the human brain essentially remains the same.

Neil deGrasse Tyson sums up this idea very well:

“7% elite scientists of the United States are religious and believe in personal god who intervenes in their lives.

Until that number is zero you have nothing to say to the general public.

These are scientists among us in the National Academy of Science who are religious and pray to a personal god.

Figure that one out first before you try to pin point out the general public.

May be there is something in the brain wiring that positively prevents some people from ever being an atheist.  

If that’s the case, in a way they can’t help it.”

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:

http://skmclasses.weebly.com/

All his books can be downloaded for free through this link:

https://zookeepersblog.wordpress.com/science-tuition-chemistry-physics-mathematics-for-iit-jee-aieee-std-11-12-pu-isc-cbse/

For edutainment and English education of your children, I recommend this large collection of Halloween Songs for Kids:

https://www.youtube.com/channel/UCd14DRdYKj454znayUIfcAg

September 24, 2017 Sunday

Bedtime Story

Comparing Gödel’s Completeness and Incompleteness Theorems

Gödel’s completeness theorem says that in a system of first-order logic, there are sentences or axioms that are consistent, and if a sentence in it is provable using these axioms and rules of inference, then it will be true in all models of theory.

Gödel’s incompleteness theorem on the other hand says that given a consistent, computable set of axioms there is a statement φ in the language of arithmetic such that the axioms prove neither φ nor ¬φ.

One must not confuse “true” with “derivable” (or provable).

So the completeness theorem says that given a set of first-order logic axioms in the language of arithmetic, there is a model in which these axioms and their consequences are true.

It does not follow from this that these axioms will allow or are sufficient to prove a arithmetical sentence or disprove it.

Thus there remains a chiasm between what is true and what is provable in a first-order logic system of arithmetic.

It was problems such as these that was bothering David Hilbert and for which he had proposed the Entscheidungsproblem regarding validity of a statement of first-order logic to all models.

Is there way of knowing this answer?

Is there any such procedure?

Is there any such algorithm?

His problem was posed in 1928.

He did not have to wait very long (just eight years) as the answer came in 1936 and not from one but from two independent separate sources by two men, each answering in their very original way.

They were Alan Turing who answered this question with the concept of his Turing Machine and Alonzo Church who solved this problem with his lambda calculus.

Alan Turing has been highly popularized both in books and movies and many if not most modern humans seem to be faintly aware of him and his work, most particularly for his code-breaking work at the Benchley Park.    

Alonzo Church who happens to be both an American and doctoral advisor of Alan Turing is far less known in popular media and to the general public.

A closer inspection of the private life of Alonzo Church made me reconsider something that I once held as a long cherished belief.

It is the connection or rather disconnect that ought to exist between reason/logic and religion.

There is a school of thought which reasons out that the brain of human apes is inherently illogical as is evident from the wide-spread fear of mathematics prevalent in them along with almost pervasive belief in mutually contradictory religions/gods and spiritual mumbo jumbo across the cultures.

The argument is that mathematics is pure logic and since most of us find mathematics not only difficult but even scary should indicate that human brain is anything but logical.

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:

http://skmclasses.weebly.com/

All his books can be downloaded for free through this link:

https://zookeepersblog.wordpress.com/science-tuition-chemistry-physics-mathematics-for-iit-jee-aieee-std-11-12-pu-isc-cbse/

For edutainment and English education of your children, I recommend this large collection of Halloween Songs for Kids:

https://www.youtube.com/channel/UCd14DRdYKj454znayUIfcAg

September 23, 2017 Saturday

Bedtime Story 

Gödel’s Completeness Theorem

Gödel’s completeness theorem establishes a formal connection between semantic truth and syntactic provability in first-order logic.

You will get it once I discuss the theorem with you.

Gödel proved this theorem in 1929 and he stated it as follows:

If a formula is logically valid, then there is a finite deduction (formal proof) of the formula.

In a way, this theorem is implying that the deductive system of a first-order predicate logic is complete.

By complete, he means that all the logically valid formulas can be proven using the established rules of inference.

The implication of this theorem is that a formula is logically valid, if and only if it is the conclusion of a valid deduction.

It can also be stated in terms of model theory.

Let me tell you briefly what a model theory is.

Model theory studies classes of mathematical structures (such as universes of set theory, graphs, groups) from the perspective of mathematical logic.

The object of study is models of theories in formal language.

It examines the semantical elements (meaning and truth) by means of syntactical elements (formulas and proofs) of a corresponding language.

A simple way of putting model theory is universal algebra + logic or an even simpler way is to say that model theory deals with what is true in different models.

Model theory stands on the cross roads of several fields such as mathematics, computer science and even philosophy.

Gödel’s completeness theorem establishes a close link between this model theory and proof theory.

If model theory studies what is true in different models, then proof theory studies what can be formally proven is specific formal systems.

So in a way it establishes a link between truth and proof.

So Gödel’s completeness theorem can also be expressed in terms of model theory in the following way:

Every consistent, countable first-order theory has a finite or countable model.

A consistent theory is defined as one in which for no formula F, both F and ¬F can be proven.       

That simple means that for a given formula in a consistent theory, it is not possible for it to be both true and not true at the same time.

    

At first glance it does appear that Gödel’s completeness theorem and incompleteness theorems contradict each other.

So it behooves me to set these two theorems next to each other and consider if there is any tension between those two.

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:

http://skmclasses.weebly.com/

All his books can be downloaded for free through this link:

https://zookeepersblog.wordpress.com/science-tuition-chemistry-physics-mathematics-for-iit-jee-aieee-std-11-12-pu-isc-cbse/

For edutainment and English education of your children, I recommend this large collection of Halloween Songs for Kids:

https://www.youtube.com/channel/UCd14DRdYKj454znayUIfcAg