Short History of Computing

“Go down deep enough into anything and you will find Mathematics.” This is exactly what I experienced when I started grad school in Computer Science. I just want to share my incredible journey from Computer Science to Mathematics. I think it is worthwhile to understand how concept of computation and Mathematics are inextricably linked.

People often tend to ignore mathematics while learning Computer Science. You need not be a Mathematician to be a Computer Scientist however every computer scientist or professional must understand the underlying mathematics of computation. It is also very beautiful and fascinating.

In my opinion Computer Science was born when Kurt Godel wrote his proof of Incompleteness theorem in 1931. This is arguably the most important and beautiful result in last 2000 years. This proof has answered the long pursued question by many great thinkers including Greg Cantor. "Is there a theory of everything?". The answer is negative. Godel had proved limits of mathematics using mathematics, limits of science using science. He proved that the concept of "Theory of Everything" of fallacious.

It was not obvious to many people that this deep result will give rise to an extremely promising field that will change the face of the world. This was because Godel's proof was complicated in nature and was based on formal language. In 1936 Alan Turing reformulated Godel's result with the concept of Turing Machine and defined the terms Computation and Algorithm. While the results are same in nature the concept of Algorithm, Computation and Turing Machine are much more graspable than the formal language based proof of Godel. Turing's result presents what is computable and what is not computable. Later on he also proved the undecidability of 'Halting Problem'. Both Godel and Turing were extraordinary mathematicians of the 20th century.

A lot of research in mathematics contributed to the idea of computation. The famous Church-Turing theses states or hypothesized that all the computational models are equivalent to Turing machine. Or putting in other words, the set of computable functions remains same under any computational model. This was a very fundamental and ground breaking result as the concept of computation proved to be independent of the underlying computational model.

After it was proven that the concept of computation had an emmence potential, electric engineering research focused on building computers. It led to successful development of early computers and various research challenges were faced by the newly born computer science community. In my opinion the two research papers stand out in terms of their contribution to Computer Science.

First paper is by Juris Hartmanis and Richard Stearns. They proved the time complexity theorem. Performance of any computer program / software is measured mainly on the basis of its asymptotic running time. The concept of running time is not something that is defined for our convention but it is an intrinsic property of computation. Those who are familiar with the notion of BigOh BigOmega etc, should understand that these concepts are not defined for convention. It emerged as an intrinsic property of the algorithm.

Second major contribution is the Theory of NP-Completeness which is a beautiful theory in itself and also an extremely interesting topic of research.

Theoretical Computer Science looks at these topics in depth. When you start studying Theory, you go in the reverse direction the development of Computer Science. You will never realize when you escaped from computer science and entered the realm of pure mathematics. The borders lines are as thin as soap bubble surface. Computer science in a way is a branch of Mathematics which can be a realized using digital computers.

On Sachin Tendulkar's double century ....

He has never forgotten why he started playing the game in the first place. The best have lofty ambitions when they begin but soon commerce, like a tenacious worm, gnaws into them. Fame surrounds them and prevents the fresh air of reason from breaking through. They acquire sycophants, that great curse of success. Playing the game becomes a means to a seemingly superior but, in reality, a hollower end. Tendulkar has kept those demons at bay. He has made more money than anyone else, acquired greater fame than is imaginable but you could never guess that from the way he plays his cricket. He remains the servant, pursues the game with purity. Through the last decade India have been well served by like minded giants.
And he works as hard as anybody has. Lance Armstrong once said that he wins the Tour de France not when he is cycling down the Champs-Elysees but when he is out in the mountains facing icy winds while others are cozying in their blankets for an extra hour.

Finding Problems to Work On - Prof Lance Fortnow

Often graduate students ask me for a good problem to work on. This is one of the biggest challenges of an advisor. A good problem for a graduate student must fulfill each of three characteristics.
1.Open.
2.Doable.
3.Interesting.

Finding problems that fit any two of these three is not hard, but if a problem is doable and interesting, someone likely would have solved it by now. Too often interesting is the property that is given the least emphasis.
I generally give the advice that my advisor, Michael Sipser, gave to me. Pick up a proceedings of a recent conference in your area and read through the abstracts of papers until you find one that interests you. The "interests you" part is important, for without it you won't have the motivation to study further.

Read the paper thoroughly. Read related papers. If you lose interest, start the process all over again.

Once you've read several papers in an area that interests you talk about it with your advisor and your fellow graduate students. Some of these papers might list open questions and you could work on those. You might say, "Karp listed this as an open question, and if Karp can't solve it why should I be able to?" Karp is a very smart but also very busy person. It is unlikely he spent more than an hour thinking hard about these questions. As a graduate student you can spend much more time focusing on these problems and could easily make more progress than someone like Karp could.

Even better is to formulate your own problems. Perhaps there is an interesting variation in a model that the original paper, for whatever reason, did not cover. Perhaps you can find connections between two papers that no one had noticed before. These are great problems to work on: As you are breaking new ground, theorems can start flowing like water. Just remember not to have too much weirdness in your questions; keep the research interesting.

Only Polynomially bounded algorithm does not suffice.

I have been thinking about my first post for long time. Although I mentioned that predicting the future by pure computation is NP-hard problem, I was not satisfied. Intuitively, the problem is much more harder. And here is the idea how it is.

Since the life is a real time process or it runs in linear time, to know the future in polynomial time is not a sufficient condition. The computation should be done in Linear time Algorithm. As we suspect that P=NP isn't true, it is near to impossible that the NP-hard problem can be solved optimally in polynomial time algorithm. (Again this is a conjecture). And solving a NP-hard problem in a linear time looks more near to impossible. Hence its much harder.

Approximate Nature

The notion of approximation has brought forward a completely inherent phenomenon of the nature. The interesting fact that not all the problems in the nature have optimal solutions. And it is pretty evident that every action that happens around us, may not be the best way it can be done. Again the most interesting example of 'Human Brain' is valid here. Not all the time we do things optimally. Many times an approximately good choice suffices and we opt for it. We may not be interested in acting optimally every time (though it will be very interesting :P to get the optimal result).

The whole point here is, the study of Approximation is crucial. And the resemblance of computational processes with the natural processes has given a nice directions and platform to study it. Approximation Algorithms a recent field has given many directions to the problem solving domain. It is not solving the only computational problems but many problems that lie at the base of this world. The P versus NP question again has interesting significance here. If (P=NP) then a huge set of natural problems will be optimally tractable rather than being approximably tractable. (Which does seem unlikely but nobody knows yet for sure.) Again this kind of thought might lead to confusion. If nature does not act optimally then how does it manage to maintain such a huge equilibrium? Or are there many optimal solutions? The question is wheather the optimal solution needed or an approximate solution suffices. The approximate versus the optimal solution problem is actually a nice thing to obtain the truth about the optimality.

Truely the P versus NP problem has its own beauty. Its not just a mathematical or a computer science problem but one of the problems that lies at the crux of the nature.

Complexity of life.

Since this is my first blog I thought I would put little thoughts on "Complexity of Life".

I believe that figuring out how to make your life best or ideal (optimal in mathematical terms) is one of those complex decision problems called Non-Deterministic Polynomial-time (NP). I don't have a proof to this argument. Consider the verifier based definition of problems in NP. If there exists a verifier running in polynomial time (P) for the solution of the algorithm then then we call that the problem in in NP class.

Now imagine you are 84 years old and had a pretty good life so far (maybe a good career in computer science) and you are sitting in the park thinking about your past life. Suddenly God appears in front of you and he starts discussing about your the decisions in your past life. He wants to explain what could have been the best decisions for your life (optimal decisions) that he had written in his book.

He tells you if you had done BS Mathematics instead of Computer Science you would have topped university. And then if you chose to attend Princeton mathematics discarding the Stanford admit your Phd thesis on combinatorics (again a choice) would have won the best thesis award. After graduating from Princeton if you chose to become a professor letting go a lucrative job offer, you would have won a "Fields Medal"......

Or he tells you if instead of working for others all your life, if you had trusted your gut and started your own finance company, you would have been the richest man on earth...

And You faint ..

You have done good enough with your life, but you could have done better. It is easy to verify (in P TIME) the decisions in God's book (answer to the decision problem) about doing BS in Mathematics and going to Princeton were clearly the best choices for your life because they led to Optimal solution. But the question is can we find this answer in a considerable amount of time at the start of your life? (or at the end. but that wont help.) The answer is unknown.

If we consider every choice of your life and try to find a solution the time to find this will be approximately 1000000.......(I dont know where to stop) in any time-unit. Thats what makes it hard.

But human is an ingenious creature. Though we cant figure out what is ultimately (optimally) best choice for us we have some lookahead and by using that we can find an approximate solution to our lives (OPT/alfa). In some cases it performs very well (alfa=1) and for some cases its not that good.

At the end what I want to say is finding the optimal solution to the "life problem" is a NP problem. Since its not yet proven that P=NP we can still hope... But we have approximate solutions that do well if we give our best as an input to the algorithm.

So there is an approximation solution to the life and it performs best when we do our best .. Obviously we can check how well did we do in the the God's book later on in the heaven ...

Vinay