Throughout the course, I've alluded to the notion of computability. Computability is the notion that a problem can be solved using a mechanical procedure. Much of 20th century logic was built as a way to describe mathematical proof and hopefully automate it, and the birth of computer science stems directly from these efforts.
Of course, that we talk about the notion of computability implies the possibility that some problems are, well, not computable. This would mean that there is no algorithm that can solve these problems at all. Depending on how you feel about computers, this may or may not be an obvious statement.
First of all, what is a problem? There are many different ways to define this. For instance, in sorting, we want to end up with a sorted list. In optimization problems, we may want to minimize or maximize some parameter. For our purposes, we will stick to decision problems.
Definition 23.1. A decision problem is a problem with an answer of either yes or no.
Much like how we determine whether a predicate is satisfied by a tuple of terms, we can think of decision problem as sets containing the items which satisfy it. In fact, this is how these kinds of problems are often considered in computability and complexity theory.
For instance, if we have the set $$P = \{n \in \mathbb N \mid \text{$n$ is a prime number}\}$$ then the decision problem for $P$ is determining whether a number is prime or not. Or maybe if we have $$R = \{\langle G,s,t \rangle \mid \text{$G$ is a graph that contains a path from vertex $s$ to $t$}\}$$ then $R$ is the problem of determining whether there exist graphs $G$ with vertices $s$ and $t$ such that there's a path from $s$ to $t$ (sometimes called the reachability problem). Another problem could be $$S = \{\varphi \mid \text{$\varphi$ is a propositional formula that is satisfiable}\}.$$ Here, $S$ is called the satisfiability problem, which I mentioned back when we were talking about satisfaction of propositional formulas.
One objection to using decision problems is that this seems to limit what kinds of questions we can ask. This doesn't turn out to be a huge problem, since many different kinds of problems can be reformulated so that all we need is a yes or no answer. For instance, in a lot of optimization problems, like finding a shortest path through a graph, we can reformulate our problem into asking whether there exists a path of length $k$. Then to find the shortest one, we just ask the decision problem variant for $k = 1, 2, \dots$.
For all of the problems we mentioned above, determining whether a given natural number is prime, whether some vertex is reachable from another vertex in a particular graph, or whether $\varphi$ has a satisfying assignment of propositional variables, there are algorithms that exist that tell us whether an instance is a yes-instance ($n$ is a prime, $G$ is a graph that satisfies the property, $\varphi$ is a satisfiable propositional formula) or a no-instance ($n$ is not a prime, $G$ is not a graph that satisfies the property, $\varphi$ is not a satisfiable propositional formula). We call such problems decidable.
Definition 23.2. A decision problem is decidable if there is an algorithm that, given an input to the problem, outputs "yes" if the input has answer "yes" and outputs "no" if the input has answer "no". A problem is undecidable if it is not decidable.
Example 23.3. Let $S \subseteq \mathbb N$ be a finite subset of the natural numbers. Then $S$ is decidable.
Example 23.4. Let $C \subseteq \mathbb N$ be the set of composite numbers. Then $C$ is decidable.
Example 23.5. Let $S \subseteq \mathbb N$ be a subset of the natural numbers that is decidable. Then the complement of $S$, $\overline S = \mathbb N \setminus S$ is decidable.
However, is it the case that every problem can be solved using an algorithm?
The first of these kinds of problems was asked by Hilbert in 1900, when he asked whether there was a mechanical procedure to determine if a Diophantine equation had a solution in the integers. This is known as Hilbert's 10th problem.
In 1928, he asked another, similar question, which we refer to now as Hilbert's Entscheidungsproblem. Typically, in a theory of computation class, this is boiled down to asking whether any mathematical problem could be mechanically. What we mean by that is that he asked if mathematics was:
However, we're in a logic class and so we can state his actual problem: Is there an algorithm that, when given a statement in first-order logic, outputs "Yes" if the statement is valid and "No" if not. This is the problem which is called provability in the slides: If we have a (first-order) logical statement, does it have a proof?
Gödel's Completeness theorem says that we can, hypothetically., if it is valid However, there are two problems with this. The first is the one we encountered during our discussion: even though a proof should exist somewhere out there, we don't have a way to construct it, at least not from what we've gained through the proof.
The second is a problem that comes up by his Incompleteness theorems. Because, you see, when we talk about proving things in mathematics, we have a very clear idea of what kinds of rules we should allow and what kinds of objects should be in our domain and such. That is, we have a specific interpretation that we would like to prove things about. This is different from saying that first-order logic as a whole is complete and sound.
As I mentioned earlier, in 1931, Gödel showed, via his Incompleteness theorems, that no system that is powerful enough to prove the things we want to prove can be both complete and consistent. Specifically, he showed that every sufficiently powerful system, the system is either incomplete or inconsistent. How powerful is sufficiently powerful? The system that he used was Peano arithmetic, which deals with addition and multiplication of natural numbers. (Note that Presburger arithmetic, which only deals with addition is weak enough to be both complete and consistent!)
As a note, Hilbert's 10th problem also turns out to be undecidable. This was shown in 1970 by Yuri Matiyasevich making use of earlier work by Julia Robinson, Martin Davis, and Hilary Putnam.
Alan Turing would be the one to show that the third item on Hilbert's wish list is also not achievable and it is by doing this that he gets to be called the Father of Computer Science. To do this, he essentially invents the notion of computation by defining a model of computation that we call the Turing machine in 1926. Obviously, back in the 1920s, they didn't have computers as we know them now (those don't enter the picture until at least during the Second World War). Instead, computers were people who carried out computations and the Turing machine is meant to simulate the way people carry out computations.
Now, these people were not necessarily mathematicians; they were given a set of instructions and all they needed to do was follow the "algorithm" given to them, kind of like what you could do if you had hired 30 co-op students or something. In this case, what would each person need to carry out a computation? At a very abstract level, the person would:
So because you don't want your co-op students to keep coming back to bother you every time they read something, you give them a set of instructions which hopefully will cover everything they need to do, including when they can stop. This set of instructions cannot be infinitely long, but their workspace, like a whiteboard or a lot of scrap paper, can be infinitely long.
That is basically a Turing machine: a conceptual machine that reads some input, has some limited/finite set of states to remember or instructions it can carry out, and modifies or writes some output. With this model, Turing showed that you could even define some very general model that could read the definitions of other Turing machines and simulate them.
Notice that that's essentially what a general-purpose computer does. We no longer need to build hardware-specific to certain computing tasks (although we certainly can and do sometimes for more specific purposes). So we don't need a special machine to compute the digits of $\pi$ and another machine that will let us watch cooking videos on YouTube and yet another machine that will interpret Racket.
What this allows us to do is abstract the things that Turing machines compute into algorithms and programs. So although traditionally, all of the stuff that we're talking about is formally presented as things that Turing machines do, we can simply talk about algorithms or programs that do the same thing.
But how do we show that something is undecidable? This sounds a lot like the problem with trying to figure out if some entailment has a proof. How do we show the non-existence of a proof? How do we show the non-existence of an algorithm? Does such a problem even exist?
There are two main ways to show that a problem $P$ is undecidable. The first is to prove that $P$ is undecidable directly. We will see how to do this later on. The second is to show that if we assume $P$ is actually decidable, then we can use it to come up with an algorithm that decides some other problem $Q$ that we've already showed is undecidable. Since we already know that $Q$ is undecidable, this must mean that our assumption that $P$ was decidable was incorrect.
From this, it sounds like proving that $P$ is undecidable directly is much more difficult than showing that it can be used to solve some other undecidable problem. The problem is that in order to use the second method, we must have an example of at least one other undecidable problem. What this means is that we will have to show that at least one undecidable problem exists before we can make use of it.
The ur-undecidable problem is due to Turing in 1936 and is called the Halting problem. The problem is stated as follows:
Problem 23.6. Given a program $P$ and input $I$, will $P$ terminate when run on input $I$?
That is, we want to know if when we run a program $P$ on some input $I$, whether it will stop at some point or if it will run forever. It turns out that this problem is undecidable.
Theorem 23.7. The Halting Problem is undecidable.
We will examine the proof of this next class.
However, once we know that there is some problem out there that is undecidable, we are able to show whether some other problem is undecidable or not.
Example 23.8. We will outline what a proof of the undecidability of a problem by using the Halting problem looks like. Let $D$ be a decision problem. We will show that $D$ is undecidable.
Note that in general, to show that a problem $P$ is undecidable, it is not a requirement that you reduce to the Halting problem; any other undecidable problem may do, as long as you can describe how your algorithm works. However, we don't know that many undecidable problems, so your reductions will likely end up reducing $P$ to the Halting problem.
Step 3 is where most of the work is done. The idea is that you can transform the problem you want to solve into some other slightly different problem you know how to solve already. This is a very computer science thing to do. We can define this notion more formally.
Definition 23.9. We say a decision problem $P$ reduces to a problem $Q$ if you can solve $P$ given access to an algorithm to solve $Q$.
Example 23.10. Here is an example of a reduction that doesn't have anything to do with decidability. Suppose we want to show that a formula $\varphi$ is unsatisfiable. We could describe an algorithm that solves this directly, but we know from above that satisfiability is decidable. Suppose we have an algorithm SAT that solves satisfiability. Then we can define an algorithm UNSAT, which takes as input some propositional formula f, by doing the following:
UNSAT(f):
b = SAT(f)
if b is True:
return False
else:
return True
In other words, our algorithm just runs the algorithm we already had. Now, suppose we wanted to determine whether a formula was a tautology. We can use the same trick. Here is an algorithm TAUT for solving tautology:
UNSAT on the formula $(\neg \varphi)$.
UNSAT returns True, then $(\neg \varphi)$ is unsatisfiable. Therefore, every valuation satisfies $\varphi$, so return True.
UNSAT returns False, then $(\neg \varphi)$ is satisfiable. Therefore, there is a valuation $t$ such that $\varphi^t = F$, so return False.
These are simple manipulations but by doing this, we can say something about the satisfiability problem. That is, if unsatisfiability or tautology turned out to be provably difficult, that would mean satisfiability would also be difficult, since both unsatisfiability and tautology can be solved by solving satisfiability. Similarly, we know that solving unsatisfiability and tautology can be as easy as solving satisfiability. This is exactly what we would do more rigourously if we were interested in the complexity of these problems.
We can apply the same insight to decidability and undecidability. The following result states explicitly what we have assumed in our proof template above.
Theorem 23.11. If $A$ is reducible to $B$ and $B$ is decidable, then $A$ is decidable. If $A$ is reducible to $B$ and $A$ is undecidable, then $B$ is undecidable.
A very common pitfall of working with reductions is getting confused about what is getting reduced to what. A very easy trick I tell my students in CS 360 to do is to just draw it out.
Suppose I want to reduce $P$ to $Q$. In other words, I want to use $Q$ to solve $P$. I can construct a big machine for solving $P$, but inside of it, I have a smaller machine that solves $Q$ and I just have to hook up the wires correctly to get the result I want.
Example 23.12. Let HALT-NO-INPUT be the problem
Given a program $P$ which takes no input, does $P$ halt?
We will show that HALT-NO-INPUT is undecidable. Suppose for contradiction that HALT-NO-INPUT is decidable and let $A$ be an algorithm that decides it. Let $(P,I)$ be a program and input that we want to determine whether it halts or not. We will construct a program $P'$ that takes no input and does the following:
Then $P'$ halts if and only if $P$ halts when run on input $I$.
Now, we describe an algorithm that solves the Halting problem:
This decides the Halting problem, by our earlier observation about $P'$ halting. But the Halting problem is undecidable, so we have a contradiction. Therefore, HALT-NO-INPUT is not decidable.
Example 23.13. Let RUNS-FOREVER-0 be the problem
Given a program $P$, does $P$ run forever on input $n = 0$?
We will show that RUNS-FOREVER-0 is undecidable. Suppose for a contradiction that RUNS-FOREVER-0 is decidable and let $A$ be an algorithm that decides it. Let $(P,I)$ be a program and input that we want to determine whether it halts or not. We will construct a program $P'$ that takes no input and does the following:
Then $P'$ halts on all inputs, including 0, if and only if $P$ halts when run on input $I$.
Now, we describe an algorithm that solves the Halting problem:
That is, the algorithm outputs the opposite of whatever $A$ does. This algorithm decides the Halting problem, but the Halting problem is undecidable, so we have a contradiction. Therefore, HALT-NO-INPUT is not decidable.