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 is, roughly, this: “Can we make a computer program that can determine with 100% accuracy whether other programs will halt?”
It turns out the answer is “No.”
**Why it’s important** is this: it turns out that a lot of other problems can be turned into the halting problem.
For example: “is there a 100% reliable automated way to tell if two chunks of computer code do the same thing?”
It turns out if you had a way to do that, you could solve the halting problem. And since we can’t solve the halting problem, we can’t find a way to do that.
Or: “If I give you a set of square tiles with notches on the edges, is there a 100% reliable way to tell if those tiles can be made into a jigsaw that fills a whole infinite plane?”The answer is “No”, since it turns out it’s possible to encode any computer program as a set of tiles, which will fill the plane if and only if the program never halts.
Or: “Is there a way to tell, 100%, whether a polynomial has integer solutions?” Again, it turns out there are some really clever ways to turn computer programs into polynomials, and the ones that halt have integer solutions.
And so on. The “halting problem” turns out to be a bit special, because lots of problems can be seen as a restatement of the halting problem, and the fact that the latter can’t be solved means that the original problem also can’t be solved.
**The proof** goes like this: imagine we had a computer program that could check if other computer programs would halt. Then we could always feed that computer program to itself. Since our “halting problem solution” is 100% reliable, it must halt, so when we feed it itself, it will say “Yes”.
But then, we can make a slightly modified version of the program: instead of saying “No” or “Yes”, it will say “No” or go into an infinite loop (ie, never halt). This is trivial to do, if we can solve the halting problem, we can certainly make this less useful version. Now we feed THAT to itself.
It immediately delegates to the original halting problem “solver”, gets and answer, and then either halts (because the answer was “No”) or not (because the answer was “Yes”).
* If it halts, it says “No!”, which means the original halting problem solver said “No, it never halts” when shown a program that does, in fact, halt. So it’s actually given the wrong answer, and wasn’t 100% reliable. Our so-called “100% reliable solution” to the halting problem was fake.
* If it doesn’t halt, it’s because the halting problem solver looked at the code an said “Yes, this halts!”, and then our program went into an infinite loop. Again, that means the original halting problem “solver” has given the wrong answer, and is not 100% reliable.
Either way, it turns out our supposed solution to the halting problem sometimes gives wrong answers. Which means there’s no such thing as a halting problem solver.
Latest Answers