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

DISCLAIMER: I have no knowledge of this topic and my (very) dumbed down explanation is completely based off of what i got from other comments. PLEASE tell me if I’m wrong, my interest is piqued and I wanna know this too.

Essentially: There is no possible program that can accurately tell (in all situations) what programs run infinitely and what programs eventually finish running.

Example:

Program 1: runs infinitely
x = 0
Repeat until x == -2
x = x + 2

print x

This program runs infinitely and will never give an output

Program 2: eventually stops
x = 0
Repeat until x == 20
x = x + 2

print x

This program stops eventually and will give an output of 20

Let’s say that these were then named # and $, and you don’t know which is which.
The halting problem is the idea/fact that there is no possible program that can accurately tell (in all situations) which program is 1 and which is 2. There is no possible program that can accurately tell (in all situations) what programs run infinitely and what programs eventually finish running.

This is the basic principle.

The proof is this:

We make a program, “Halt”. “Halt” is used on another program. “Halt” gives me “yes” if the program finishes eventually, and “no” if the program runs forever.

We make another program, called “Liar”. “Liar” will run infinitely if given the input “yes” and will stop operating if given the input “no”.

For simplicity’s sake, we’ll assume right now “Liar” is running a program that stops eventually. We run “Halt” on “Liar”. “Halt” gives the input “yes”, because “Liar” will eventually stop running. “Liar” receives the input “yes” , which will start the infinitely running program. In this case, “Halt” has told us that the program will stop running when it won’t. It is inaccurate. If you run “Halt” on “Liar” now, it will give the output “no”. “Liar” will receive this as an input and will stop operating, finishing the program. “Halt” is also inaccurate in this case.

The idea is, no matter what happens, “Halt” will not be accurate if run on the program, or programs like, “Liar”. So “Halt” being 100% accurate in figuring out whether a program will stop or not is impossible, because there is a specific program (“Liar”) that will render “Halt” completely inaccurate.