The Halting problem is the problem where given code and input to a computer program, can you decide if the code halts on that input. In 1936, Alan Turing proved that you cannot write a computer program to solve this problem. This is the first computational problem that was proven to not be solvable by a computer, no matter how powerful it may get.

In this article, I will explain why no computer program can solve the Halting problem. I will present this reasoning in a story that anyone can understand, even with no background in computer science. All you need to know if that a computer program is some instructions given to a computer to tell it what to do when given certain inputs.

Story

Imagine that you have a computer program that can solve the Halting problem. Let’s name this program Herbert. Herbert can be given code and input to some other computer program and decides if the code halts on that input.

Now, I will write a program named Paradox. Given code and input to some other computer program, Paradox does the following:

1. Ask Herbert if the code halts on the input
2. If Herbert says yes, run forever
3. If Herbert says no, halt

Let’s consider what happens if Paradox is given its own code as input.

1. Paradox asks Herbert if Paradox halts on its own code
2. If Herbert says yes, run forever
3. If Herbert says no, halt

In both cases, Herbert is always wrong. If Herbert says that Paradox will halt, Paradox starts to run forever. If Herbert says that Paradox won’t halt, Paradox halts.

Since we have found a situation where Herbert is wrong, it is logically impossible for Herbert to exist. Therefore, a computer program that solves the Halting problem can’t exist.