The Blog

Thursday, August 11, 2005

Halting problem solved

Recent Results in Theory of Computing - I

"The Halting Problem is Solvable"

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)

(from rec.humour.funny)

4 Comments:

At 8/12/2005 10:45:00 AM, Anonymous Zoheb said...

There is a mistake in the proof, where the SuperGrad is fed a description of himself. This proves that a solution may sometimes exist, but may not always exist.

 
At 11/16/2005 04:18:00 PM, Anonymous concentrate said...

Hey Mahesh,

Your blog "Halting problem solved", leads me to believe you will find my information on study guides to be very beneficial.

Some of the not so common searches that found our extensive site included ... certification study aids exam programs, firefighter study aids, study aids for elementry, mpre study aids, lpn study aids, patent bar exam study aids and firefighter study aids mpo.

We have many hundreds of study prep guides and aids to help you pass your exams without weeks and months of endless studying.

Best Wishes
Emily

 
At 3/13/2010 06:32:00 PM, Anonymous Anonymous said...

Nice dispatch and this enter helped me alot in my college assignement. Gratefulness you for your information.

 
At 4/24/2010 02:09:00 AM, Anonymous Anonymous said...

Sorry for my bad english. Thank you so much for your good post. Your post helped me in my college assignment, If you can provide me more details please email me.

 

Post a Comment

<< Home