Fri 8 Nov: Scene-Set for the Halting Problem

1. Class is Asynchronous online today
2. What is Undecidable and why do we care? Rambling scene-set
3. Watch a Youtube video about the halting problem. e.g. This one
4. Watch a Youtube video about related questions. E.g. one about The busy beaver problem

Mon 11 Nov: More about Models of Computation

1. Review of Assign 7 and Test 4
2. Chomsky's hierarchy revisited
3. Printer TMs

Wed 13 Nov: The Self-Denying and Acceptance Problems

1. Assign 8 due Tuesday 11/19
2. Language S_tm is not r.e.
3. Preamble
4. Proof that A_tm is not recursive
5. another proof

Fri 15 Nov: Diagonalization and Countable/Uncountable

1. Diagonalization
2. Take-away: Set of programs is countable but set of languages is uncountable. Details
3. Review of S_tm and A_tm

Mon 18 Nov: The Halting Problem and Reductions

1. The Halting Problem is undecidable
2. Summary: here
3. Reductions. Take away: If Problem A reduces to Problem B and B is easy, then so is A.
4. Quiz 5 ON CANVAS asynchronous

Wed 20 Nov: More on Reductions

1. Assign 9 is due Noon Tuesday 12/3
2. Review of Assign 8
3. Reductions: Definitions and more slides
4. Review of Quiz 5
5. Practice 23
6. Test 5 is multiple-choice

Fri 22 Nov: TEST 5