Draft of November 1, 2008: comments welcome
Copyright © Ian Horswill 2007, 2008 ian@northwestern.edu
What is computation?
In the 19th century, our society fundamentally changed the way it produced material goods.
Whereas production had previously depended on human and animal labor, the steam engine
allowed much of that labor to be transferred to machines. This made the manufacture of many
goods and services more efficient, and therefore cheaper. It made other kinds of products
available that would otherwise have been impossible to manufacture. At the same time, it
caused widespread economic dislocation, putting many skilled tradesmen out of work and
forcing much of the population to leave their rural communities for cities, radically changing the
very environment they lived in. Consumer culture, television, corporations, and the automobile,
would not have been possible, or at least as influential, without this automation of production,
better known as the industrial revolution.
We now hear we’re in the midst of an “information revolution.” Like the industrial revolution, it
involves automation – the transfer of human labor to machines. However, this revolution
involves not physical labor, but intellectual labor. While we cannot know the ultimate
consequences of these changes, information technology has played an increasingly central role
in our society over the last two decades. In the 1950s, if you and your friends wanted to go to a
movie, you wouldn’t have started by walking to the library. But today you wouldn’t think twice
about checking the internet for reviews and show times. Similarly, average people wouldn’t
have published their diaries in the 1950s, but today people blog about everything from
international politics to their pets’ favorite toys.
Yet for all the importance of these technologies, people still tend to think of computation as
being about numbers, and computer science as being about the esoteric worship of acronyms
and punctuation.
Computation isn’t tied to numbers, acronyms, punctuation, or syntax. But one of the things that
makes it so interesting is that, in all honesty, it’s not entirely clear what computation really is.
We all generally agree that when someone balances their checkbook, they’re doing
computation. But many people argue that the brain is fundamentally a computer. If that’s true,
does it mean that (all) thought is computation? Or that all computation is thought? We know
that the “virtual” environments in computer games are really just computational simulations.
But it’s also been argued that the real universe is effectively a computer, that quantum physics
Draft of November 1, 2008: comments welcome
Copyright © Ian Horswill 2007, 2008 ian@northwestern.edu
is really about information, and that matter and energy are really just abstractions built from
information. But if the universe is “just” computation, then what isn’t computation? And what
does it even mean to say that something is or isn’t computation?
Computation is an idea in flux; our culture is in the process of renegotiating what it means by
the term. One hundred years ago, nearly everyone thought of computation as being a mental
operation involving numbers. And being a mental operation, it could only be done by people.
Today, the overwhelming majority of what we consider to be computation is done by machines.
But at the same time, we still somehow associate it with thought. In Western culture, we tend
to take our capacity for thought as the central distinction between ourselves and other animals.
Moreover, we view our specific thoughts and feelings as being one of the major constituents of
our personal identity. So thought is constitutive both of our collective humanity and of our
individual identities.
Changing our ideas about computation changes our ideas about thought and so 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.
Questions and answers
I’ve said that computation isn’t fundamentally about numbers. Nevertheless, let’s start by
thinking about arithmetic, since we can all agree that it’s an example of computation. Suppose
you ask someone:
“What’s seven plus three?”
If they reply “ten,” 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 we do as being a “mental” thing that takes place “in” our heads. But
Draft of November 1, 2008: comments welcome
Copyright © Ian Horswill 2007, 2008 ian@northwestern.edu
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 re‐presented them as symbols on paper, presumably
Arabic numerals.1
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:
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 functional model
Let’s try to be more precise about what we mean by saying computation is a kind of question
answering. First of all, there are different kinds of computation problems. So it’s fair to ask an
adding machine what 3+7 is, but not what the capital of India is. The ability to do a task like
addition is roughly the ability to answer a certain prescribed set of questions with the correct
answer. So we can think of a computational problem as a set of possible questions, each of
which has a desired correct answer.
1 In fact, “the numbers themselves” never even made an appearance, since they’re completely intangible; we only have access to
them through representations.
speech speech
writing writing
add1
add2
write read
Draft of November 1, 2008: comments welcome
Copyright © Ian Horswill 2007, 2008 ian@northwestern.edu
In the case of addition questions, the only relevant parts of the question are the numbers to be
added. For an adding machine, the “what is the sum of” part of an addition question is
irrelevant because that’s the only kind of question it can answer. So we’ll dispense with the
irrelevant parts and just say the question consists of the relevant bits, in this case the pair of
numbers to be added. Similarly, we’ll distill the answer down to just a number.
So while we still don’t know what computation is in the abstract, we can at least say something
about what we mean by a computational problem. It’s a group of related questions, each of
which has a corresponding desired answer. We’ll call the information in the specific question
the input value(s) and the desired answer the output value. For any input, there is a
corresponding desired output. The notions of input and output are the most basic concepts of
computation: computation is – for the moment – the process of deriving the desired output
from a given input(s).
If you’ve taken the right math courses, then you may realize that what we’re calling “a
computational problem” is the same as what mathematicians call a function. A function is just
a specification of output values for any given input value(s). Sine and cosine are functions; they
specify output values (numbers) for every possible input number. Addition is also a function,
but of two inputs rather than one. And more esoteric operations in mathematics, like the
derivative can also be thought of as functions, although they’re functions whose inputs are
themselves other functions. But functions don’t have to be about numbers. For example, an
MP3 player computes a function whose input is a compressed song and whose output is an
audio waveform.
A procedure (aka an algorithm, program, routine, or subroutine) is a specific method for
determining an output value from a set of input values. Assuming the procedure always
produces the same output for a given set of inputs (e.g. it doesn’t involve rolling dice or other
non‐deterministic operations), then it “acts like” a function in that it has a strict correspondence
between inputs and outputs. The difference between procedures and functions is that
functions only specify what their outputs are, whereas a procedure specifies how to compute
them. There are typically many different procedures for computing a given function, but as we
shall see, there are some functions we can’t compute. We can provisionally think of Computer
Science as the study of procedural knowledge: how to describe procedures, construct them,
and compare competing procedures for computing the same function.
We’ve been assuming here that the only important part of a procedure’s behavior is its output.
We’ll call this the functional model of computation: procedures are 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 the resources they require such as length of time or
amount of scratch paper). This is a limited view of computation, but it covers a surprising
amount of ground. Remember that the inputs and outputs of our functions don’t have to be
numbers. They can perfectly well be things like MP3 files or images from a web cam.
Draft of November 1, 2008: comments welcome
Copyright © Ian Horswill 2007, 2008 ian@northwestern.edu
Procedures
Let’s consider one last arithmetic example. Suppose you’re at a restaurant and want to leave a
20% tip. As a computational problem, this involves taking a number as input and computing
20% of it. If we call the input c for “check”, then were computing the function:
tip(c) = 0.2×c
Most people aren’t especially good at computing percentages in their heads because it involves
multiplying multi‐digit numbers; if I asked you what 73% was of 151.05, you’d probably have to
take out pencil and paper or use a calculator. But 20% has the useful property that we can use
the following procedure:
1. Double the number
2. Erase the last digit
(assuming the bill and tip are whole numbers)
This is much easier because most people can double numbers of a few digits in their heads,
whereas computing higher multiples is harder for them. On the other hand, it’s assumes we
represent the number as a string of decimal digits so that removing a digit divides the number
by ten. If the wait person writes the check in Roman numerals, you’re out of luck (quick: what’s
XX% of MMCMXLIV?).
Representation
In practice, inputs and outputs are always encoded in some specific representation. Often, we
can ignore which representation is used and just think about the procedure as manipulating the
“information” in the input rather than as manipulating the components of a specific
representation. Consequently, computation is often referred to as information processing and
the computing industry as the information technology industry. However, as this example
shows, the choice of representation can affect our choice of algorithm. Consequently,
Computer Science is also very concerned with studying the properties of different kinds of
representations or data structures.
Part of the reason representation matters is that it affects what simpler procedures you can take
for granted. Procedures are always written in terms of other simpler procedures. In the
algorithm above, we assumed the reader already knew how to double a number and how to
erase a digit, since those are relatively easy to do in decimal notation. However, if we were
teaching it to a child who hadn’t learned multiplication, we might instead say:
1. Add the number to itself
2. Erase the last digit
This is technically a different procedure, since it replaces multiplication with addition, but since
it computes the same output, it’s behaviorally equivalent to the original one.
Draft of November 1, 2008: comments welcome
Copyright © Ian Horswill 2007, 2008 ian@northwestern.edu
Now suppose the child hasn’t learned to do multi‐digit
addition, and yet we still want them to compute our tip
for us, perhaps as torture of a younger sibling. Then we
could say:
1. Start with the last digit
2. Add it to itself
3. If the result is more than ten, then write the 1
above the next digit
4. If there are any digits left
a. Move to the next digit
b. Go to step 2, remembering to add in
the 1 above it, if you carried a 1 over
5. Otherwise, erase the last digit
This procedure explains computing a 20% tip on a
multi‐digit number in terms of single‐digit addition. But
suppose the poor child can’t add, but can only count,
yet is inexplicably eager to please you, their sadistic
older sibling. Then we could tell the poor child to:
1. Start with the last digit
2. Add it to itself by doing the following
a. Write a 0 underneath it
b. If the number underneath is the same
as the digit that we started with, then
go to step e
c. Count each number up by one
d. Go back to step b
e. If there was a carry written above the
original digit, then count it up one
more time
6. If the result is more than ten, then write the 1
above the next digit
7. If there are any digits left
a. Move to the next digit
b. Go to step 2, remembering to add in
the 1 above it, if you carried a 1 over
8. Otherwise, erase the last digit
But of course, to do that, you would have to be really
sadistic.
Levels of abstraction
We described multiplication in
terms of addition, which broke
down into adding digits, and then
counting. In practice, we would
make this explicit by describing
procedures in terms of sub‐
procedures:
• To double a number: add
it to itself
• To add two numbers: add
the last digits, then add
the next digits, with the
carry, etc.
• To add two digits:
repeatedly add 1 to one
while subtracting one
from the other until the
second digit is zero.
If we were to diagram all the
procedures involved, it might look
like this:
Most programs break up into
layers like this. Procedures are
built “on top of” simpler
procedures, which usually are built
on top of still simpler procedures,
until we get down to the level of
the primitive operations that the
computer’s hardware can execute
directly. However, you can never
describe a procedure
“completely”; you can only
describe it in terms of other
procedures the reader already
understands.
Draft of November 1, 2008: comments welcome
Copyright © Ian Horswill 2007, 2008 ian@northwestern.edu
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 that computations always read an input, think
for a while, write an output, and then stop. The only aspect of a program’s behavior the
functional model is concerned with is the relation between its input and its output; it considers
procedures that generate the same output for the same inputs to be behaviorally equivalent.
On the other hand, the steps of our tip computing procedures involve scribbling on scratch
paper. In fact, they basically work by gradually accumulating scribbles until the answer is on the
page. And those individual steps of writing, erasing, and re‐writing the scratch paper aren’t
necessarily best thought of as computations in this sense of having specific inputs and outputs.
As it happens, computers work internally in much the same way; their fundamental operations
involve reading, writing, and erasing locations on what amounts to electronic scratch paper.
But what about this procedure:
1. Draw an X at the top of the page
2. Draw an X under the current X
3. Erase the X above the new X
4. If the new X isn’t at the bottom of the page, go to step 2
5. Draw an X on top of the current X
6. Erase the X below the new X
7. If the new X is at the top of the page, go to step 2, otherwise to step 5
This is effectively a simple animation procedure. It makes an X move up and down on the
screen, or in this case, the paper. It never produces an output in the sense of the functional
model of computation. In fact, it never even stops running. So we have a procedure that:
• Can be followed mechanically
• Does something useful, and
• Does it using exactly the same techniques that “normal” procedures use
Yet it isn’t considered a computation under the functional model because it doesn’t compute a
function per se.
Clearly the functional model’s narrow limitation of a program’s behavior to its output is a
significant limitation.2 Many programs don’t return results in the usual sense. The software on
your cell phone never stops running, or so one hopes. Similarly, when you use a backup
program to make copies of your files, the program’s modification of your backup medium isn’t
2 This is somewhat unfair to the functional view. It’s easy to make other functional models of computation that can embrace this
kind of computation. Our purpose here is not to choose one model over another, but to draw attention to two different ways of
thinking about computation.
Draft of November 1, 2008: comments welcome
Copyright © Ian Horswill 2007, 2008 ian@northwestern.edu
an incidental side‐effect of the program, as it was when computing a tip; it’s the whole reason
for the program.
Program steps that involve modifying the computer’s memory or taking some action in the
world are called commands or imperatives3. In practice, the basic instructions followed by your
computer are imperatives. Programs are sequences of imperatives that the computer executes
in order. As in our tip calculating example, imperatives can be strung together to compute a
function. But as with the backup program example, they can also just be strung together to
manipulate the computer’s memory in a manner we find useful.
This gives us another model of what computation is, which we’ll call the imperative model:
procedures are sequences of
本文档为【What is computation】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。