To reason precisely about what computers can and cannot do, we need abstract models that capture the things we think are important but avoid the complexities of physical objects.

The physical world is messy and suffers from arbitrary limits — this applies both to the physical computing devices we use (which always have some probability of failing and can’t even do arithmetic correcly) and even more so to biological systems we consider in this class. Mathematics is precise and unconstrained — we can define formal systems that always behave in the prescribed way, can do operations without generating heat, and can be infinite. Mathematical models are useful because we can reason about them using the formal tools of mathematics, and can abstract away physical complexities and finite limits of physical reality. Mathematical models have proven uncannily useful in understanding and predicting properties of the physical world, but when we use them we have to be mindful that they are abstractions that avoid many of the messy aspects of physical reality.

To model a computer, we need to: (1) define a set of mathematical objects that correspond to instances of the computer we are modeling; and (2) define an execution model that shows how any element in that set in that model executes. Note that when we say computer in theoretical computer science, we mean a complete computing system — there is no separation between “hardware” and “software” as there is in informal use of “computer” as a physical device that doens’t do anything without its program. In our theoretical computing models, the input may include a description of a program (and often does), but the mathematical object that we are modeling includes everything needed to perform a computation.

An execution of a computer takes (1) an input, (2) does some processing, and (3) produces an output. So, the execution model for a model computer needs to explain how the input is represented (typically by a finite string of bits), and how processing is done (this typically requires defining some kind of abstract machine that operates on the input, and uses some kind of storage (also called memory) to keep track of what it is doing), and a way to know when an execution is finished and to interpret the final state of the abstract machine (including its memory) as the output.

We discuss two examples of computing models soon, but first introduce some important terminology. When discussing computing, several terms that are often used informally are used in a very precise way and the precise definitions of these terms are important for understanding what statements using them mean both in theory, and what such statements imply in practice. Some important terms to understand precisely:

• Functions: a function is a relation that maps an input to an output. The set of possible inputs to a function is known as the domain; the set of possible outputs is its codomain. If the function is defined for all elements of the domain it is total; if not, it is partial. A function is defined by how it maps inputs to outputs, and there are many different ways to describe a function. A finite function (where the input size if fixed) can be defined by a table that gives the output for each possible input (as the input size becomes larger than a few bits, though, this becomes infeasible in practice, but it is still useful to think of functions this way). We can define more complex functions by giving the property the output should have. Note that the term function is often (mis)used by programmers and programming languages to mean a procedure for doing computation that takes some input parameters and returns an output. This is very different from a mathematical function, and the two should not be confused.
• Algorithms: an algorithm is a precise description of steps to perform. An algorithm computes a function if it is guaranteed to always produce a correct output for any input (that is, it implement the input-output mapping of the function). This means it must always finish and output a result, and the output it produces must be the correct output for the given input. We talk about solving a problem by providing an algorithm that computes a function that satisfies the requirements of the problem.

Two useful and widely used theoretical models of computers are Boolean circuits and Turing machines (in this class, we will assume clear understanding of these models, and some variations on them, and may also use a replacement grammar model of computation (Lambda Calculus), but will introduce it in class). We provide a refresher summary of these two models below, but won’t provide a detailed introduction to these models here. So, if you are not already familiar with them follow the links in the Additional Materials below.

Model	Boolean Circuit	Turing Machine
Input	Fixed-length sequence of bits, each input bit is one input wire for the circuit	Finite sequence of bits of any length, written from left to write on a infinite tape. When the machine starts execution the rest of the tape is blank, and the tape head is at the leftmost (first) input bit.
Processing	Boolean logical operations (e.g., AND, OR, NOT) connected in an acyclic graph. Each Boolean operation (sometimes called a gate) takes a few input bits (e.g., 2 for AND and OR, 1 for NOT) and outputs one output bit)	State machine with a tape head, each step it can read the current square on the tape, write a new symbol in that square, move (left, right, or halt), and transition to an internal state
Termination	Always terminates since circuit is acyclic	Terminates if a halt transition is executed (but may run forever without producing any output)
Output	Values on the output wires of the circuit	Sequence of symbols on the tape when the machine terminates
Functions	All finite functions	The computable functions (by definition — the computable functions are defined as the set of functions that can be computed by a Turing Machine)

One of the most important insights that comes from formally modeling computing is that the sets of functions that can be computed by particular computing models are very robust to slight (and sometimes even major) changes to the model, and many seemingly very different models of computing can compute exactly the same sets of functions. This ability to make one machine do anything is why programming is so powerful: using one simple (at least abstractly) computing engine, we can perform any computation by finding the right program.

For finite functions (where the input to the function is a fixed-length binary string), there is a Boolean circuit that computes every finite function using only two-bit AND, two-bit OR, and one-bit NOT operations. We can compute exactly the same set of functions (that is, all finite functions) using Boolean circuits composed of just two-bit NAND. This can be proven by showing how to compute the each of the AND, OR, and NOT operations using a Boolean circuit made of only NAND gates. We call sets of gates that can be used as the components of Boolean circuits that are capable of computing every finite function a universal gate set.

For functions where the input length is unbounded (but still finite), a Turing Machine is universal, in the sense that it can compute every function that can be computed by every other ``reasonable'' computing model. (What it means for a computing model to be reasonable is either circularly defined as those that are equivalent in power to a Turing Machine, or defined intuitively as anything that could be done by a human computer following precise rules with unlimited scratch paper, which was what Turing was originally modeling, but also covers many variations on Turing Machines as well as more different computing models like replacement grammars and random-access memory machines.) We can prove a computing model is universal, but showing that it can simulate a Turing Machine; we can prove that it is no more powerful than a Turing Machine by showing how a Turing Machine can simulate the new model.

 

Next: Computational Complexity