The Halting Problem

First of all, an introduction. 

The Halting problem:

Consider a program 'A' which accepts a program 'b' as an input. It gives 'true' as an output if the program 'b' stops(or halts) after a finite time. It returns 'false' otherwise. The problem is that whether such a program 'A' exists or not.

Finding a solution:

Let us try to write a pseudo code for program 'A'.

A(program b)

{
   if(itHalts(b)) 

      return true;

   else

     return false; 

}  

You may be wondering what does itHalts() procedure do. Well, as the name suggests, it checks whether a program passed to it halts or not.

Wait !  

itHalts() checks whether a program halts or not.....Right ? We just said that program 'A' is assumed to do just that !

Let's then write the itHalts() procedure as the procedure 'A'. The pseudo code will then become:

A(program b)

 {
   if(A(b))  

     return true; 

   else 

    return false; 

 }

That's the problem with the algorithm.... it goes into infinite recursion ! No matter, how much time and computational resources, you provide, the program will never succeed in reaching an answer.

Thus, the "Halting problem" is indeed intractable - it cannot be solved by any computer.

The original problem was posed by the legendary David Hilbert. It was called the Entscheidungsproblem ('Entscheidungs' in German means "decision-making").

This problem was shown to be unsolvable by Alan Turing in his famous paper titled Computing Machinery and Intelligence which was published in the year 1950. It was a path-breaking work. More information could be found in standard books.

 

Intelligence vs. Evolution

If you are reading this, and understanding what I have written, then you may be called an intelligent being. By intelligence, I mean that you are quite able to grasp the characters before your eyes and through your accumulated knowledge of English language, you're able to understand what I have written. 

That's great ! You should be thankful to the millions of years of evolutionary processes that went towards it.

Now, for some moment, consider a butterfly. It has also evloved through millions of years and is quite dextrous in what it does. Can it be considered intelligent ? Ofcourse ! But, its not quite intelligent as us. 

Now a comparison: the butterfly is far more intelligent than the device you're using to see this post. Also, it has mastered the ability to fly (at moderate speed) and can mitigate obstacles quite easily.

It may also come in your mind that we humans have also made robots that can function as flying machines. Yeah we did :)

So, the interesting observation: we humans, who have lived on this earth for some 12000 years, have become so intelligent that we can create a robot that can mimic a butterfly(which has taken millions of years to evolve) ! Just amazing ! Intelligent beings creating intelligent beings within a far less time than what nature had taken...

 This observation can help you understand Technological Singularity (I recommend you to go over that link and check for yourself).

We have intelligence.  Intelligence enables us to do far greater things by taking in control of our surroundings. Also, evolution is helping us: with each passing decade and each passing century, we are becoming more intelligent and so our machines. 

Who will triumph ? We, who were created by evolution or the machines that will be created by us ?


I don't know. But, all hail to Intelligence.