1. Introduction

In this course, we will examine one big question:

    What problems can computers solve?

This question is extremely broad, but as we will see throughout the course, we can obtain remarkably definite and far-reaching answers to it.

As a first step, let’s clarify what we mean by problems in the question. Here’s a reasonable definition: a (computational) problem is a task where for each possible input to the problem, there is one or more valid outputs that is to be produced. This notion of problem is general enough to capture almost any task that you could want to accomplish using a computer. But, in fact, it is a little bit too broad to study directly, so we start with two simplifying restrictions.

Two Simplifying Restrictions

Our first restriction is on the set of possible inputs to the problems that we will consider.

Simplifying Restriction 1. We only consider problems whose inputs are binary strings.

We use \(\{0,1\}\) to denote the two elements of the binary alphabet, and we write \(\{0,1\}^n\) to denote the set of strings that contain exactly \(n\) binary symbols. The unique string in \(\{0,1\}^0\) is the empty string, which we denote by \(\varepsilon\). We also write \(\{0,1\}^* = \bigcup_{n \ge 0} \{0,1\}^n\) to denote the set of all possible binary strings.

Formally, then, the first simplifying restriction says that the only problems we will consider are those whose inputs are \(\{0,1\}^*\). This restriction is rather mild, since we can encode any object with a finite description with a binary string. This observation is basic but will prove to be extremely useful, so let’s highlight it with a proposition that makes this claim a little bit more precise.

Proposition 1. For every finite set \(\mathcal{X}\) with \(k\) elements, there is a one-to-one encoding function \(h : \mathcal{X} \to \{0,1\}^{\lceil \log k \rceil}\).

Proof. Fix any ordering \(a_1,a_2,a_3,\ldots,a_k\) of the elements of \(\mathcal{X}\). Then define the encoding function \(h\) that maps \(a_i\) to the string that gives the binary representation of \(i\).

The second simplifying restriction is on the outputs of the problems that we consider.

Simplifying Restriction 2. We only consider decision problems, where there is exactly one valid output for each input, and this output is either Yes or No.

Equivalently, in a decision problem the output on every input to the problem is exactly one of the elements in \(\{0,1\}\).

This restriction is more severe than the first one; there are many natural problems that interest us for which the desired output is not simply a Yes or No answer. And in fact we will return to more general problems with other outputs at various points throughout the course. However, it turns out that in most cases, understanding what decision problems can be solved by computers really is the key to understanding which more general problems they can solve as well.

Functions and Languages

With the two simplifying restrictions in place, a decision problem where all the inputs are binary strings of length $n$ can be described with a Boolean function

where for each \(x \in \{0,1\}^n\), the value \(f(x)\) represents the valid output for input \(x\).

To better understand what computers can do, however, we usually don’t want to consider problems where all the inputs have the same length. Instead, we want to consider decision problems where the inputs can be binary strings of any length. Such problems can be represented by a family of Boolean functions or, equivalently, by languages that we represent as subsets

To see the connection between Boolean functions and languages, notice that for any \(n \ge 0\), the set of inputs of length \(n\) in a language \(L\) can be represented with the Boolean function \(f \colon \{0,1\}^n \to \{0,1\}\) defined by setting \(f(x) = 1\) if and only if \(x \in L\).

Similarly, any family of Boolean functions \(\{f_n\}_{n \ge 0}\) where \(f_n \colon \{0,1\}^n \to \{0,1\}\) for each \(n \ge 0\) corresponds to the language \(L = \bigcup_{n \ge 0} f_n^{-1}(1)\).

Cardinality of Languages

Counting arguments will prove to be extremely useful in establishing the fundamental limits of computers. To apply counting arguments to languages, we review some fundamentals about cardinality of sets.

A set \(S\) is finite if there is a one-to-one mapping between the elements of \(S\) and the elements in the set \(\{1,2,\ldots,n\}\) for some \(n \ge 0\). Otherwise, \(S\) is an infinite set.

A set \(S\) is countable if there is a one-to-one mapping between the elements of \(S\) and the set of natural numbers \(\mathbb{N} = \{1,2,3,\ldots\}\). Otherwise \(S\) is uncountable.

For any fixed value of \(n\), the set of binary strings \(\{0,1\}^n\) is finite. The set \(\{0,1\}^*\) of all binary strings is infinite, and it is countable.

Proposition 2. The set \(\{0,1\}^*\) is countable.

Proof. Consider the mapping \(h \colon \{0,1\}^* \to \mathbb{N}\) where for each \(x \in \{0,1\}^*\), we define \(h(x)\) to be the natural number with binary representation \(1x\), where we use \(1x\) to denote string concatenation, where we add a 1 at the front of the string \(x\). The mapping \(h\) is one-to-one, as we can verify directly.

This result also implies that the set of strings in any language is countable. The set of all languages, however, is uncountable.

Theorem 3. The set of all languages is uncountable.

Proof. This proof is an example of a diagonalization argument. We will use similar arguments multiple times throughout this course.

Assume for contradiction that the set of all languages is countable. Then we can list the set of languages in some order \(L_1, L_2, L_3, \ldots\).

We can build a table whose columns are labelled by the strings in \(\{0,1\}^*\) in lexicographical order and rows are labelled by the languages \(L_1, L_2, L_3, \ldots\) in the order we just defined. For each cell \((L_k, x)\) in the table, enter a 1 in the cell if \(x \in L_k\) and 0 otherwise. The table will look something like this:

\(\,\)	\(\varepsilon\)	0	1	00	01	10	\(\cdots\)
\(L_1\)	0	0	0	0	0	0	\(\cdots\)
\(L_2\)	1	0	0	0	0	0	\(\cdots\)
\(L_3\)	0	1	1	0	0	1	\(\cdots\)
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\ddots\)

Consider now the language \(D\) that we obtain by looking at the diagonal entries of this table and using their negation to determine if the corresponding string is in \(D\). Namely, if \(x\) is the \(k\)th string in the lexicographical ordering of \(\{0,1\}^*\), then \(x \in D\) if and only if \(x \notin L_k\).

\(D\) is a language so by our assumption there is a value \(n \in \mathbb{N}\) such that \(D = L_n\) is the \(n\)th language in our list. Let \(x\) denote the \(n\)th string in the lexicographical order of \(\{0,1\}^*\). But then \(x \in D\) holds if and only if \(x \notin L_n\), so \(D \neq L_n\). We have arrived at our desired contradiction, and so the set of all languages must be uncountable.

First Uncomputability Result

We can use the last two results to obtain our first result regarding the limitations of computers.

Let’s go back to our main question. What problems can computers solve? We have seen that with our two simplifying assumption, we can represent problems as languages. But what about computers? What does it mean for them to solve a problem—or a language? Let’s keep things simple and concrete for now, and consider what happens if we say that a computer can compute a language if there is a valid Python program that accepts exactly the set of inputs that belong to the language.

Proposition 4. There exist a language \(L\) for which there is no Python program that accepts each input \(x \in \{0,1\}^*\) if and only if \(x \in L\).

Proof. Assume on the contrary that for every language, there is a Python program that accepts exactly the set of strings in that language. Then there is a map from the set of all languages to the set of Python programs. But every program can be represented as a binary string. (Just take the binary encoding of the program.) So there is a mapping from the set of all languages to the set of Boolean strings \(\{0,1\}^*\). But since \(\{0,1\}^*\) is countable, this means that there is a mapping from the set of all languages to \(\mathbb{N}\), contradicting Theorem 3.

There is nothing special about our choice of definition of algorithms as Python programs. You could of course replace Python with your favourite programming language. Or we could even be more general and observe that for any machine model that specifies a finite list of allowed instruction and consider algorithms that consist of finite lists of these instructions, the same argument applies. (The key step in the proof just relies on the fact that we can encode our algorithms as strings, and this step holds whenever the algorithms have finite descriptions.) As a result, for any fixed machine model, there are decision problems that cannot be computed by algorithms in this model.

That was easy! But then… why are we not done? If we reflect on the result we have established, we may find (at least) two reasons to be slightly unsatisfied with it. First, the result is non-constructive: it tells us that there do exist problems that can’t be solved by computers, but it does not tell us anything about what these uncomputable problems might be. As far as this result shows, it could be that the problems that can’t be solved by computers exist but would never be anything that we would be interested in solving anyways. In fact, it could be that we can’t even describe these uncomputable problems!

And the second problem is that even though it says that each machine model has some languages that it can’t compute, it doesn’t say anything about languages that are uncomputable by all machine models simultaneously. Or, in other words, it leaves open the possibility that we can solve every problem with computers, as long as we’re allowed to build different types of computers (using different machine models) for each problem.

In the next lecture, we solve both problems: we’ll identify an explicit problem that can’t be solved by any computer, no matter how we define it.

Eric Blais ©2024 — Last edited on Jan. 7, 2024