Sometimes when using your computer, you might
find that a program freezes and stops responding to you. When that happens, it's not always obvious
what's going on. In some cases, just waiting a little bit of
time solves the problem, and the program starts responding again. But in other cases, the program may have entered
some sort of infinite loop that never ends, so the program will be frozen forever and
needs to be force quit. You might wonder, though, why your computer
can't just tell the difference for you. That is to say, we might wonder if the computer
can tell whether a program will finish what it's doing at some point, or whether the program
will continue to run forever? To try to answer that question, let's set
the scene so that we can define what we're asking more precisely. We can define a computer program as some set
of instructions. A program can accept inputs, so that the program
behaves differently depending on what input is provided to the program. Here, for example, is a program called "Walk"
that starts by keeping track of a variable steps, which starts out as 0. As long as the steps value isn't equal to
the input to the program, the program instructs us to move forward, turn right, and then increase
steps by one. That keeps repeating until steps is equal
to the input, at which point the program terminates. If we give this program to a computer, and
then give it an input, like the number 4, then the computer will repeat the process
four times: moving, turning, increasing its internal step counter. And after repeating four times, the program
terminates. In other words, when the program is done running
all its instructions, it will halt. But if we give the same program a different
input, like the number -1, the computer will keep running this program forever. Every time the loop runs, the step counter
increases by 1, but the counter will never reach -1, so with this input, the program
will never halt. So here's our question: could we define a
new program "Halt" that accepts a program and an input and tells us whether that program
will halt when run on that input. This is the halting problem, and it's a famous
problem in computer science. The answer, it turns out, is that the halting
problem can't be solved. Not only is there no program that exists that
can solve the halting problem, but we can actually prove that there could never be a
program that solves the halting problem. So, let's prove it. Let's prove that the halting problem can't
be solved. We'll approach this proof using a common technique
known as proof by contradiction. We're going to start by assuming that there
is a program that solves the halting problem, and show that if such a program were to exist,
it would lead to a contradiction: some situation that logically doesn't make sense and couldn't
possibly be true. Let's give it a try. Say we had some program called "Halt" that
could solve the halting problem: it could take a program and an input, perform some
computation, and then give us back an answer: either yes, the program does halt on the input;
or no, the program does not halt on the input. If such a program were to exist, we could
then use it inside of other programs. Here, for example, is a program called "Opposite". It accepts an input program, and then uses
the "Halt" program to see whether the input program will halt when given the input program
itself as its input. The reason we've called this larger program
"Opposite" is because whatever "Halt" tells us, we're going to do the opposite: if "Halt"
says yes, the program will halt, then "Opposite" will do the opposite and never halt, as by
looping forever. If "Halt" says no, the program won't halt,
then "Opposite" will terminate and halt the running of the program. So if we have a computer run this "Opposite"
program, it'll work like this. We give the program some input. The computer will take the input and pass
it along to the "Halt" program, checking to see whether that program will halt when given
itself as input. Whatever "Halt" says, "Opposite" does the
opposite. If "Halt" says the input program halts, then
"Opposite" will do the opposite and loop forever, never halting. Importantly, as long as it's possible to write
the "Halt" program, it's also possible to write this "Opposite" program: since we're
just adding some logic like conditional constructs and loops that we know computer programs can
use. But now, here's the tricky question: what
happens if we use the "Opposite" program itself as the input to the "Opposite" program? Does the program halt? Well, let's consider what might happen. Following the program's instructions, the
first thing that happens is that we ask the "Halt" program whether the "Opposite" program
will halt when given the "Opposite" program as input. There are two possibilities. Possibility one is that "Halt" says yes: the
"Opposite" program will halt when given the "Opposite" program as input. Then, our program does the opposite and decides
not to halt. But that doesn't make sense, because "Halt"
said that the program would halt in this case. Possibility two is that "Halt" says no: the
"Opposite" program will not halt when given the "Opposite" program as input. Then, our program does the opposite and decides
to halt. Again, this doesn't make sense, because "Halt"
said our program wouldn't halt in this case. Either way, we've reached a contradiction,
where whatever "Halt" says will happen can't possibly be consistent with what actually
happens. And if assuming the existence of the "Halt"
program was all it took for us to arrive at this logical contradiction, then the only
explanation is that our original assumption is wrong, and that the "Halt" program logically
cannot exist. There can never be a program that can tell
us, in general, whether a program will halt on a given input. So, the next time you see a program that appears
to be running forever, know that your computer can't be so sure. Maybe it is running forever, or maybe it's
just running for a long time and will finish eventually. The computer doesn't have a way to know. There are some problems — many problems,
in fact — that computers just can't solve, and the halting problem is one of them.
