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.