The halting problem is a decision problem in computability theory. It asks, given a computer program and an input, will the program terminate or will it run forever? For example, consider the following Python program:
1 2 3
It reads the input, and if it's not empty, the program will loop forever. Thus, if the input is empty, the program will terminate and the answer to this specific question is "yes, this program on the empty input will terminate", and if the input isn't empty, the program will loop forever and the answer is "no, this program on this input will not terminate".
Halting problem is perhaps the most well-known problem that has been proven to be undecidable; that is, there is no program that can solve the halting problem for general enough computer programs. It's important to specify what kind of computer programs we're talking about. In the above case, it's a Python program, but in computation theory, people often use Turing machines which are proven to be as strong as "usual computers". In 1936, Alan Turing proved that the halting problem over Turing machines is undecidable using a Turing machine; that is, no Turing machine can decide correctly (terminate and produce the correct answer) for all possible program/input pairs.
The decision problem , for Halting problem, is the set of all , for an appropriate definition of "program" (usually "Turing machine"), and where denotes some kind of encoding. A Turing machine solves if, given any input , it terminates in an accepting state if , and terminates in a rejecting state otherwise. Note that it doesn't matter whether terminates because it accepts, or because it rejects, or because it gets some kind of error; as long as it terminates and doesn't loop forever, should accept it.
Proof by contradiction
Suppose there exists a Turing machine that decides . Now consider a Turing machine defined as follows: it takes an input , runs on input , and halts if and only if rejects. That is, takes a program , runs the supposed Turing machine that decides the halting problem on the input "program , input "; based on the outcome, if it says "yes, on input halts", then it loops forever, otherwise if it says "no, on input doesn't halt", then it terminates. Note that is the encoding of a program into a suitable input (bit-string or natural number), and hence can be accepted as input by another program.
Consider what happens when receives as input. It runs on the input . We now have two cases:
- accepts. This means on input halts. But by definition of , if accepts we will enter an infinite loop, and so on input doesn't halt after all.
- rejects. This means on input doesn't halt. But by definition of , if rejects we will terminate, and so on input halts after all.
In both cases, we derive a contradiction. This contradiction happens because we assumed the existence of ; its existence allows us to create that behaves incorrectly. Thus cannot exist, and so no Turing machine can decide .
Real-world Example 
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 . If halts, then accepts, this app will not crash your phone. If loops, then 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.
Consider the following algorithm which when fed with another algorithm and an input, tells if the program halts:
- Simulate the first step of the algorithm given.
- If the program halts, return
Yes, the algorithm haltsand 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 haltand 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.
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 is reducible to problem if a solution to could be used to solve . If has been proven to be an undecidable problem, to prove that a new problem is undecidable, it is sufficient to show that a solution to could be used to decide . This yields a contradiction since it was already proven that is undecidable, and therefore, is also undecidable.
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 state Turing machine will take before halting.
If we had a function that could compute the Busy Beaver function, , 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.
If the halting problem could be solved, many other problems could be decided:
- Goldbach’s conjecture could be decided. It's easy to construct a Turing machine that tests every even natural number greater than 2 on whether it's the sum of two primes or not; if it encounters any counterexample, it immediately halts and reports that a counterexample has been found, otherwise it will run forever. If Halting problem were decidable, we could decide whether this program would halt or not, and thus give an answer to Goldbach's conjecture.
- Kolmogorov complexity would be computable.
- The Busy Beaver function would also be computable.
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.
It's important to note that Halting problem depends on what programs we're considering. The halting problem on Turing machines is undecidable. Conversely, the halting problem on finite state automata is easily decidable; all finite state automata halt. Thus it's important to specify the model.
The halting problem on usual computers is also decidable. To see this, note that there are a finite number of bits in the memory, and thus a finite number of possible configurations the computer can be in. If a program ever repeats a configuration, it will never terminate. Thus a Turing machine, with infinite memory, can simulate the program. By Pigeonhole Principle, if there are configurations that the program can be in, but we have simulated the program for steps, we must have visited a configuration twice and thus the program will never terminate. So halting problem for usual computers is also decidable using a Turing machine.
- 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/