Undecidable Problems: Reducibility (Part 1) | What are Reductions?

A reduction is when we view a problem as another, and by solving the new problem, we solve our initial problem. For example, we may reduce our problem of getting around a new city, to the problem of finding a map of the city; by finding a map, we solve our initial problem of finding our way. We use reductions in computer science to prove that some problems are undecidable or unsolvable. Reductions can be a little tricky to understand at first, so this video provides some additional ways to understand reductions and how we can use reductions to show that a problem is undecidable. If you do reference Michael Sipser's Introduction to the Theory of Computation textbook, then the Truth Problem is actually A_TM (defined in chapter 4.2 on page 174 in the 2nd edition). ____________________ Additional resources: https://youtu.be/1KvYcoTeRbI - My next video (part 2 of reductions) that show how exactly we can reduce the Halting Problem to the Truth Problem. https://youtu.be/VyHbd6sx5Po - My previous video on the Halting Problem, a well known undecidable problem. Michael Sipser. 2006. Introduction to the Theory of Computation (2nd. ed.). International Thomson Publishing. - The main source of my Theory of Computation knowledge (a textbook). Read Chapter 5: Reducibility to learn more about reducibility and how a formal proof would look like. _____________________ And as always, this video project could not have been done without the support and guidance of Audrey St. John at Mount Holyoke College, a truly incredible professor-mentor-human.