Lecture 6: TM Variants, Church-Turing Thesis

Om kurset

Description: Quickly reviewed last lecture. Showed that various TM variants are all equivalent to the single-tape model. Discussed the Church-Turing Thesis: Turing machines are equivalent to “algorithms” and model-independence. Introduced notation for encoding objects and describing TMs. Instructor: Prof. Michael Sipser