Not every well-defined problem can be solved by an algorithm and thus by a program. Problems that have no algorithm are called unsolvable. Fortunately, most problems we encounter in applications and need to write a program for can be solved by an algorithm. However, a number of interesting problems arising in various branches of mathematics (e.g., logic, game theory) are unsolvable.
We describe three problems which have no algorithm. We first describe a simple “reverse and add until a palindrome” problem for which it is not known whether there exists a program solving it. We actually write a Python program for it, but it is not a correct program as it may create an infinite loop on some inputs. Nobody knows whether the problem has an algorithm that will terminate on every input. The computational difficulty lies in being able to determine that no palindrome can be generated. We also describe two known unsolvable problems, the Halting problem and the Wang Tile problem. For both problems there exists a mathematical proof showing that no algorithm can exist.
