MIT
Lecture 9: Reducibility
Data Science, Analytics & Computer TechnologyComputer ScienceScience & MathMathematicsEngineering
Om kurset
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