New Avatar

Life is all about change. When man gets bored of routine, decides to do something new. For that matter, even if he is not bored a good change is always welcome.

Today, me and maddi decided to take same welcome change. Forced by hot weather of Kanpur (It's really getting hot over here, maximum temperature recorded is 47 C!!!), we decided to shave our heads. and here is the result. You got to see "bode plot" (tribute to KCJs??!!). It really felt nice after getting shaved. You won't believe but people say I look better after getting my head shaved. *blushes* . Anyways, people believe it or not doesn't matter much though. I found it pretty *cool* (pun intended).

Now, two of us are finding this very enjoyable and we strongly feel that everyone should get their shaved. For once, if not all the time. For more, you can also ask the guy who is accompanying me in the photograph. He will also agree. So bhaiyo aur behno, aage badho aur apne baal katane mein koi sharm mat rakho. Jab bhi marzi aaye apne baal kata len aur ganje hone ka mazaa len. I seriously apologize you all if you find this all writing crap, because I also do. Bahut neend aa rahi hai, but it had to be there on blog. so...

Halting Problem is solvable

Sometimes you come across articles which always remain in your memory. Here is one such funny article, which says Halting Problem is Solvable :-) (For unenlightened, Halting Problem is one of the very fundamental problem in Theoretical Computer Science). So here I go...

From rec.humor.funny archives

Recent Results in Theory of Computing - I

Halting Problem is Solvable

Bala Rajagopalan (raja@cs.uiuc.edu)

A fundamental question in the graduate computer science curriculum can be posed as follows: Given an average grad student doing a Ph.D, will the student ever complete his dissertation? This problem has been termed the "Halting Problem," and it has been an open problem thus far. In the following, we show that the halting problem is solvable. Furthermore, the problem can be solved within the time stipulated by the Graduate College for Ph.Ds or, in the worst case, with only a constant number of petitions for extensions.

The halting problem was first formulated by Alan Turing, who observed a number of his graduate students being apparently busy all the time but never graduating. Turing tried to solve the problem by first stopping all assistantships after the sixth year and then by purging all games from the research computers. Needless to say, his efforts were fruitless. Later, Church almost succeeded in solving the problem when he placed notices in grad students' mailboxes indicating attractive jobs in industry with several orders of magnitude higher remuneration. The so called Church's thesis was that the halting problem is solvable, given enough financial motivation. Church's idea backfired when grads found out that they have to actually work to earn money in the outside world. Thus, far from solving the halting problem, Church aggravated it (After this, we are not sure whether Church himself graduated). Recently, Cook et al have shown that the halting problem falls under a new complexity class, "NP Hairy." (NP hairy is the class of hopelessly complicated problems with no known solutions. The hardest problem in NP hairy has been shown to be the problem of trying to claim standard deductions in the 1040 form).

In the following, we show that the halting problem is indeed solvable. For this, we assume the existence of a "Super Grad," who is capable of working in any area in CS (except possibly numerical analysis). For notational convenience, we call this super grad, S sub G sup i,j sub * (written using a funky theoretical CS font). The property of Super grad is that, given the description of any grad (mostly in terms of the number of newsfiles he/she reads every day) and a description of his/her thesis topic, Super grad will either halt with a dissertation or keep publishing technical reports indefinitely. Now, we give Super grad a description of himself and his own thesis topic. If Super grad halts, we are done (and so is he) otherwise we get a stream of technical reports. But by the "fundamental research theorem" of CS Departments (refer to the graduate study manual) any five arbitrary technical reports on unrelated topics can be compiled into a Ph.D thesis. Thus, we are done in the second case too.

Finally, how long does it take for a dissertation to be completed? The time is either less than or equal to the duration allowed by the Grad College for the completion of a Ph.D or it is greater. In the latter case, infinite number of petitions can be filed for extensions. Since the Grad College never remembers previous petitions, the total number of petitions received by the Grad College is always one, a small constant. (QED)