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.
Lecture #13: First Undecidable and Unrecognizable Languages
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
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
Lecture #15: Many-One Reductions
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
Tutorial #12: Reductions and Undecidability I
Lecture #16: Proofs of Undecidability — Examples I
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 previous lecture presentation 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
Tutorial #13: Reductions and Undecidability II
Lecture #17: Proofs of Undecidability — Examples II
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.
