首页 What is computation

What is computation

举报
开通vip

What is computation 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 prev...

What is computation
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,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_436112
暂无简介~
格式:pdf
大小:509KB
软件:PDF阅读器
页数:0
分类:互联网
上传时间:2010-07-11
浏览量:24