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
Consider a computer program that looks like:
let i be an integer, starting at 0
while i < 10
i = i + 1
end
This program will loop 10 times and then end (halt). Now consider another program that looks like:
let i be an integer, starting at 0
let j be an integer, starting at 0
while i < 10
j = j + 1
end
This program sits in a loop always incrementing j, but it never touches i. It is an infinite loop.
The halting problem poses the question: if you are given a program, how do you determine if it will ever end? There are plenty of programs like the two here where the answer is fairly obvious just from inspection. The challenge, though, is how do you come up with a procedure that will always, 100% of the time, tell you the answer?
What makes this problem interesting is that it is actually unsolvable–and you can prove that fact! No matter how you lay out the process by which you could analyze a program there will always be some programs that your solution gets the wrong answer for. We prove this fact through contradiction, where we assume one thing and then take a bunch of logically sound steps until you arrive at a statement that is clearly false. As long as all of the logic is sound the only remaining conclusion is that the assumption was false.
As a building block here it’s useful to note that programs are themselves just data. At one point in computer science history (at a time where “computer science” was really just a branch of math) that’s a novel concept, but these days people are used to the idea since you can download a program as easily as a gif of a cat jumping into a box and falling over. Programs take in data and emit data, but since a program *is* data you can have a program that takes in a program and tells you something about it.
We take our first step in the proof by assuming the existence of a program that takes in a program and then tells you whether that program would halt or not. Perhaps we call that program HALT(x), which is to say that you pass in program x to the HALT program and it returns True or False based on whether it halts or not. Building from there we consider another program:
LIAR(x):
if HALT(x):
loop forever
otherwise:
end
This program also takes a program. It asks HALT if the program will halt, then if that program would halt then LIAR will loop forever. If the program would loop forever then LIAR immediately halts. This leads us to a problem: what happens if you call LIAR(LIAR)? You take the data representing LIAR and pass it into the LIAR program. It takes that data and asks HALT If the program will halt or not. If HALT says it halts then LIAR turns around and loops forever–a contradiction! If HALT says that LIAR will loop forever then LIAR turns around and immediately exits! No matter what HALT is guaranteed to have given the wrong answer when it was presented with this program. This means that no matter how good HALT is at figuring out if a program will loop or not it will *always* give the wrong answer for some cases.
As for why this is important, it would be way more important if things went the other way. Imagine if we could come up with a program that can tell if a program will finish. We could then write a program that amounts to:
let i be an integer, starting at 1
loop forever:
if <some mathematical conjecture is false for i>:
halt
otherwise:
keep looping
If we took this program and fed it into a working HALT function then we’d be able to immediately prove that conjecture–if HALT says the program halts then there must be some value of i that allowed the program to reach the halt statement; if HALT says the program runs forever then there’s no way to reach the halt statement.
Since no such HALT function can exist we’re left with the less useful state of knowing when we should stop looking for a solution. Since we can prove that it’s impossible to find a HALT function that means that if we can show some other problem to be equivalent we immediately know that it’s unsolvable, too. That becomes more powerful thanks to the extremely basic terms in which the computers and programs of the halting problem are defined.
Latest Answers