Lecture 6: TM Variants, Church-Turing Thesis

Name: Lecture 6: TM Variants, Church-Turing Thesis
Uploaded: 2021-10-06T12:44:38Z
Duration: 1 h 14 min 49 s
Description: 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

1:14:49

Up Next

Lecture 7: Decision Problems for Automata and Grammars

Continue

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