Computability
Overview
This next set of lectures concerns the question of whether there are problems that provably cannot be solved by computers, and how to identify these.
Two techniques for showing that languages are undecidable, or unrecognizable — which make use of closure properties for the sets of decidable languages and of recognizable languages — will be introduced.
This material will be covered in lectures on October 15–31 and in tutorials on October 23 – November 5.
Supplemental Material
You should not need any reference material, for this, that is not provided on the course web site. However, the following book provides a readable introduction to computability theory, including the use of many-one reductions to prove undecidability:
- J. E. Hopcroft, R. Motwani, and J. D. Ullman,
Introduction to Automata Theory, Languages, and Computation
Third Edition, Pearson/Addison-Wesley, 2007
Lecture #13: First Undecidable and Unrecognizable Languages (Tuesday, October 15)
Why This is Included
Like the other techniques that make use of closure properties (to prove that something is impossible), the techniques that will be introduced to prove undecidability, and unrecognizability, require that one knows of at least provably undecidable language, and at least one provably unrecognizable language, already. The goal of this lecture is to supply these.
While the proof techniques that are used, in this lecture, are of some interest by themselves, the results that are established using them will be considerably more important for the rest of this course.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #14: Oracle Reductions (Tuesday, October 22)
Why This is Included
“Establishing an oracle reduction” is the first technique to prove undecidability, that is based on a closure property, which will be introduced in this course. This is often the first such technique introduced, in introductions to computability, because it can be easier to discover and present oracle reductions than the other kind of “reduction” that will be introduced after this. As this lecture explains, oracle reductions can be used to prove that various languages are undecidable if you know of at least one undecidable language already.
Preparatory Reading
Lecture Presentation
Finishing Up
Tutorial #12: Oracle Reductions (Wednesday, October 23 and Thursday, October 24)
Lecture #15: Many-One Reductions (Thursday, October 24)
Why This is Included
While oracle reductions can be used to prove undecidability, because the set of decidable languages is closed under these reductions, the set of recognizable languages is not closed under these reductions, so they cannot be used, in the same way, to prove unrecognizability. Many-one reductions between languages can be trickier to find and describe — but the set of recognizable languages is closed under these reductions, so that many-one reductions can be used to prove unrecognizability and to prove undecidability.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #16: Proofs of Undecidability — Examples I (Tuesday, October 29)
Why This is Included
The “many-one reductions” that a student might be asked to provide, to solve a problem on a test, might be very different from the “many-one reductions” that a student might be asked to provide, to solve a problem on an assignment. The “many-one reductions” that were used to establish the undecidability of problems, when computability theory was developed, are different again: The first (kind of) many-one reductions are often shorter and simpler than the second, and the second (kind of) many-one reductions are shorter and simpler than the third.
The lecture presentation for the previous lecture included the kind of a “many-one reduction” that one might expect to use when solving a problem on a test. This lecture will include a discussion of a many-one reduction that looks more like what one might be asked to use to solve a problem on an assignment, instead. Advice will also be given about how to work on this kind of problem.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #17: Proofs of Undecidability — Examples II (Thursday, October 31)
Why This is Included
Sometimes, one example is not enough. This lecture will include another “many-one reduction” resembling those that you might be asked to give when solving a problem on an assignment.
