Halting Problem
The halting problem is a critical problem in computability theory. It is the theoretical problem of determining whether a computer program will halt (produce an answer) or loop forever on a given input. This is different from looking at some specific code and seeing if the creator forgot to close the loop function in it, but rather a broader theoretical problem. Could there be a machine that can check any code with any input and determine if it halts?
The halting problem is usually taught using Turing machines. In 1936, Alan Turing proved that the halting problem is undecidable, and therefore, cannot be solved. If a solution to the halting problem existed, many open computer science problems could be solved, such as computing Kolmogorov complexity, the Busy Beaver function, and more.
One can determine the decidability of other computational problems by combining reduction techniques and the unsolvability of the halting problem.
Contents
The Halting Problem
The halting problem is the problem of determining whether a program will halt or loop forever on a given input. If a program halts, it provides an answer. When using Turing machines to think about the halting problem, halting means either accepting or rejecting an input. If a program loops forever on a given Turing machine, the Turing machine cannot provide an answer for that input.
Proof of the Undecidability of the Halting Problem
General Proof by Contradiction
Suppose that there exists a Turing machine \(P\) that can solve the halting problem. In other words, \(P\) runs something we can call the halting test. \(P\) takes another Turing machine \(M\) as its input and decides whether or not \(M\) will halt or loop forever. If \(M\) is a Turing machine that halts, the \(P(M)\) returns an accept, and if \(M\) loops forever, then \(P(M)\) rejects. (As a note, plenty of code can take other code, or even itself, as an input. For instance, a debugger written in C can debug other C code. Or a debugger might even debug itself!)
Next, suppose there is a Turing machine \(Q\) that runs \(P\), the halting test, and does the opposite. Then, it also does not just return an accept or a reject, but halts or loops itself. \(Q\) is a special Turning machine that says if some input passes the halting test, I'm going to make it loop, and if it fails the halting test, I'm going to make it halt — it's devious. If \(M\) halts, then \(P(M)\) accepts, but \(Q\) runs \(P(M)\) and loops forever, \(Q(P(M))\) loops. If \(M\) is a Turing machine that loops, then \(P(M)\) would return a reject, but \(Q(P(M))\) would halt.
However, a contradiction occurs when we run \(Q\) on \(Q\). Remember that \(Q\) runs \(P\), so this is asking for \(Q(P(Q))\), or to run the halting test on \(Q\) and then running \(Q\) on that result. If we run \(Q(Q)\) for an original input of \(M\), then \(Q(Q)\) is \(Q(P(Q(P(M))))\). There are four steps here. First, the halting test, \(P\), runs on \(M\). Second, \(Q\) reverses that, and then loops or halts. Third, the halting test \(P\) runs on that result, determining if \(Q\) passes the halting test. Then, finally, \(Q\) runs on that result, reversing that and either loops or halts the whole thing. Let’s play this out:
If \(M\) is a Turing machine that halts, then \(P(M)\) accepts. In defiance, \(Q(P(M))\) would loop, so \(P(Q(P(M)))\) would reject. Here the halting test, \(P\), says that \(Q\) does not pass the halting test. But we've got one more step, to run \(Q\) on that result, which halts. The halting test, \(P\), rejected \(Q\), but \(Q\) halted. A contradiction.
Similarly, if \(M\) loops, then \(P(M)\) rejects, \(Q(P(M))\) halts, and \(P(Q(P(M)))\) accepts. The halting test, \(P\), says that \(Q\) passes the halting test. But \(Q\) then acts on that, looping it, and creating a contradiction.
Some people aren't clear on how this is a contradiction, so let’s look at this in terms of real-world Turing machines.
Real-world Example^{[1]}
One way to visualize this is to think of apps on a phone. Apps are types of Turing machines. Sometimes apps crash your phone because they get caught in a loop and do not halt. Let’s supposes a clever team releases an app to check for this. This app, the Checker app can solve the Halting problem.
The Checker app checks some app \(M\). If \(M\) halts, then \(Checker(M)\) accepts, this app will not crash your phone. If \(M\) loops, then \(Checker(M)\) rejects, this app will crash your phone.
Suppose a diabolical computer scientist decides to create a App called Paradox. This app will effectively reverse the Checker app. And because the Checker app works, this one works too, it's really simple: - It turns on the Checker app, and inputs itself into the Checker app. - If the Checker returns an accept, then the Paradox app forces the phone to loop and crash. - If the Checker app returns a reject, then the Paradox app will halt, meaning that it doesn't deserve that rejection, it's a safe app and doesn't crash your phone.
Effectively to run Paradox means to run Paradox(Checker(Paradox)). If Paradox is a bad app, that crashes your phone, Checker will reject it, and Paradox will return a halt. Paradox(Checker(Paradox)) = Paradox(Checker(loop)) = Paradox(reject) = Halt If Paradox is a good app, that halts, then the Checker app will accept it, and Paradox will crash your phone. Paradox(Checker(Paradox)) = Paradox(Checker(halt)) = Paradox(accept) = Loop So the Checker app says Paradox is good, and then Paradox crashes you, or the Checker app says Paradox is bad and Paradox halts. This is a contradiction.
Now some people still don't see this as a contradiction. To which we'd point out that this is a supertask, which we know to be impossible in the real world. A supertask is an uncountable series of infinite tasks, examples include Thompson's lamp or zeno's paradox. We know that running Paradox actually means Paradox(Checker(Paradox)) which means Paradox(Checker(Paradox(Checker(Paradox)))) which means Paradox(Checker(Paradox(Checker(Paradox(Checker(Paradox)))))) and so on. Either the Paradox app does crash your phone or it doesn't. Those are the only two possibilities. But this series of infinite checks switch back and forth between loop and halt, with no result.
- Simulate the first step of the algorithm given.
- If the program halts, return
Yes, the algorithm halts
and terminate. - If it does not halt (as of yet), capture a snapshot of the simulation.
- Compare the snapshot with the previous snapshots. If it is the same as one of the snapshots previously taken, return
No, the algorithm does not halt
and terminate. - Simulate the next step.
- Go to 2.
Now which of the following is true?
A. The construction is correct; The halting problem is only undecidable for computers with infinite memory
B. The construction is wrong; Snapshots of a simulation cannot be captured by a computer program
C. The construction is wrong; The simulation might run into a previously encountered snapshot but still halt.
D. The construction is correct; It solves the halting problem in general for any computer
E. The construction is wrong; The described construction cannot be written as a finite program in a proper computer.
Note: The construction refers to the algorithm described, which is the one that is supposed to solve the halting problem.
Reductions and Consequences
A typical way to prove that a problem is undecidable is to use reduction. If a problem can be reduced to the halting problem, it is undecidable.
A problem \(A\) is reducible to problem \(B\) if a solution to \(B\) could be used to solve \(A\). If \(A\) has been proven to be an undecidable problem, to prove that a new problem \(B\) is undecidable, it is sufficient to show that a solution to \(B\) could be used to decide \(A\). This yields a contradiction since it was already proven that \(A\) is undecidable, and therefore, \(B\) is also undecidable.
If the halting problem could be solved, many other problems could be decided. For example, Goldbach’s conjecture could be proved or disproved, Kolmogorov complexity would be computable, and the Busy Beaver problem could be solved. More generally, the undecidability of the halting problem proves that there cannot be an algorithm that decides whether a given statement about the natural numbers is true or not.If we could solve the Busy Beaver problem, we could solve the halting problem.
The Busy Beaver problem is the problem of determining the maximum number of steps an \(n\) state Turing machine will take before halting.
If we had a function that could compute the Busy Beaver function, \(BB(n)\), we could know the maximum number of steps any Turing machine will take before halting. This means that we could know how long we would have to wait for a machine to halt, and ultimately, we will know if the machine will halt. In other words, if we had a way to compute the Busy Beaver function, we could use it to solve the halting problem. Since the halting problem is uncomputable, it follows that the Busy Beaver function is uncomputable.
It is useful to know about the kinds of problems that are undecidable because it helps us to understand the limitations of our computation models.
References
- Husfeldt, T. The-Freeze-App-Does-Not-Exist. Retrieved April, 24 2016, from https://thorehusfeldt.net/2012/06/25/the-freeze-app-does-not-exist/