Proving Halting Problem is undecidable (for layman programmers)
There are problems which are computationally impossible. These belongs to the class of undecidable problems. For an undecidable problem there is no algorithm which solves the problem on every input regardless of the running time of the algorithm. You run polynomial time, exponential time; there’s no algorithm which is going to solve it on every input.
In 1936 the great Alan Turing proved that the halting problem is undecidable. And we’re going to see the idea of that result now.
This paper by Turing in 1936 introduced the notion which we now refer to as Turing Machine. What Turing showed is that the halting problem is undecidable on a Turing Machine and a Turing Machine captures the power of a conventional computer. By conventional we are excluding things like quantum computer.
Later, many other problems were showed to be undecidable, but the halting problem is quite nice, so we’re going to dive into that proof.
Defining Halting Problem
Input:
The input to the halting problem is a program P, with an input I for that program P.
Now how is this program P given to you?
Well, we can restrict it to any language we want. We can say it’s in pseudocode, we can say it’s in golang, C, Python, or any arbitrary language.
Output:
Now what is the output of the halting problem?
Well, think of the basic task of a compiler.
Given a program and an input, we want to figure out if this program terminates on this input or does it have an infinite loop.
That’s the task of the halting problem, to figure out whether program P on this particular input I runs forever, or ever terminates.
So if the program P on input I ever terminates, so it stops eventually, then we output true.
We’re not trying to figure out whether it runs correctly, whether it gives a correct solution on this input.
We’re just asking whether the program P ever stops when we run it on input I.
On the other side we output false if the program P on input I never terminates. In other words, it has an infinite loop.
Example
Let’s look an example instance for the halting problem.
func P(x int32) {
for x%2 == 1 {
x += 2
}
}This simple program is written in golang. The program P consists of one input variable x, and it consists of one while loop(thats how you right while loop in golang). The while loop checks whether x is odd.
If x is odd, then it adds 2 to x and it repeats. And it keeps going until x is even.
Now let’s look at this program P on input x=5.
Now for this simple program, it’s easy to see what will happen.
x starts at 5, and then it’ll be 7, 9, 11 and so on.
x will always be odd. So the program never halts as this is going to be an infinite loop. Now of course, this is assuming infinite memory. So there’s no overflows or anything like that.
Therefore if we look at halting with this pair of inputs, program P and this input x=5. Then this program has an infinite loop on this particular input. Therefore, halting(P,5) is false.
Similarly halting(P,2) is true.
Theorem: The halting problem is undecidable
How can we hope to prove this theorem?
It is incredibly difficult to come up with a program for which no algorithm can solve the halting problem on that program.
It’s easier to reason that for every algorithm, there is a program for which the algorithm fails.
So the way we go about proving this theorem is by contradiction.
Let us assume that we had an algorithm that solves the halting problem on every input. If we can construct an input for which this algorithm is incorrect then that will contradict our assumption. Therefore, that will prove the theorem.
Defining the signature of this algorithm
Now let’s give a name for this algorithm. Since this algorithm is determining whether a particular program on a specific input terminates or not. So let’s call this algorithm doesTerminate.
func doesTerminate(P, I) booldoesTerminate takes a pair of inputs,P and I. P is a program,I is an input for program P, and doesTerminate outputs true or false depending on whether this program P, on this particular input I, terminates eventually or not.
If it eventually terminates, then the output is true.
If it has an infinite loop, then the output is false.
And we’re assuming that doesTerminate is correct. It solves the halting problem for every program P, and every input I.
The Plan
Now we’re going to construct a program Q and an input J, and show that when we run doesTerminate on this input pair (Q,J), then its output is incorrect. Since doesTerminate is incorrect on this pair of input, therefore, doesTerminate does not solve the halting problem on every input.
So this will give us our contradiction, and therefore, that would complete the proof by contradiction.
Evil genius (Heavy recursion ahead)
Now how can we hope to construct this program Q?
Well, one important piece is that we’re assuming the existence of this program, doesTerminate. So we can use this algorithm, doesTerminate as a subroutine in our new program Q.
Now we don’t know anything about the inner workings of doesTerminate so we have to use it as a black box, hence we can use this as a subroutine.
So consider the following evil program, it’s evil in the sense that doesTerminate algorithm that we assumed existed is going to fail on this program.
This new program that we will define now, let us call it Contradictory.
func Contradictory(J) {
for doesTerminate(J, J) {}
}Contradictory has one input J.
First line of Contradictory is a while loop. What we do is we run doesTerminate on this input pair (J,J). So J is a program and J is the input to the program J as well.
So we use this input J of the Contradictory program as the program P and the input I for the doesTerminate algorithm.
Now doesTerminate returns true or false. So the two possibilities are
1. If doesTerminate returns true then program will go in an infinite loop.
2. If doesTerminate returns false then program exits.
Let’s detail once again what’s happening in this simple program.
We’re running doesTerminate(J,J). What does that do?
It evaluates program J(J),and doesTerminate returns true if program J(J) terminates. It eventually halts.
And it returns false if J(J) never terminates. i.e It has an infinite loop.
To summarise
a) If program J(J) terminates, then doesTerminate(J, J) will return true and program Contradictory(J) never terminates. It gets into an infinite loop.
b) If program J(J) never terminates, so it has an infinite loop. Then doesTerminate(J, J) will return false and our program Contradictory(J) exits right away, and therefore it terminates.
The Paradox
Now, we need to derive a contradiction. What we do is we set the input J to be this program Contradictory which we just defined.
So Contradictory is this short one line program, and we use that as the input to Contradictory itself.
i.e J=Contradictory
Now the question is, does the program Contradictory(Contradictory), terminate or not?
Well there are two possibilities,
either it does terminate or it has an infinite loop.
Let’s consider both possibilities.
1) Contradictory(Contradictory) terminates
Suppose program Contradictory when it takes itself as input does terminate.
We have already seen that, if J(J) terminates, then Contradictory(J) never terminates because it gets into this infinite loop.
So plugging in J=Contradictory,
we have that Contradictory(Contradictory) never terminates.
So if the program Contradictory(Contradictory) terminates, then Contradictory(Contradictory) never terminates.
That’s a contradiction. Therefore this can’t be the case.
2) Contradictory(Contradictory) never terminates
What happens in this scenario?
In this scenario when J(J) never terminates, then Contradictory(J) terminates because it exits the program Contradictory immediately.
So plugging in J=Contradictory,
if the program Contradictory(Contradictory) never terminates, then Contradictory(Contradictory) terminates.
Again, we have a contradiction, so this can’t be the case.
The Conclusion
Since either case leads to a contradiction, our initial assumption that the program doesTerminate which solves the halting problem on every input exists must be impossible. Therefore there does not exist a program which solves the halting problem on every input. And that completes the proof of the theorem.
