and therefore our ideas about ourselves. It reverberates through our culture, producing excitement, anxiety, and countless B-movies about virtual reality and cyber-thingies.

And yet for all our collective fascination with computation, what we mean by the term is still somewhat mysterious.

QUES TIONS AND ANSWERS

Suppose you ask someone: “What’s seven plus three?”If they reply “10,” then they just performed a computation. So we can provisionally think of computation as a kind of question-answering. In the case of addition, the question always involves a pair of numbers and the answer is always another number. For any particular addition question, there’s a corresponding number, determined by the pair of numbers, which is the desired answer.

Now suppose you ask them “What’s one million, seven hundred eighty-two thousand, six hundred, and seventy-eight plus three million, two hundred ninety-two thousand, seven hundred and four?” Unless they’re especially good at mental arithmetic, they won’t be able to keep all the numbers in their head and so they’ll have to take out pencil and paper, ask you to repeat the question, write it down, perform the addition on paper, and read off the answer.

But now arithmetic is no longer just a mental operation; it’s also a physical operation. It involves manipulation and change of physical objects (the pencil and paper). We’re used to thinking of the arithmetic as a “mental” thing that takes place “in” our heads. But in this case, it’s spread out between a person’s head, hands, pencil, and paper. Another change from the seven-plus-three example is that while we presented the numbers to the person as a set of sounds in spoken English, they then represented them as symbols on paper, presumably Arabic numerals. (In fact, “the numbers themselves” never even made an appearance, since they’re completely intangible; we only have access to them through representations.)

What’s interesting here is that none of these differences matter. So long as the person comes up with the right

answer in whatever representational system or systems they happened to be using, we consider them to have successfully done the arithmetic. Put another way, it doesn’t matter which path we take through the diagram below:

 

Writing
Writing
add2

Write
Read
Speech
Speech
add1

 

We’ll call this the principle of behavioral equivalence: If a person or system reliably produces the right answer, they can be considered to have solved the problem regardless of what procedure or representation(s) they used. Behavioral equivalence is absolutely central to the modern notion of computation. If we replace one computational system with another that has the “same” behavior, the computation will still “work.”

THE FUNC TIONAL MODEL

The question is what it means to have the “same” behavior. For question-answering, it means giving the same answers to the same questions; that is, generating the same output. We can provisionally think of a computational problem as a function from a set of possible inputs (the questions) to their desired outputs (the answers). If we assume that the only important part of a computation’s behavior is its output, then we have a functional model of computation. Procedures are just ways of computing functions and so two procedures are behaviorally equivalent if and only if they compute the same function, although they may differ in efficiency.

Procedures differ from functions
in that functions only specify what
their outputs should be, whereas pro-
cedures specify how to compute them.
Computer science is in many ways the
study of procedural knowledge: How to
describe procedures, construct them,
and compare competing procedures
for solving the same computational
problem.

THE IMPERATIVE MODEL

The functional model is a pretty good model of what we mean by computation; it covers all of math and a lot of programming. But it assumes computations ( 1) read an input, think for a while, write an output, and halt; and ( 2) the only important aspect of a program’s behavior is the relation bet ween its input and output.

The problem is our arithmetic example, like modern von Neumann computers, worked by gradually modifying scratch paper—writing carries down, partial sums, etc. And the act of writing a carry mark on scratch paper, like the act of storing a register to main memory, isn’t best thought of as computing a function, per se; it is an imperative. It’s an operation that works by modifying the internal state of the machine. So we have the embarrassing situation that our model doesn’t consider the steps of our computations to be computations.

Moreover, many computations just
don’t fit into the functional model.
Does the delete file command on your
laptop produce an output? Not really.
Whereas the modification of memory
may be a side effect of an arithmetic
program, it’s the very purpose of de-
letion; and an animation program’s
purpose is to draw successive frames
to video memory. Nor do all programs
terminate; you actually want your op-
erating system or anti-lock brake con-
troller to be infinite loops! These are
all computations that:
• Are performed mechanically.

• Do something useful.

• Do it using exactly the same primitive instructions that “normal” procedures use.

 

But these aren’t considered computations under the functional model because they don’t compute functions.

There is another model of computation, the imperative model: Computations are sequences of imperatives that manipulate representations. The advantage of this model is that it’s more inclusive than the functional model.