Halting problem is a famous problem in computer science. The problem is simply we want to prove and know whether a computer program will be halted or terminated or it will continue running forever.

Alan Turing proved that there is known solution for the halting problem. It is impossible to determine whether a program with an input will be terminated or it will run forever.

The proof used contradiction method to prove its unsolvability.

The Proof

Assume that we have a program P(X) that takes X as an input

The output of the program will be 0 or 1 where 1 indicates the program will halt and 0 indicates the program will continue forever

Assume we have another program Q that takes program P as its input, Q(P(X)) that output 0 or 1 where 1 indicates P(X) will run forever and 0 indicates it will halt

Assume we pass the program Q to itself (Recursion) as its parameter Q(Q)

Now, we have 2 cases

Case 1: If Q(Q) halts, then P(X) returns 1, which means Q(P(X)) will return 1 which indicates P(X) runs forever. Contradiction

Case 2: If Q(Q) runs forever, then P(X) returns 0, which means Q(P(X)) will return 0 which indicates P(X) halts. Contradiction