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.

Advent of Intelligent Machines !

We all have watched the movie Terminator. It revolves around intelligent machines from the future called Terminators, who are sent to eliminate Sarah (and John) Connor so that they couldn't save mankind from the impending doom(Judgement Day).

As you are reading this, I may assume that you have wondered if such machines are possible in reality. 

Yes, they are ! Not now, but sometime sure in the future !

Now, you may wonder how intelligent today's machines are. Frankly speaking their intelligence is not even close to the intelligence level of the stupidiest person on the earth ! 

So, what characteristics should be present in an ideal "intelligent" machine ?

Analysing the premise of the question in terms of how we humans think, perceive and understand; we can safely point out four "has-to-be" properties that can make a machine intelligent. These four properties were laid out by the celebrated Computer-Science pioneer, Alan Turing, some 63 years ago, and is called the Turing test.

• Processing Languages: The machine should be able to communicate in the complex natural languages that humans have developed. At least a human should be able to communicate freely with the machine in a language that he/she speaks.
• Knowledge Retention: The machine should be able to store the information that it receives either by visual perception(through a camera) or by hearing (by an audio-detecting device).
• Response: The machine should be able to give an automated response to different situations in a rational manner. It must also include reflex actions which require no/minimal thinking.
•  Adaptation: The machine should be able to adapt to new situations that it is exposed to and must reach conclusions, that would have been reached by any other sane-human on being subjected to same situation. Also, it must solve problems on the basis of given facts and should have the ability to decide whether a particular problem is solvable or not.

Again, lots of research is going on reaching this feats. For ex: Neural networks that try to mimic human-brain, have become an interest area for many.

Also, you may ask whether an "intelligent" machine should behave exactly like a human or take a rational approach. Or whether it should have the ability to feel boredom like many intelligent animal do ?

Majority of people involved with Artificial-Intelligence (AI) believe that a rational approach rather than a human-like approach, is more feasible and acceptable. Reasons are again clear for that: much less knowledge is available about human thinking, which has been developed by still largely unknown evolution.

So, you can say that AI is quite exciting. It is still a baby-science and lot has to be done in it. 

But, its certain that intelligent machines (which may even surpass humans) will walk on this earth.

Will a John Connor be needed ? Or humans will reach even greater feats with machines that can think ?

Who knows ?

Only future will tell.
      

Factoring: number of ways to factorize a number.

It happens that you learn a new thing or two everyday. Today, I learned how to find the number of ways to factorize a number where order of divisors is not important (4 X 2 is same as 2 X 4).

Let's think about a the problem :

Suppose your number is n. Also, n can be factorized as n = a x b. So, the number of ways to factorize n will be equal to 1 + no. of ways to factorize b !

So, we need a recursive approach. Here's a code in C++ for doing such that:

//This code finds the no. of ways to factorise a number.
//It is based on a recursve code.
//Order is not important i.e; 2 X 4 is same as 4 X 2.
#include <cstdio>
#include <iostream>
using namespace std;

int countWays(int n,int factor)
{
   int i;
   int count=0; //This variable will contain the number of ways
  for(i=factor;i*i<=n;i++)
    if(n%i==0)
     count += countWays(n/i,i) + 1;
 return count;    
}  
int main()
{
    int n,t;
 scanf("%d",&t); //Test cases.
 while(t--)
 {
  scanf("%d",&n);
  printf("%d\n",countWays(n,2));
 }
 return 0;
}

Try to understand it ..its very simple !

Computer Science: A Beginning

So, here you are !
You are reading this either because you are a Computer Science student or want to be one.
Great...so, here I go.

First about computers. Computers make our job easier.
But, how ?

You will explore only this question in the fantastic realm of Computer Science !

But, becoming a good Computer scientist requires immense efforts. Also, you have to become good in the following things.

First and foremost,  you have to develop a sequential thinking pattern (Computers are sequential machines, they execute in discrete steps. They are not like you :- you have a brain which acts as a parallel machine).

Second, you have to get a good grip on a particular computer language which will be your tool for instructing computers what to do.

Third, you have to learn programming and know how some real world problems are solved on computers. The area is vast, but you still have to know some of the basic ideas.

Fourth, practice.... lots and lots of practice. Browse problems, read articles, discuss with your friends and most importantly, remain excited about computers !

Only this much for now. I will expand it if I feel the need to. Till then , good luck !