To show that the Truth Problem is undecidable, we reduce the Halting Problem to the Truth Problem. In this video, we show the complete reduction. Also, if you use 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).
Here is the proof and reduction in writing (I use 'machine' below, but 'program' means the same thing):
Truth Problem: "Can we build a machine that determines if another machine returns true?"
Halting Problem: "Can we build a machine that determines if another machine halts?"
***** PROOF *****
Suppose T decides the Truth Problem. We define H as follows:
Let H = "On input ❮M❯, where M is a machine:
1. Run T on input ❮M❯.
2. If T returns true, return true and exit. If T returns false, continue to step 3.
3. Construct M’ as follows:
M’ = “On input y:
1. Run machine M on y.
2. If M returns true, return false and exit. If M returns false, return true and exit.”
4. Run T on ❮M'❯ and return what T returns.
If T decides the Truth Problem, then H decides the Halting Problem. But this contradicts the fact that the Halting Problem is undecidable. Therefore, the Truth Problem is undecidable.
***** END PROOF *****
Note: In step 3 of the proof above, I said in the video that we change input ❮M❯. However, in a formal proof, we simply construct a new machine that returns the opposite of what M returns.
To summarize reductions:
1. We can use reductions to show that a problem is unsolvable or undecidable.
2. If problem A reduces to problem B, and problem A is undecidable, then problem B must be undecidable. However, if problem B is decidable, then problem A is decidable.
3. To prove that a problem is unsolvable through a reduction:
i. Find another unsolvable problem A.
ii. Claim that you can reduce problem A to the problem you are trying to show is unsolvable.
iii. Show the complete reduction.
iv. State that the reduction results in a contradiction, since the problem A cannot be solved.
____________________
Additional resources:
• Undecidable Problems: ...
- Previous video (part 1) on reductions.
• 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
