Lecture 14, Nov. 8, 2001.

Done in class:

(1) Variants of Turing Machines: 

    two-way infinite tape;
    
    multiple tapes;

    nondeterministic.

    The equivalence of these variants and our definition of  TM.

(2) The Church-Turing Thesis.

(3) Decidable Problems:

    Problems and the corresponding languages

    Decidable languages

Assigned reading: Sec. 3.2-3.3, 4.1.