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.
Смотрите видео Undecidable Problems: Reducibility (Part 1) | What are Reductions? онлайн без регистрации, длительностью часов минут секунд в хорошем качестве. Это видео добавил пользователь lydia 10 Декабрь 2020, не забудьте поделиться им ссылкой с друзьями и знакомыми, на нашем сайте его посмотрели 47,643 раз и оно понравилось 1 тысяч людям.