Eli5 Halting Problem

Question

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

Answer 1

Consider what happens to your computer when you try to overload its poor little brain. Everything slows down, the cursor turns into something spinning, and eventually you get a popup that says ‘I’m broken, want me to stop?’ Sometimes you want it to because it is just not working, but sometimes it just needs a little more time to finish what it’s doing. It would be great if there was a way to tell which is which.

That is the halting problem; can you tell when a computer will ever finish what it’s doing?

​

The proof:

Imagine that you have written a program that solves the halting problem (I’ll call this the halting program). You can run the program, feed it the program and input of any arbitrary program, and it will output ‘yes’ if the program will ever finish, or ‘no’ if the program will never finish.

Now, you also write a second program (I’ll call this the no program). If you tell this program ‘no’ it does nothing. If you tell this program ‘yes’, then it will do an infinite loop of ’10:PRINT, “Hello” 20:GOTO 10′, and will never finish.

Now you write a third program (I’ll call this the liar program) that calls on the first two programs. First, it runs the halting program, then feeds the output of that into the no program.

Now, you run the liar program, and put its code as its input. This code will first run through the halting program, which will output ‘yes’ or ‘no’. If the halting program outputs ‘no’, then the no program will do nothing, and the liar program will finish its calculations. But, if the liar program finishes its calculations then it has halted, and the halting program should have said ‘yes’. But if the halting program says ‘yes’, then the no program should run forever, so the liar program doesn’t halt, and the halting program should have said ‘no’

Whatever the halting program calculates, the no program makes that output incorrect. Since it is trivially easy to show that the no program exists, that means the halting program can’t exist, and therefore there is no way to tell if a computer will ever finish what it is doing that is always correct.