3Preliminaries

In this section, we make some initial attempts at defining computation.

3.1What is computation?¶

At its most basic form, “to compute” means to take an input, process it in a finite number of steps, and produce an output:

An algorithm to be a step-by-step description of the computational process. Given an algorithm $A$ and an input $x$, we write $A(x)$ to denote its output.

A computational problem is a set of input-output pairs, specifying the correct output for each input. In particular, a computational problem can be represented as a predicate $P(x,y)$ that indicates, for every possible pair of input $x$ and output $y$, whether $y$ is the correct output for input $x$.

Algorithm $A$ solves problem $P$ if for every input $x$, the algorithm’s output $A(x)$ is the correct one. We can express this formally using predicate logic: $∀x~P(x,A(x))$.

3.2Model of computation¶

We are interested not just whether a problem can be solved in finite number of steps, but whether it can be solved efficiently. But what does “efficient” mean? Algorithms use resources which can range from time, space (i.e. memory), randomness, quantum entanglement, input access, and many others.^[1] Thus, “efficient” means that there is a constraint on the type and quantity of resources that the algorithm can use.

Informally, a model of computation defines constraints on resources. A problem is solvable in a model of computation there exists an algorithm that solves the problem and obeys the resource constraints on every input. For example, sorting is solvable in polynomial-time as there are algorithms (e.g. mergesort) that correctly sorts every input array in time polynomial in the input size. On the other hand, we only know how to solve integer factoring in polynomial time using quantum entanglement.

Note that to show that $P$ is solvable, it suffices to show that there is some algorithm that satisfies the desired properties. But showing that $P$ is not solvable requires us to argue that every algorithm either does not correctly solve the problem on every input, or does not satisfy the resource constraint on every input.

We are interested in studying the power and limitations of various models of computation:

1. Are there problems that cannot be solved even with unlimited resources?^[2]

2. What problems can and cannot be solved under various resource constraints?

3. Tradeoffs between different resources^[3]

3.3Strings, languages and decision problems¶

In the rest of the semester, we are going to consider problems in which the input is some string (most commonly, bit strings; more to come later), and the goal is to correctly output YES/NO, i.e. to correctly decide if some fixed (fixed means independent of the input string) predicate is satisfied by the input string or not. These are called decision problems.

We can compactly represent the problem by the set of strings for which the correct answer is YES. We call the set of strings a language. In particular, a language $L$ is a set of strings that satisfy some predicate.

Let $A$ be an algorithm. We say that $A$ accepts a string $x$ if $A(x) = \text{YES}$ and rejects if $A(x) = \text{NO}$. The language of strings accepted by $A$ is denoted by $L(A)$.