This Will Help You to Understand the Halting problem

One of the most fascinating ideas in all of Computer Science, Philosophy, and Mathematics in general, is Halting Problem. But understanding it is not difficult at all.

When the mechanical machines became widespread in solving the difficult problems, the question was raised whether there is a way to find if there exist some problems which computer machine will never be able to solve regardless of how advance, fast or intelligent it may be. Every computer follows an algorithm — program that tells it what to do — to produce an output, so in order to know if there are certain problems (also algorithms), used as the inputs, that may not produce any output we need to have a program which would tell us exactly that. A more precise way of defining it is as follows:

“Can we find a program that can predict whether any other program and its input will halt or run forever?”

So to find that program which could give us the definitive answer as to whether the given problem is solve-able or not, put another way; would it take computer some finite time to run it, or will it never halt and run forever. We can see the parallel idea in mathematics by David Hilbert who proposed a question: is mathematics decidable? That is to say; is there a way to test if any mathematical statement is true or not, or is it possible that we might never be able to know the yes or no answer for some mathematical statements.

Turing’s proof of the Halting problem by contradiction.

There is a popular way to prove a mathematical statement which is proof by contradiction. It is to prove (or disprove) a mathematical statement by establishing that its opposite is false (or true). Turing’s ingenious solution makes use of this mathematical model, as he establishes that there are indeed some programs for which it is impossible to know whether they halt or run forever.

Proof by contradiction.

To start off, let us assume that there is exists such a program which gives us a definitive answer as to whether a certain program halts or run forever. For the sake of simplicity, let us call this program X. So any program about which we want to know if it halts or not is given as an input to X, if X produces yes in the output, that means our program halts, otherwise it will not. Now imagine another program, Y, which does the opposite of X. So, if X gives yes, then Y will run forever and vice versa.

Now this is where it gets interesting, now we use Y as an input to X. So, if Y halts then X returns yes, indicating that the input program halts, and now Y, which does the opposite of X, runs forever. But we have already assumed that the Y halts, so this is a clear contradiction. This goes to show that there cannot be a computer program which could tell us whether every single program will halt or run forever.

The halting problem impact

The philosophical impact of halting is hard to undermine. We are naturally wired to believe that there is always a yes and no answer to every problem proposed, and, philosophically speaking, there was no reason to not believe that. It is also important to point out that halting problem is not a problem of there not being a computer with nearly infinite processing speed and infinite time available to run the program. Even if we there was such a machine that had infinite memory and processing power, there are always going to be programs for which we wouldn’t be able to know whether they would halt or run forever. So, Halting problem is much of a problem associated with the computational nature of the processes in this universe, and not with computational limits of the machine.