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:
• Undecidable Problems: ...
- My next video (part 2 of reductions) that show how exactly we can reduce the Halting Problem to the Truth Problem.
• The Halting Problem: T...
- 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.
9 дек 2020
