Hi guys, Welcome to the Advanced Video Search Engine, and you are watching Undecidable Problems: Reducibility (Part 2) | A Sample Reduction. That video is uploaded by lydia at 2020-12-10T04:36:12-08:00. We are promoting this video only for entertainment and educational purpose only. So, I hope you like & enjoy it. [1KvYcoTeRbI]
| Name | Undecidable Problems: Reducibility (Part 2) | A Sample Reduction |
| Video Uploader | Video From lydia |
| Upload Date | This Video Uploaded At 10-12-2020 12:36:12 |
| Video Discription | 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: https://youtu.be/U4yGQp5aCTM - Previous video (part 1) on reductions. 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. 1KvYcoTeRbI |
| Category | Education |
| Tags | Education Download MP4 | Education Download MP3 | Education Download MP4 360p | Education Download MP4 480p | Education Download MP4 720p | Education Download MP4 1080p |
