Optional Presentation

Purpose

This exercise deepens both individual and class understanding of undecidability (and perhaps other forms of noncomputability) and how to prove it.

Background

This exercise is based on the ideas of undecidability and reduction presented in chapter 5 of our textbook. We will cover this material in lectures between March 30 and approximately April 13. Be aware, however, that the main material from the presentations you will do for this exercise must come from sources outside of our textbook and class discussion.

Activity

Identify some undecidable (or otherwise algorithmically unsolvable) problem not covered in our textbook or class discussions, find and study sources describing it, and give an approximately 15 minute presentation to our class about the problem. Also give me a one to two page written summary of your findings, including a bibliography of sources you consulted.

Presentations and written summaries should minimally include a description of your problem (i.e., what it is) and a summary of the proof that it is unsolvable. Depending on the problem, you might also include discussions of its real-world applications or other things you consider important about it.

I will be happy to meet with you before your presentation to go over drafts of it and of the written summary. You don’t have to do this, but I strongly encourage it—it’s the best way to know ahead of time whether your work is likely to meet the standards for waiving Math 348, and, if not, how you need to improve it; the mere act of giving a presentation isn’t necessarily sufficient.

The presentations and written summaries for this exercise must be prepared and given individually in order to get a waiver for Math 348. You may, however, help one another with the research.

Follow-Up

Please let me know by Monday, April 25, if you plan to do this exercise. You can subsequently decide not to present, but I need an upper bound on the number of presentations ahead of time so I know how much class time to reserve for them and how many pre-presentation drafts to expect to review.

Your main reward for doing this exercise is a possible waiver for Math 348, the research and presentation requirement for the math major.

This exercise is completely optional, and carries no direct credit towards Math 304. I do, however, believe that studying an unsolvable problem on your own and in detail will help you understand the limits of computability and therefore do better on the final exam and perhaps the last problem set(s), and that hearing the presentations will improve everyone’s understanding of computability.