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)