Proofs That Languages are Undecidable or Unrecognizable
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 16–30 and in tutorials on October 27 – November 4.
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: Universal Turing Machines (Thursday, October 16)
Why This is Included
A “Python emulator” is a program that receives a Python script and input for that script, and executes the script on the input. This can be written as a Python script, itself.
Similarly, a “Java compiler” is a program that receives a Java program as input and converts it into lower-level machine code that can be processed, directly, by a computer. This can be written as a Java program, itself.
This lecture introduce a universal Turing machine — which is, essentially, a “Turing machine interpreter” which is, itself, a Turing machine.
Once one knows about universal Turing machines, one can define an “acceptance language”, ATM, and prove that it is recognizable. A simple proof by contradiction establishes something extremely important, namely, that this language is undecidable. The complement of this language is provably unrecognizable — and proofs of both of these results are also sketched.
Thus, this lecture plays a role that is similar to the lecture about regular languages that introduced the Pumping Lemma for Regular Languages, as part of the discussion of regular languages: It introduces the first provably undecidable and unrecognizable' languages, that are needed in order to use techniques, introduced after this, to prove that other languages ore undecidable or, sometimes, unrecognizable, as well.
