| RHF Joke Archives |

Note: Apologies to non-cs types.
 

	   Recent Results in Theory of Computing - I
	   -----------------------------------------

	      "The Halting Problem is Solvable" 


A fundamental question in the graduate computer science carriculum
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 succeded 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 existance 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)

| RHF Joke Archives |