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.
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.
I’m going to leave the mathematics mostly behind and take you on a descriptive journey.
You leave your house and go to the grocery store. Just before you enter someone walks in in front of you. Where are they going to go?
Do they turn left? Right? Do they freeze and grab a basket? Are they getting a phone call and they stop to answer the phone? How fast are they going to walk?
The scope of what they *could* do at any point is huge, and the Halting Problem basically posits that there will be no simpler way to predict what they do than to have the real live human do whatever they’re going to do, live, right in front of you. It’s easier for the universe to manufacture that exact human on that exact day than to simulate, with certainty, what the person will do.
Let’s move to computers. The Halting Problem says that there’s no better way to predict when a program will end (halt) than just running the program to see what it actually does.
This matters because it means (here comes math again) operating systems can’t predict the behavior of programs running on them in *polynomial time*–basically there’s no straightforward equation to tell you how much longer to wait for any arbitrary process to finish, become responsive, take free resources, etc… that’s better than than just letting it run.
So the best we *can* do is spinning beach balls and task managers that allow you to kill programs and frustrating progress bars that never seen to know how long something will really take. Because math says nothing will be better than letting the thing actually happen and seeing how long it takes.
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.
The Halting Problem takes a program (and it’s input) as it’s input, and tells you whether or not that program (run on the provided input) will eventually stop (halt) or if it will keep running forever (loop). This is what’s called a *decision problem*, meaning that it takes an input and gives you a yes or no answer as it’s output, but that’s less important.
You can just thing of the problem as of a computer program. So solving the Halting Problem really means writing a computer program that will tell you whether or not a program that it gets as input will halt or loop. This part is important, and I feel like it trips many people up: a program is really just text, so it can be an input of another program.
What’s important about the Halting Problem is that it’s undecidable, which means that it’s impossible to write a program that will tell you wether any program will loop or halt. And when I say impossible, I don’t mean we haven’t came up with it yet. I mean we have proven that it’s impossible. Now that on it’s own isn’t that interesting, there are actually many problems that are undecidable, but the Halting Problem is an interesting intro to this, because it’s relatively simple, the sketch of the proof is not that complicated, and, most importantly, it’s a program that we would really like to have (because it would make writing safe code much easier).
The full proof is beyond the scope of this subreddit, there are many videos on it (don’t feel discouraged if you don’t get it on your first try, it gets a little confusing, that’s just how high level math is). But here’s the idea:
Imagine that we can solve the Halting Problem. That means there is some program that will tell us wether a given program will loop or halt, for any program. We’ll call this program the Oracle (this is actually a technical term for this kind of program, which I just find funny). Now, using this oracle, let’s make another program that we’ll call Smith, which will take another program as it’s input, and work like this:
1. It will check if the input program (A), loops or halts, using the Oracle.
2. If A halts, then Smith will loop forever.
3. If A loops, then Smith will halt.
Now this might sound strange, but it is a valid program that you could write on your computer – if you had the oracle.
But here’s the thing. What happens if we give Smith itself as it’s input? Well, let’s say that the Oracle says it loops. But then Smith will halt! What if the Oracle says that it halts? Well, then Smith will loop! The Oracle was wrong in both cases! Which means, that the Oracle can’t exist. This is called a proof by contradiction: we first assumed that something is true, then we found some example that contradicts our initial assumption, which means it must be false. This proof is also very simplified, since it doesn’t take into account that the program also has inputs. But this is the basic idea.
There are several good descriptions of the proof’s of the Halting Problem.
The IMPORTANCE of the halting problem is that it is basically the Computer Science Version Of [Math] Goedel’s Incompleteness theorem.
It is a proof that there are things that are not compute-able. They ARE one way or another, but they cant be computed.
It says, “there are things which can’t be solved”. Not “which are hard to solve” but “with all the computing power that is, and ever will be, for all the time in the universe, cannot be solved”. Which is kinda neat.
It’s really a mathematics problem. At one the turn of the 20th Century, there was a famous list of outstanding questions in mathematics. Hilbert wanted to know if mathematics was complete — did all true statements have proofs. Kurt Godel disproved that by constructing a self-referential statement which claimed it had no proof. If it was true it has no proff. If it was false, it did have a proof. Mathematics was wither incomplete or inconsistant.
The fall back question was could we find all true proofs. Alan Turing imagines a machine that could solve problems — a Turing machine. He described how it worked and designed a program that tried to prove statements. He showed that, given an arbitrary statements, there was no way of knowing if the program would ever find a solution. This is the Halting Problem.
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.
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.
It basically goes down to a paradox like this:
“The next sentence is true.
The previous sentence is a lie.”
If the first sentence is true then it’s also a lie.
If the first sentence is a lie, then the second sentence cannot be true and yet it’s true.
The halting paradox is something very similar but in a more complicated story.
Latest Answers