In this video, we study a classic problem introduced by Alan Turing, the so-called halting problem. In the halting problem, our input is the source code of any computer program, and we want to know whether this computer program eventually terminates. We show that in general the halting problem is not solvable, not even if we have unlimited time and resources. The halting problem is an example of Kurt Gödel’s incompleteness theorem, which says that any complicated enough system must exhibit unsolvable problems.
