- Input: A list of instructions (think of an algorithm, or even a computer program written in any programming language).
- Question: Does it eventually terminate?
Section 1.6 Undecidable Problems
As we have discussed, the notion of polynomial-time reductions divides the set of all decision problems into classes which form a hierarchy based on “hardness”. In this section, we will briefly discuss the hardest problems of all: the undecidable problems; i.e. the problems which cannot be solved by any algorithm. At first, it may seem bizarre that such problems can even exist but, as it turns out, there are some pretty simple examples of such problems. The most famous is the Halting Problem.
Problem 1.6.1. The Halting Problem.
An example of a “no” instance of the Halting Problem is an infinite loop. E.g. the following list of instructions never terminates:
- Initialize \(i:= 0\)
-
while \(i\geq 0\)
- increase \(i\) by \(1\text{.}\)
That is, we initialize the variable \(i\) to be zero and then, as long as \(i\geq0\text{,}\) we increase \(i\) by one. Clearly, this will never terminate (however, technically, in most coding languages, this will terminate; do you know why?). So, this is indeed a “no” instance. It is not too hard to come up with a “yes” instance of the Halting Problem. Just come up with any algorithm that eventually terminates. An empty algorithm would do the trick. Let us now see why the Halting Problem is undecidable.
Theorem 1.6.2.
The Halting Problem is undecidable.Proof.
Suppose that there exists an algorithm \(A\) which can accept any list of instructions as an input and, in a finite amount of time, can output TRUE or FALSE depending on whether the list of instructions terminates or not. Now, let \(P\) denote the following computer program:
-
if \(A(P)\)
- Loop forever.
-
else
- Terminate.
Note that \(P\) is “self-referential”. That is, the program depends on itself. That’s not against the rules! Anyway, now we ask: Does \(P\) terminate? Well, if it does, then \(A(P)\) is true... which triggers \(P\) to loop forever. But, if it does not terminate, then \(A(P)\) is false which causes it to terminate. Either way, we run into a contradiction. So, the only reasonable thing to conclude is that the algorithm \(A\) cannot exist. This issue of self-reference is analogous to those that appear in other paradoxical constructions that you may be familiar with, such as Russel’s Paradox. If you’re interested in hearing more about this topic, see the video at the end of this section. Anyway, this completes the proof.
We won’t go into great depth on undecidable problems in this course, but it is worth presenting at least one more example (without proof). In the year 1900, Hilbert famously proposed 23 problems which motivated a large part of 20th century mathematics. His 10th problem was on devising a general algorithm for determining whether a Diophantine equation with integer coefficients has an integer solution. This was solved by Matiyasevich who showed that no such algorithm exists; in fact, he proved the following.
Theorem 1.6.3. Matiyasevich’s Theorem.
Given an integer \(k\) and a polynomial \(p(x_1,\dots,x_k)\) as an input, the problem of determining whether or not \(p(x_1,\dots,x_k)\geq0\) for all \(x_1,\dots,x_k\in\mathbb{Z}\) is undecidable.
There are also many natural problems throughout different areas of mathematics, including discrete mathematics, which turn out to be undecidable. See, for example, this paper, this one, or this one.
Here is a YouTube video related to the topics of this section (skip to the 1 hour and 13 minute mark).
Here is a video by Veritasium on topics related to the Halting Problem and various related paradoxes in mathematics.
