Lecture 9: Reducibility

Name: Lecture 9: Reducibility
Uploaded: 2021-10-06T12:46:14Z
Duration: 1 h 16 min 37 s
Description: Description: Quickly reviewed last lecture. Discussed the reducibility method to prove undecidability and T-unrecognizability. Defined mapping reducibility as a type of reducibility. Showed that \(E_\bf{TM}\) is undecidable and T-unrecognizable; \(EQ_\bf{TM}\) and \(\overline{EQ_\bf{TM}}\) are T-unrecognizable. Instructor: Prof. Michael Sipser

1:16:37

Up Next

Lecture 10: Computation History Method

Continue

Description: Quickly reviewed last lecture. Discussed the reducibility method to prove undecidability and T-unrecognizability. Defined mapping reducibility as a type of reducibility. Showed that \(E_\bf{TM}\) is undecidable and T-unrecognizable; \(EQ_\bf{TM}\) and \(\overline{EQ_\bf{TM}}\) are T-unrecognizable.

Instructor: Prof. Michael Sipser