On Wed, Apr 17, 2013 at 10:27 AM, Nicholas Thompson <
[email protected]> wrote:
>
> <snip>
>
> 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?
>
Your basic English.
> 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?
>
Well, I do get asked a lot about computation and have found a "progressive
disclosure" approach best. I'd start by saying exactly what Michael
Sipser, Intro to Theory of Computation, does:
"The general problem os software verification is not solvable by
computer".
Usually that is clear enough but if more is needed, we progressively
discuss what software is and how it is modeled in computer theory. Believe
it or not, I've had this sort of thing lead to Finite State Automata, first
as circles and arrows but then to the formal 5-tuple. And this was not a
mathematically sophisticated person.
-- Owen
============================================================
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
