[Jokes] The Halting Problem is Solvable

[David 'The Raven' Chisnall]

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)