Week 9
- Dates: 5/29/23 - 6/3/23. No class on Monday in observance of Memorial Day. Project is due this week.
Lecture and Discussion podcast
See videos on podcast.ucsd.edu
(Video) Reducing A_TM to HALT_TM
(Video) Mapping Reducation Applications
(Video) Mapping Reduction Strategy
(Video) ETM is undecidable, part 1
(Video) Reduce ATM to ETM complement
(Video) Mapping reduction steps
(Video) EQTM
(Video) Complexity motivation
(Video) Complexity first definitions
(Video) Complexity classes examples
(Video) Complexity of ADFA