Wednesday, January 13, 2010

Ode to my students + moralizing

First, two tales of hubris and folly. The recursion theorem was a big success with my students. We don't usually teach it in this course, but my students went through the standard material like pie and were hungry for more. Other than a ridiculously easy proof of the undecidability of the halting problem, the recursion theorem yields a slick proof that L_min is not in RE (good luck approaching that one without this tool). Riding a euphoric wave of success, I thought I'd improvise a proof that L_min is not in coRE. I thought I had a clever proof using the fixed-point theorem, but it turned out to be wrong. After spending a couple of days in search of a proof, I turned to mathoverflow (an amazing resource!) where Ryan Williams produced a correct proof.

Second, during the last lecture, a student asked if every undecidable language in RE is complete for RE under mapping reductions. I thought the answer should be true, and tried to prove this during the break. Needless to say, I failed to find a proof. After speaking with Menachem Kojman, I learned that in fact the answer is false; this follows froom the Friedberg-Muchnik theorem.

There are two morals to this story:
1. I was blessed with amazing students this semster.
2. Sometimes (if one is lucky!) innocent-sounding questions that come up in undergraduate lectures turn out to be deep, difficult research problems. By all means attempt to tackle them, but keep in mind this caveat.

No comments: