Introduction

Why study computation—and how do we reason about it?

Why does computation need a theory?

Computation is what computers do. So who needs theory?

Charles Babbage’s Difference Engine (1822) was an extraordinary piece of engineering. But building increasingly elaborate machines does not, by itself, tell us what machines can ultimately accomplish—or what limits every possible machine must face.

A reconstruction of Charles Babbage’s Difference Engine.

The history of engines offers a useful analogy. Hero of Alexandria demonstrated the aeolipile, an early steam-powered device, in the first century AD. Many centuries later, engineers such as Matthew Boulton and James Watt built increasingly capable steam engines. Yet engineering progress alone did not answer the most fundamental questions about engines.

Hero of Alexandria’s aeolipile.

A Boulton and Watt steam engine.

Carnot’s questions

Nicolas Carnot (1796–1832) asked questions such as:

Nicolas Carnot.

• Is the potential work available from a heat source unbounded?
• Can heat engines be improved by replacing steam with some other fluid or gas?

Carnot answered these questions by studying an abstract model of a heat engine. His work showed that the efficiency of an ideal engine depends on the temperature difference between its reservoirs. Engines therefore have fundamental limits.

An idealized Carnot cycle.

This theoretical result did not make engineering irrelevant. It gave engineers a better direction in which to work. Rudolf Diesel, for example, used insights derived from Carnot’s work while developing an alternative to the steam engine.

An early diesel engine.

Theory drives practice, and practice drives theory.

The corresponding questions about computers

Carnot’s questions have computational analogues:

1. Computability: Can every problem be solved by a computer?
2. Computational power: Can a computer solve more problems if we change how it operates or what resources it has?
3. Complexity: Which problems can a computer solve in a reasonable amount of time?

To answer these questions precisely, we first need precise definitions:

• What is a problem?
• What is a computer?
• What does it mean for a computer to solve a problem?
• How do we measure the time or memory required by a solution?

Church and Turing addressed the first major question in the 1930s by proposing formal models of general computation. The second remains connected to one of computer science’s greatest open questions: whether \(P=NP\).

This course will not resolve \(P\) versus \(NP\). It will develop the tools needed to understand what such a question means and what an answer might look like.

“I can’t find an efficient algorithm, but neither can all these famous people.”

The two major themes of the course

Computability

What problems can a computer solve at all?

Computability identifies the boundary between problems that have algorithmic solutions and those that do not.

Complexity

What problems can a computer solve with a reasonable amount of time and memory?

Complexity distinguishes problems with practical solutions from problems whose solutions require prohibitive resources.

To investigate both questions, we will use abstract models of computation, also called abstract machines.

What is a computer?

A computer is something that computes—but that only moves the question:

What is computation?

Rather than beginning with all the details of a modern computer, we will start with very simple machines and gradually add capabilities. These machines are abstract: they omit incidental implementation details and retain the features necessary for reasoning formally.

Examples considered “computers” in the original lecture.

For each model, we will ask:

• What is the machine allowed to do?
• What information can it remember?
• What problems can it solve?
• What does it mean for the machine to solve a problem?

What is a problem?

A computational problem consists of:

1. a description of a set of possible inputs, and
2. a description of acceptable outputs, including the property a correct output must satisfy.

A machine solves a problem if, for every valid input, it eventually produces a satisfactory output.

Decision problems

A decision problem has only two possible outputs: yes and no.

More general problems can often be expressed as a sequence of decision problems. Instead of asking “What is \(2+2\)?”, for example, we could ask:

• Does \(2+2=0\)? No.
• Does \(2+2=1\)? No.
• Does \(2+2=2\)? No.
• Does \(2+2=3\)? No.
• Does \(2+2=4\)? Yes.

The set of inputs for which the answer is yes forms a language.

Problems as language recognition

Let \(L\) be a language and \(s\) an input string. The corresponding decision problem is:

Is \(s \in L\)?

A machine \(M\) recognizes \(L\) if it can determine, for every input string \(s\), whether \(s\) belongs to \(L\).

We can therefore describe the computational power of a kind of machine by describing the set of languages it can recognize.

Models of computation

Machine	Added capability	Corresponding language description
Finite automaton	A finite number of states	Regular expressions / regular languages
Pushdown automaton	A stack	Context-free grammars / context-free languages
Turing machine	An unbounded tape	Recursive and recursively enumerable languages

We will also consider what happens when nondeterminism is added to these models.

The Turing machine

A Turing machine is an abstract machine capable of carrying out the primitive steps involved in any algorithmic process.

The Church–Turing thesis asserts that anything that is effectively computable can be computed by a Turing machine. This gives us a formal working definition:

Computation is that which can be carried out by a Turing machine.

This definition leads to two profound conclusions:

• Some problems cannot be computed by any Turing machine. These are undecidable problems.
• Some theoretically solvable problems require too much time or memory to be practical. These are intractable problems.

Turing machines are therefore the eventual destination of our study, but we will build toward them using simpler models.

Alan Turing

The ideas that led to the Turing machine are more fascinating—and more influential—than a brief treatment in a theory textbook can convey. Turing’s work helped establish the foundations of computer science, while his life also raises important historical and ethical questions worth studying separately.

A dramatization of Turing and the Bombe.

Alan Turing.

Course expectations

Key points from the syllabus:

• Collaboration can be valuable, but it also has limits and risks.
• Do not use solutions found online or obtained from previous students.
• Exams are not collaborative.
• A one-page reference or “cheat sheet” is allowed on exams.

Definitions and Proofs

The language of computer science

We will use the following mathematical objects throughout the course:

• sets and tuples
• functions and relations
• graphs
• alphabets
• strings
• languages
• Boolean logic

An important recurring question is:

What makes a definition precise and useful?

Defining the natural numbers

Consider the informal definition

\[ \mathbb{N}=\{1,2,3,\ldots\}. \]

The ellipsis communicates an intended pattern, but it is not sufficiently precise to support a formal proof. A recursive definition is better:

• Base: \(1\) is a natural number.
• Recursive step: If \(i\) is a natural number, then \(i+1\) is a natural number.

Theorem: There is no largest natural number

Proof. Suppose that a largest natural number \(x\) exists. By the recursive part of the definition, \(x+1\) is also a natural number. But \(x+1>x\), contradicting the claim that \(x\) is largest. Therefore, no largest natural number exists. \(\square\)

What is a proof?

A proof is an argument that establishes that a statement is true. Mathematical proofs are convincing because they use precise definitions and accepted rules of inference.

“I think you should be more explicit here in step two.”

The techniques used in this course include:

• direct or constructive proof
• proof by contradiction
• proof by induction
• proof by reduction

In many cases, the goal is to prove an implication \(p\rightarrow q\): assuming \(p\) is true, demonstrate that \(q\) must also be true.

Direct or constructive proof

To prove \(p\rightarrow q\) directly, assume \(p\) and use definitions and rules of inference to derive \(q\).

When proving that two statements or sets are equivalent, it is often helpful to divide the task into two implications. For example, to prove \(P\Leftrightarrow Q\), prove both \(P\rightarrow Q\) and \(Q\rightarrow P\).

Proof by contradiction

To prove a statement by contradiction:

1. assume the logical negation of the statement,
2. show that this assumption leads to a contradiction, and
3. conclude that the original statement must be true.

The proof that there is no largest natural number is an example: assuming that a largest number exists produces the larger natural number \(x+1\).

Proof by induction

Induction proves that a property holds for every object in a recursively defined, potentially infinite collection.

Induction is often compared to a chain of falling dominoes.

1. Define the collection recursively. This is sometimes implicit, but making it explicit is helpful.
2. Base case: Prove the property for the base object.
3. Inductive hypothesis: Assume the property holds for an arbitrary object or value \(k\).
4. Inductive step: Use that hypothesis to prove the property for the next object or value, usually \(k+1\).

Example: Closure of the natural numbers under addition

Theorem. The sum of two natural numbers is a natural number.

Proof. Let \(A\) and \(B\) be natural numbers. We proceed by induction on \(B\).

Base case: Let \(B=1\). Since \(A\) is a natural number, the recursive definition tells us that \(A+1\) is also a natural number.

Inductive hypothesis: Assume \(A+k\) is a natural number for some natural number \(k\).

Inductive step: Let \(B=k+1\). By the inductive hypothesis, \(A+k\) is a natural number. Applying the recursive definition once more, \((A+k)+1=A+(k+1)=A+B\) is a natural number.

Therefore, the natural numbers are closed under addition. \(\square\)

Recursive definitions

Recursive definitions are especially useful in theory of computation.

Sets

• Base: \(\varnothing\), the empty set, is a set.
• Recursive step: If \(S\) is a set, adding one object to \(S\) produces a set.

Alphabets

An alphabet, usually written \(\Sigma\), is a finite set of symbols.

Strings

A string is a finite sequence of symbols from an alphabet \(\Sigma\).

• Base: \(\varepsilon\), the empty string, is a string.
• Recursive step: If \(s\) is a string and \(a\in\Sigma\), then \(sa\) is a string.

Languages

A language over \(\Sigma\) is a set of strings formed from symbols in \(\Sigma\).

Practice with strings and languages

Try proving the following statements:

1. There is no longest string.
2. The set of strings over an alphabet is closed under concatenation.
3. Let \(L\) be defined recursively by:
   • \(\varepsilon\in L\);
   • if \(s\in L\), then \(sa\in L\) and \(sab\in L\).
   Prove that every \(x\in L\) neither begins with \(b\) nor contains two consecutive \(b\) symbols.

Proof-writing tips

• Read the statement carefully and understand every piece of notation.
• Break equivalence and equality claims into multiple directions:
  • to prove \(P\Leftrightarrow Q\), prove both implications;
  • to prove \(A=B\), prove \(A\subseteq B\) and \(B\subseteq A\).
• Search for counterexamples. Even when none exists, the search can reveal why the statement is true.
• An example can illustrate a claim, but it cannot prove a universal claim.
• Look for induction when your reasoning sounds like “repeat this for every \(n\)” or “the pattern continues indefinitely.”
• Be precise, and explain why each step follows.

Questions to carry into the course

1. What is the weakest kind of machine capable of solving a given problem?
2. What additional problems become solvable when a machine gains memory?
3. Are there problems that no computer can ever solve?
4. When does a solvable problem become computationally impractical?
5. How can we prove that a machine has—or lacks—a particular capability?