F2021 CS 411/811 Lecture 28 (Variants of TMs, Nondeterministic Turing Machine, Chomsky Hierarchy)

In this lecture we finished up the last discussion on Turing Machines and what we can do with many different models, including the nondeterministic TM. Then I summarized everything today. Thank you everybody for the time to finish up today's lecture! Have a wonderful reading week :)!

Time Stamps
0:00 Opening
2:06 Restricted Turing Machines
8:47 Multitape Turing Machine
27:35 Time Complexity (of TM), time complexity result for Multitape TM from TM
34:59 Nondeterministic Turing Machines
46:35 Equivalence of Deterministic TMs and Nondeterministic TMs
54:14 Where are we so far? Chomsky Hierarchy.