Turing Machines
Overview
The next set of lectures introduces another, even more powerful, way to
represent languages, namely by giving Turing machines
that “recognize” or “decide” these languages.
We will see that these are — in a significant sense — at least
as powerful as any “real” computer.
Lecture #19: Introduction to Turing Machines
Required Reading
Lecture Presentation
Lecture #20: Designing a Turing Machine
Required Reading
Lecture Presentation
Tutorial Exercise #14: Introduction to Turing Machines
Lecture #21: Multi-Tape Turing Machines
Required Reading
Lecture Presentation
Tutorial Exercise #15: Multi-Tape Turing Machines
Lecture #22: Nondeterministic Turing Machines
Required Reading
Lecture Presentation
Tutorial Exercise #16: Variants of Turing Machines — and
Simulations
Lecture #23: Universal Turing Machines
Required Reading
Lecture Presentation
Lecture #24: The Church-Turing Thesis
Required Reading
Lecture Presentation
