The Halting Problem: The Unsolvable Problem
lydia
https://www.youtube.com/watch?v=VyHbd6sx5Po

Transkript (automatisch erstellt)

0:00 Computers have helped us solve and achieve many things They run complex algorithms fast and allow us to analyze incredibly large data sets to answer our questions
0:11 Save and access our work from anywhere and make and watch videos So as our computers become faster and more powerful, is there ever a limit to what computers can do
0:23 As in, is there anything that even the most powerful supercomputer with an infinite amount of memory and processing power will never be able to solve
0:35 In fact there are Queue the halting problem
0:40 The halting problem asks, is it possible to write a program that determines whether another program halts? By halt we mean whether it ultimately stops and exits
0:52 A program that never halts is one that has an infinite loop for example Alan Turing both proposed and proved that the halting problem is in fact
1:01 unsolvable using a formal proof by contradiction We won't go through the formal proof, but here's the idea of the proof
1:10 We assume that we do in fact have a program that always correctly determines whether another program halts Let's call this magical program H
1:20 H takes in another program as input and after scanning through the program it tells us if the program will halt or if the program will run forever
1:31 Now let's create a bigger machine D that encompasses H D is designed such that for every input it gets it gives it to H
1:42 and whatever H says, it does the opposite So if H says the program runs forever, then D will halt and if H says that the program halts
1:53 then D never halts So that's our machine D
1:59 The contradiction arises when we give machine D its own program So when D takes in its own program as input. It passes it to H and H decides whether D will halt
2:13 Let's say H determines that D will halt but because D is designed to do the opposite of what H says Then D ends up running forever
2:23 Even though H said D will halt This means H is wrong
2:30 but we assumed in the beginning that H is always right So let's try again D takes in its own program and process it to H
2:40 but this time H says D does not halt and runs forever And again, because D is designed to do the opposite of what H says, D halts
2:51 H is wrong again But remember in the beginning
2:56 we assume that this magical program H always correctly tells us if a program will halt exists But our experiment with D just showed that if H existed and we built D using H
3:09 Then H can be wrong This contradicts our initial assumption that H is always right
3:17 Therefore a program such as H that correctly determines if another program will halt cannot exist So that's the halting problem and again not even the most powerful
3:31 supercomputer will be able to solve the halting problem Asking a supercomputer to solve the problem would be like asking
3:39 the supercomputer to come up with a triangle with four sides Logically, it makes no sense
3:47 So yeah, the halting problem is pretty significant And mind-blowing when you really think about it
3:53 It's also just incredible how mathematicians and computer scientists have rigorously proved that there are problems that can never be algorithmically solved
4:03 So the next time someone tells you that computers will one day solve everything just tell them about the halting problem