Owen is right that there are N! ways to map a set of N objects 1-1, onto
another set of N objects. The first object can go to 1 of N objects, the
next to 1 of N-1, etc. That's pretty standard.
As to the Halting Problem, Why not start with the first few lines of the
Wikipedia article ? That is simple and easy to understand.
Joe
On 4/17/13 7:32 PM, [email protected] wrote:
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
--
"Sunlight is the best disinfectant."
-- Supreme Court Justice Louis D. Brandeis, 1913.
============================================================
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
