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:
• Undecidable Problems: Reducibility (P...
My next video (part 2 of reductions) that show how exactly we can reduce the Halting Problem to the Truth Problem.
• The Halting Problem: The Unsolvable P...
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.
Watch video Undecidable Problems: Reducibility (Part 1) | What are Reductions? online without registration, duration hours minute second in high quality. This video was added by user lydia 10 December 2020, don't forget to share it with your friends and acquaintances, it has been viewed on our site 47,64 once and liked it 1 thousand people.