I watched videos and read about it but I still don’t understand why is important and proof of it. Can you please explain me what it is?
Thanks
In: 60
The Halting Problem takes a program (and it’s input) as it’s input, and tells you whether or not that program (run on the provided input) will eventually stop (halt) or if it will keep running forever (loop). This is what’s called a *decision problem*, meaning that it takes an input and gives you a yes or no answer as it’s output, but that’s less important.
You can just thing of the problem as of a computer program. So solving the Halting Problem really means writing a computer program that will tell you whether or not a program that it gets as input will halt or loop. This part is important, and I feel like it trips many people up: a program is really just text, so it can be an input of another program.
What’s important about the Halting Problem is that it’s undecidable, which means that it’s impossible to write a program that will tell you wether any program will loop or halt. And when I say impossible, I don’t mean we haven’t came up with it yet. I mean we have proven that it’s impossible. Now that on it’s own isn’t that interesting, there are actually many problems that are undecidable, but the Halting Problem is an interesting intro to this, because it’s relatively simple, the sketch of the proof is not that complicated, and, most importantly, it’s a program that we would really like to have (because it would make writing safe code much easier).
The full proof is beyond the scope of this subreddit, there are many videos on it (don’t feel discouraged if you don’t get it on your first try, it gets a little confusing, that’s just how high level math is). But here’s the idea:
Imagine that we can solve the Halting Problem. That means there is some program that will tell us wether a given program will loop or halt, for any program. We’ll call this program the Oracle (this is actually a technical term for this kind of program, which I just find funny). Now, using this oracle, let’s make another program that we’ll call Smith, which will take another program as it’s input, and work like this:
1. It will check if the input program (A), loops or halts, using the Oracle.
2. If A halts, then Smith will loop forever.
3. If A loops, then Smith will halt.
Now this might sound strange, but it is a valid program that you could write on your computer – if you had the oracle.
But here’s the thing. What happens if we give Smith itself as it’s input? Well, let’s say that the Oracle says it loops. But then Smith will halt! What if the Oracle says that it halts? Well, then Smith will loop! The Oracle was wrong in both cases! Which means, that the Oracle can’t exist. This is called a proof by contradiction: we first assumed that something is true, then we found some example that contradicts our initial assumption, which means it must be false. This proof is also very simplified, since it doesn’t take into account that the program also has inputs. But this is the basic idea.
Latest Answers