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
In computer programs, some run through and end, and others may continue forever.
Imagine you want to make a different computer program, that could determine if any computer program will either stop at a point in time (halt), or continue forever (not halt).
The methodology of proving it is a bit difficult, but in short, **IF** you *could* make such a program (I’ll call it **P**) that correctly determines whether ANY program halts or not, you could make a different program (that has **P** as a part of it), that would trick **P**. This would be a contradiction, as **P** was supposed to predict ANY program, and this one doesn’t.
Therefore, it is IMPOSSIBLE to create a program **P** that correctly predicts if **any given program** either halts or not.
Latest Answers