Nick asks Owen:
> So, Owen, you meet a beautiful woman at a cocktail party. She seems
> intelligent, not a person to be fobbed off, but has no experience with
> either Maths or Computer Science. She looks deep into your eyes, and asks
> "And what, Mr. Densmore, is the halting problem?" You find yourself torn
> between two impulses. One is to use the language that would give you
> credibility in the world of your mentors and colleagues. But you realize
> that that language is going to be of absolutely no use to her, however ever
> much it might make you feel authoritative to use it. She expects an answer.
> Yet you hesitate. What language do you use?
>
> You would start, would you not, with the idea of a "problem." A problem is
> some sort of difficulty that needs to be surmounted. There is a goal and
> something that thwarts that goal. What are these elements in the halting
> PROBLEM? And why is HALTING a problem?
Nick, Owen may well disagree, but from my point of view you've already staked a
dubious claim,
by assuming (defensably) that "problem" in the MathEng phrase "Halting Problem"
can and should
be understood to be the same word as "problem" in your dialect of English. But
this is, I
think, a false assumption. Now, at least, whatever the case was when the
"Halting Problem"
got its original name (in MathGerman, I think), the meaning that "Halting
Problem" conveys in
MathEng is the same (or nearly the same) as that conveyed by "Halting
Question". "Problem" is
there for historical reasons, just as, in geometric topology, a certain
question of
considerable interest and importance (which has been answered for fewer decades
than has the
"Halting Problem") is still called--even in MathEng!--"the Hauptvermutung".
The framing in
terms of "a goal" and "something that thwarts" is delusive. There is, rather,
"a question"
and--if you must be florid--a "quest for an answer". Note, "*an* answer". Of
course, at an
extreme level (I can't decide whether it's the highest or the lowest: I *hate*
"level" talk
precisely for this kind of reason) there is *the* answer ("no"). But that
isn't, in itself,
very interesting (any more: of course it was before it was known to be "the"
answer). *How*
you get to "no" is interesting, and there are (by now) many different "hows"
(for the "Halting
Question", the Hauptvermutung, Poincare's Conjecture, and so forth and so on),
each of which
is *an* answer (as are many of the "not hows").
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com
