Mon 21 Oct: Turing Machines

1. Assign 6 due Monday 10/28
2. Review of Test 3
3. Scene-set: What's in the rest of the course.
4. Review of Chomsky Hierarchy
5. Turing machines: Overview | Example for 0^n1^n

Wed 23 Oct: More TMs

1. Slides
2. Example for equal 0s and 1s
3. Practice 17 and Practice 18

Fri 25 Oct: Transducers

1. A transducer computes a function by leaving answer on tape.
2. Binary vs unary
3. Example: Doubler | Another Example: Exponentiation
4. Church's thesis: There is TM for problem if and only if there is an algorithm

Mon 28 Oct: TM Variations

1. Assign 7 is due Monday 11/4
2. Practice 19
3. Changing TMs: Emulations show TM power unchanged.
4. Nondeterminism doesn't change the languages (can search computation tree)

Wed 30 Oct: Recursive and r.e. languages

1. Definitions and Theorems
2. Quiz 4

Fri 1 Nov: Recursive and r.e. languages

1. Review of Assign 6 and Quiz 4
2. Closure properties of TM languages Sometimes need parallelism
3. Practice 20 and Practice 21

Mon 4 Nov: Decision Problems

1. Decision problems and some comments.
2. Practice 22
3. Revision
4. Test 4 will be on (a) Construct a TM, (b) Read a TM or transducer, (c) modifications of TMs, (d) Church's thesis, (e) definition and properties of recursive and r.e. languages

Wed 6 Nov: TEST 4