Lecture 17, Nov. 20, 2001.

Done in class:

(1) complement(A_{TM}) is NOT Turing-recognizable.

(2) Halt_{TM} and E_{TM} are not decidable

(3) Reducibilities

(4) Using reductions to prove that a language B is undecidable:

    To prove that B is undecidable, show that A <_m B, for some
    undecidable language A;

    Or, show that A <_m complement(B), for some undecidable
    language A.

(5) Using reductions to prove that a language B is NOT
    Turing-recognizable:

    To show that B is not Turing-recognizable, show that A <_m B, for
    some language A such that A is not Turing-recognizable.


Assigned reading: Sec. 5.1, 5.3.