Week 6
- Dates: 5/8/23 - 5/13/23
Lecture and Discussion podcast
See videos on podcast.ucsd.edu
(Video) TM Intro Recap
(Video) TM Accept, Reject, Loop
(Video) TM Recognize vs Decide
(Video) TM Implementation-level and formal definition Example 1
(Video) TM Implementation-level and formal definition Example 2
(Video) TM Implementation-level and formal definition Example 3
(Video) Recognizable and Decidable languages
(Video) Regular languages are decidable
(Video) Equally expressive models
(Video) TM vs May Stay machines
(Video) Multitape TMs
(Video) Nondeterministic TMS
(Video) Church-Turing thesis
(Video) High-level descriptions of TMs
(Video) Closure of class of recognizable languages under union