My first thought is a talk titled something like "What we can't do, infinity, and even bigger". It would cover two proofs that I think have a particularly high coolness to complicatedness ratio: Cantor's proof of the uncountability of reals, and Turing's proof of the undecidability of the halting problem. The outline would perhaps be something like:
1) Infinities are not all equal. There are lots of integers, but there are WAY more real numbers. Spend 20 minutes explaining diagonalization, and what it means.
2) Computer programs can do a lot, but not everything.
Spend 20 minutes explaining the halting problem, and what it means to be undecidable. I'd probably avoid defining Turing Machines, since that seems like a mess, and just talk about it in terms of computer programs, which are hopefully a little more familiar
3) The punch line: Computer programs are countable, like the integers, but the problems that you might want to solve (languages) are uncountable, like the reals. So although computer programs can solve lots of things, actually, most things can't be solved. Hopefully this can be done in 10 minutes given that I've already talked about uncountability and undecidability.
I like these proofs since they don't require any machinery, and seem like they can be done visually with some animations. Thoughts?
6 comments:
Hi Aaron,
I think this is a great choice of topic, for all the reasons you give.
Based on experience of similar pedagogical moments, I have one particular caution: we TCS people have no difficulty thinking of real numbers as interchangeable with infinite binary strings, subsets of
{0, 1}*, 'languages', etc etc....
and thinking of all of these things as defining computational 'problems'. But this does not come at all naturally at first. So in explaining how Cantor's proof implies existence of unsolvable problems, you should use a consistent, limited vocabulary, explaining it carefully at the outset.
After getting the Cantor-derived result across, it's good to acknowledge how most of the uncountably many 'problems' are not really anything we'd ever want to solve, before segueing into the Halting problem as a much more satisfying (and hopefully eye-popping) example of unsolvability.
Of course, the proof of Halting's unsolvability is really the same as that of uncountability, and that's worth emphasizing too.
Hi Aaron,
just thought I'd mention that Steven has actually been teaching these proofs and many more to high school students for several years now as part of his Andrew's leap program. You should definitely talk to him before you give the talk. He will also have excellent slides about this stuff that previously worked well for kids.
Still, you shouldn't underestimate how much preparation it takes if you really want to explain this to high school students. I remember giving a lecture at Andrew's leap once that could have been a lot better ;-)
Moritz
Hi Aaron,
I think you've got the right idea, but you have to be really careful about your audience. Is the uncountability of the reals really that cool to high school students (even technical ones)? Particularly in the context of a "what is science" session, you may not get only mathematically oriented students: you could also get anyone thinking they want to go into any scientific field, like medicine, for example.
For those students, the questions are much more basic: what IS computer science anyways? Most students think computer science is just programming, or they don't know what programming is and have no idea what CS is at all. They're technically oriented, and they're wondering whether or not to major in computer science when they get to college (which might even affect which colleges they apply to).
In particular, for those students, the uncountability of the reals is too abstract to be cool. But the fact that there are things computers can't do has much wider appeal given the ubiquity of computers in modern society.
Or maybe -- though this can be very difficult -- you could poll your audience as to their interests and tailor your talk one way or the other on the spot.
Couldn't you give a "direct proof" of undecidability of the halting problem without ever mentioning the word "uncountable" or even "infinity"? (The direct proof is just the standard proof by contradiction.) This would allow you to cut the first 20 minutes of your suggested outline and replace it with what commenter #3 said (what is computer *science*), and would also let you focus on showing unsolvability of a concrete problem of interest (detecting viruses!) rather than the rather bland statement that there exist undecidable languages (that no one cares about).
Hi,
If I had to give such a talk, I wouldn't give any proofs. I would highlight algorithms since that's something that is much more tangible.
I think Papadimitriou's talk would be a really good example and inspiration to high school kids on what cs is and what one might do with it.
Very good topic.
I think the following could possibly be explained to high school students: lower bound for sorting, the concept of NP and the question of P vs NP (Homer Simpson dreamed about it), randomized algorithm (using polynomial identity testing as an example), communication complexity (using equality as an example), PageRank, the concept of one-way function and cryptography....
Post a Comment