CSE 105

Quiz 3 is on November 27, in the regular lecture room, at the regular
lecture time.

Quiz 3 Topics

(1) Turing machines (Chaps. 3.1, 3.2, 3.3): 
    
    different versions of TMs,

    the Church-Turing Thesis

(2) Decidability/Undecidability (Chaps. 4.1, 4.2): 

    the universal Turing machine U,

    decidable/Turing-recognizable languages, 

    closure properties of the class of decidable/Turing-recognizable
    languages,

    the Diagonalization Method, 

    using diagonalization to prove that the Halting Problem is undecidable,

    the class of all languages is uncountable,

    the class of all Turing-recognizable languages is countable,
    
    Turing-unrecognizable languages 

(3) Reducibility (Chaps. 5.1, 5.3): 

    the definition of a reduction, 

    using reductions to prove that a
    language is not decidable/not Turing recognizable


You may expect to see problems similar to those on the last homework,
except for the problems from Chapter 7 (on NP). You will NOT be tested
on the material from Chapter 7, as we didn't cover it in class yet.

Make sure that you understand how to solve the problems on the last
homework (ignoring those from Chapter 7).