The Halting Problem: The Unsolvable Problem

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 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 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 In fact there are Queue the halting problem 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 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 unsolvable using a formal proof by contradiction We won't go through the formal proof, but here's the idea of the proof 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 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 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 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 then D never halts So that's our machine D 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 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 Even though H said D will halt This means H is wrong 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 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 H is wrong again But remember in the beginning 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 Then H can be wrong This contradicts our initial assumption that H is always right 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 supercomputer will be able to solve the halting problem Asking a supercomputer to solve the problem would be like asking the supercomputer to come up with a triangle with four sides Logically, it makes no sense So yeah, the halting problem is pretty significant And mind-blowing when you really think about it It's also just incredible how mathematicians and computer scientists have rigorously proved that there are problems that can never be algorithmically solved So the next time someone tells you that computers will one day solve everything just tell them about the halting problem

Channel: lydia

Views: 135,884

Keywords: halting problem, alan turing, turing machine, theory of computation, models of computation

Id: VyHbd6sx5Po

Length: 4min 14sec (254 seconds)

Published: Wed Apr 22 2020