Computer Science: Reflections on the Field, Reflections from the Field (2004)

This page intentionally left blank.

Computer science began to emerge as a distinct field in the 1940s and 1950s with the development of the first electronic digital computers. Their creation reflected several coincident factors—the development of computational theory in the 1930s and 1940s, the existence of compelling computational applications (starting with wartime needs such as codebreaking and the calculation of artillery trajectories), and the availability of electronic components with which to implement computers for those applications. A number of mathematicians, engineers, economists, and physicists turned their attention to mastering and enhancing the capabilities of this novel tool. But computers proved so powerful and absorbing, so interesting and open-ended, and so uniquely challenging that many of these people realized, a decade or so later, that they had in fact left their original disciplines and were pioneering a new field.

Computer science embraces questions ranging from the properties of electronic devices to the character of human understanding, from individual designed components to globally distributed systems, and from the purely theoretical to the highly pragmatic. Its research methods are correspondingly inclusive, spanning theory, analysis, experimentation, construction, and modeling. Computer science encompasses basic research that seeks fundamental understanding of computational phenomena, as well as applied research. The two are often coupled; grappling with practical problems inspires fundamental insights. Given this breadth and diversity, the discussion that follows does not aim to explicitly or compre-

hensively define computer science or to catalog all of the research areas. (Indeed, such an effort would inevitably bog down in classifying subdisciplines of the field and declaring interdisciplinary activities as “in” or “out.”) Instead, the approach is to indicate and illustrate the essential character of the field through a sampling of representative topics.

Computer science is the study of computers and what they can do—the inherent powers and limitations of abstract computers, the design and characteristics of real computers, and the innumerable applications of computers to solving problems. Computer scientists seek to understand how to represent and to reason about processes and information. They create languages for representing these phenomena and develop methods for analyzing and creating the phenomena. They create abstractions, including abstractions that are themselves used to compose, manipulate, and represent other abstractions. They study the symbolic representation, implementation, manipulation, and communication of information. They create, study, experiment on, and improve real-world computational and information systems—the working hardware and software artifacts that embody the computing capabilities. They develop models, methods, and technologies to help design, realize, and operate these artifacts. They amplify human intellect through the automation of rote tasks and construction of new capabilities.

Computer hardware and software have been central to computer science since its origins. However, computer science also encompasses the study and more general application of principles and theories rooted in or motivated by hardware and software phenomena. Computer science has thus come to encompass topics once distinctly part of other disciplines, such as mathematics, originally motivated by computing and conceptual questions of information-handling tasks such as natural-language processing. Computer science research is often intimately intertwined with application, as the need to solve practical problems drives new theoretical breakthroughs.

The accompanying essays in this volume elaborate on some important examples of the results of computer science research. These include:

• The Universal Turing Machine and the Church-Turing thesis, which provide a theoretical underpinning for understanding computing (see Kleinberg and Papadimitriou in Chapter 2);

• Computer programs that achieve, exceed, or augment human performance levels in challenging intellectual tasks (see Koller and Bierman and also Mitchell in Chapter 6);

• The theory of algorithms—formal expressions of procedures—which separate algorithmic behavior from the specific code that implements it (see Kleinberg and Papadimitriou in Chapter 2);

• Programming languages, which are notations specifically designed to represent computational processes, or how things happen (see Aho and Larus in Chapter 4);

• The relational model of data, which provided a systematic way to express complex associations among data and revolutionized the database industry and provided the basis for nearly all business computing (see Gray in Chapter 5);

• The Internet, a reliable system created from unreliable parts that defines a simple, general-purpose abstraction of a packet network on which a wide range of applications can be constructed (see Peterson and Clark in Chapter 7);

• Simulation, which permits the study and visualization of both natural and man-made phenomena (see Fedkiw in Chapter 3); and

• Software systems that allow non-experts to use computers (see Foley and also Ullman in Chapter 8).

Computer science’s striking research advances have touched our lives in profound ways as we work, learn, play, and communicate. Even though computer science is a relatively young field, born only within the past seven decades, the pace of innovation in it has been extraordinary. Once esoteric, expensive, and reserved for specialized tasks, computers are now seemingly everywhere. Applications and technologies that are now fixtures in many people’s lives and work (such as office automation, e-commerce, and search engines) were nonexistent or barely visible just a decade ago. The personal computer itself was first introduced less then three decades ago, yet most office workers are now assigned a PC as a matter of course, and roughly half of all households in the United States own at least one. Computers are central to the daily operations of banks, brokerage houses, airlines, telephone systems, and supermarkets. Even more computers lurk hidden inside handheld cell phones, personal digital assistants, and automobiles; for example, a typical midmarket automobile contains a network and dozens of processors. As the size and cost of computer hardware shrink, computers will continue to proliferate even more widely (see Hill in Chapter 2). All these computers have provided society with tremendous social and economic benefits even as they pose new challenges for public policy and social organizations.

Advances in computer science have also led to fundamental changes in many scientific and engineering disciplines, enabling, for example, complex numerical calculations that would simply be infeasible if attempted by hand. Computer science has provided highly useful tools

for controlling experiments, collecting, exchanging, and analyzing data, modeling and simulation, and for sharing scientific information. Indeed, finding the right data structure or algorithm can revolutionize the way in which a scientist thinks about a problem. For example, computer science algorithms made it possible to put together a vast amount of data from sequencing machines when the human genome was sequenced. In recent years, reflecting information’s central importance in scholarly work and science, computing has also taken on new importance in many other disciplines as well; Ayers (in Chapter 5), for example, discusses ways in which historians are using computing. Computer science’s computational paradigm has also shaped new modes of inquiry in other fields, such as genomics and related areas of biology.

One driver of computer science innovation is the doubling of hardware performance that we have seen roughly every 1¹/₂ to 2 years (see Hill in Chapter 2). Another is the invention of myriad new applications of computers, whose creation is made possible by the tremendous flexibility of software. Computer applications are largely limited only by human imagination, although there are fundamental limits on what is computable and there are significant engineering challenges in building complex systems.

This volume explores computer science research, emphasizing how research leads both to deeper understanding of computation and to numerous practical applications. Many others have celebrated the accomplishments of computer science or offered predictions about future directions.¹ The emphasis in this volume is on why and how computer scientists do their research.

Part Two of this volume consists of a set of individually authored essays that provide a sampling of perspectives on several areas of computer science research. These are intended to exemplify some of the observations made in this chapter and illustrate some of the flavor of computer science.

This chapter broadly considers the essential character of computer science (what does computer science investigate, design, and create?), and its methods and modes of research (how do computer scientists

approach problems? what methods do they use? and what types of results emerge?). The discussion below elucidates seven major themes without attempting to fully enumerate all the research subfields within computer science, to prescribe a research agenda, or to define the boundaries of computer science.

The character of a research field arises from the phenomena it seeks to understand and manipulate together with the types of questions the discipline seeks to answer about these phenomena. This section identifies phenomena and intellectual challenges central to computer science, describing the key ideas and the identifying work that has helped to develop those ideas. These broad themes (summarized in Box 1.1), more timeless than a comprehensive inventory of current topics would be, portray core ideas that computer science is concerned with.

Two of the fundamental techniques of computer science research are the manipulation of discrete information and symbolic representation. Some information is inherently discrete, such as money. Discrete approximation enables every kind of information to be represented within the computer by a sequence of bits (choices of 0 or 1) or the often more

convenient bytes (sequences of 8 bits, representing characters such as letters) to which the proper interpretation is applied. A digital image of any one of Van Gogh’s paintings of sunflowers (call it Sunflowers, for short) divides the continuous painted canvas into many small rectangular regions called pixels and gives the (approximate) color at each of these. The collection of pixels can, in turn, be thought of as a sequence of bits. Bit sequences, being a “digital” or discrete-valued representation, cannot fully represent precise, real-valued or “analog” information (e.g., the precise amount of yellow in a sunflower). Practically, though, this apparent limitation can be overcome by using a sufficiently large enough number of bits, to, for example, represent the analog information as precisely as the eye can see or the ear can hear.

This sequence of bits can be processed in one way so that a person can see the Sunflowers image on a display or processed another way for a printer to print an image. This sequence of bits could be sent in an e-mail message to a friend or posted to a Web page. In principle, the same sequence of bits could be passed to an audio interpreter; however, the audio produced by Sunflowers would not sound very good, since this bit sequence is unlikely to represent anything reasonable in the symbol system used by the audio player. Sunflowers could be executed as a program on the computer, since programs are themselves bit strings; again, however, the result will probably not produce anything meaningful, since it is unlikely the painting’s representation is a sequence that will do something useful.

More subtle than discrete approximation, yet more powerful, is the technique of symbolic representation. Here the underlying bits are used to represent symbols in some notation, and that notation is used to represent information in a way that permits analysis and further processing. For example:

• For analysis of differences among sunflowers or between sunflowers and marigolds, flowers could be described in terms of their genetic code.

• For graphical animation, a sunflower might be represented by a description of the color and shape of its parts together with how they are connected to each other.

• To denote different varieties, sunflowers might be represented by a set of symbols consisting of words in English.

The right symbol systems, properly interpreted, allow one to write programs that represent and manipulate sounds or images, that simulate physical phenomena, and even that create artificial systems without an analog in nature.

Several of the essays in this volume deal with symbolic representation. The essay by Kleinberg and Papadimitriou in Chapter 2 discusses the formal representation of computation itself as symbol strings. Lesk in Chapter 5 mentions many of the important kinds of representations being stored in computers as “digital libraries.”

Computer science often involves formulating and manipulating abstractions, which are coordinated sets of definitions that capture different aspects of a particular entity—from broad concept to its detailed representation in bits—and the relations through which some of the definitions refine others or provide additional concepts to help realize others.

One aspect of abstraction is that sequences of bits take on specific useful interpretations that make sense only in particular contexts. For example, a bit sequence can be thought of—in some contexts—as an integer in binary notation; using that abstraction, it makes sense to divide the integer by 3 and get another sequence of bits that is the quotient. But in a context that abstracts bit sequences as images, it would not be reasonable to divide Sunflowers by 3 and get something meaningful, nor would it make sense to divide a DNA sequence by 3. But the abstraction of bits as, for example, images, should permit operations that make no sense on integers, such as cropping (removing bits that represent pixels at the edges of an image) or applying a watercolor filter in an image-manipulation program. Similarly, the abstraction of bits as DNA sequences should permit analysis of differences among plant species that would make no sense for integers or images.

Abstraction also makes it possible to perceive and manipulate the same computer-represented “object” at many levels. Objects at one level make available to higher levels a fixed set of operations, and are perceived by the higher level as if these were the only operations that could ever be performed on them. For example, the bit sequence representing Sunflowers and other paintings could be thought of as part of a relation (two-dimensional table of data), in which each row contains the bits representing an image, another bit sequence representing the name of the painting, a third bit sequence representing the name of the artist, and so on. At the lowest level, there are operations that manipulate the individual entries in each row; for example, the image bit string could be converted to a black and white image by manipulating the color information. At the next level, one considers the entire relation as an object; operations on the relation, rather than manipulating pixels or displaying images, instead perform such operations as “find all the images of paintings by

Van Gogh.” If the image abstraction permitted operations like “tell if this image has a region that the typical person would perceive as a sunflower,” then the relation abstraction would permit searches like “find the names of all paintings with one or more sunflowers in them.” Alas, that sort of operation on images is beyond the state of the art at the beginning of the 21st century. However, operations at the image-level abstraction can be used to determine if an image has a large region of yellowish-orange, and thus to support a question at the level of the table such as “find the names of paintings with large yellow-orange regions.”

As alluded to above, abstractions apply to procedures as well as data. Consider a bit sequence representing a piece of computer code that performs a sequence of operations on Sunflowers. One set of bits might provide the (detailed) machine instructions to display the image on a particular computer. Another set of bits might be the program to animate a model of a sunflower blowing in the breeze—when interpreted by the compiler for that language (and, of course, when the object code is then executed). Yet a third set of bits might be in an animation language that permits the motion of a sunflower to be described at a high level.

The print function common across applications on most systems today, which allows a wide range of data objects to be printed on a wide range of printers, is a powerful example of abstraction. The user need not know about all the details hiding behind this simple interface—the “print” command is an abstraction that shows the user only what he or she needs to see.

In each case, the bits are interpreted by a model that abstracts procedures above the actual machine instructions that a computer executes. Observe also that bits can at the same time be both data and procedure—the compiler reads a program to produce an output (data) that will later be executed by a computer (procedure).

The Internet works today because of abstractions that were products of the human imagination. Computer scientists imagined “packets” of information flowing through pipes, and they (symbolically) worked out the consequences of that idea to determine the new laws those flows of information must obey. This conceptualization led to the development of protocols that govern how data flows through the Internet, what happens when packets get lost, and so on. The Internet’s constructs extend well beyond mathematics or models to high-level design principles such as keeping the network core simple and keeping detailed functionality at the edges. The power of a good abstraction is illustrated by the fact that the Internet’s basic protocols have reliably carried traffic on the network since its creation, even as this traffic has changed enormously not just in scale but also in behavior, from e-mail to streaming media and peer-to-peer file sharing networks.

In Part Two, Shaw (in Chapter 4) presents abstractions as a key idea in software design. The essay by Aho and Larus (in Chapter 4) discusses how the abstractions in computer languages bridge the gap between computer hardware and humans. Programming languages offer ways to encapsulate the details of algorithms and define procedural and data abstractions that allow the algorithms to be used without knowledge of their details. Peterson and Clark (in Chapter 7) discuss the important abstractions of the Internet, and Gray (in Chapter 5) covers abstractions that have proved especially useful for representing data.

Often, computing research is less about how to represent static objects (such as an image or a driver’s-license record) and more about developing and studying algorithms (precise ways to do a particular task) that will perform operations on objects. With respect to images, such operations might include cropping an image, finding boundaries between regions of different color or texture, or telling whether an image has at least 20 percent of its colors between yellow and orange. Given a symbolic representation of a sunflower as a set of measurements and some assumptions about the strength of the stem and the force of a breeze, a virtual reality algorithm could display that sunflower swaying in the breeze. Programming languages offer ways to encapsulate the details of these algorithms and define procedural abstractions that allow the algorithms to be used without requiring knowledge of their details.

Computer science also concerns itself with the amount of time an algorithm takes (its running time), and some computer scientists try to find algorithms that take less time than others to do similar things, sometimes dramatically reducing the time required. It would not do if, for example, it took all day to tell if a typical-sized image were 20 percent yellow. Sometimes, such research yields major breakthroughs that offer order-of-magnitude improvements in the time required to solve a particular type of problem.

Part Two includes a discussion of programming languages in Aho and Larus (in Chapter 4) and a treatment of algorithms and their running time in Kleinberg and Papadimitriou (in Chapter 2). Indeed, essentially all the essays in this volume mention algorithms and/or programming-language representations for one or another kind of information.

Animated sunflowers blowing in the breeze are an example of how the computational world can mimic, at an extremely accurate level, the

behavior of the real world. While computer scientists often addresses the world as it is, computer science also deals with the world as it could be, or with an entirely invented world behaving under different assumptions. Computer scientists can, for example, easily change the rules, making water more viscous or weakening the effect of gravity. For example, videogame characters often obey physical laws that have never been seen in nature (“Roadrunner physics”). Computational models also describe complex natural phenomena that are hard to observe in nature. Such models can describe both natural and unnatural worlds. For example, it is entirely possible to make ocean waves a bit more exciting to watch by altering gravity or the viscosity of water—changes impossible in the laboratory but routine within the world of computing.

Fedkiw (in Chapter 3) describes how computer-generated animation produces such images as the waves in the movie The Perfect Storm. Peterson and Clark (in Chapter 7) describe the Internet model. Bruckman (in Chapter 7) examines online virtual communities.

The speed of light doesn’t change at all, and DNA strands have grown in length only over geologic time. But computer science must deal with machines that, by various measures of size and speed (for fixed cost), double in performance roughly every 1¹/₂ to 2 years (see the essay on Moore’s law by Hill in Chapter 2).² Although these performance improvements make it easier for computer scientists to solve some problems, they can also magnify computer and system design challenges. Over time, the critical resource to be optimized changes; designers today must take into account that obtaining two numbers from a computer’s main memory can take a hundred times longer than multiplying them together whereas just the opposite was once true. Moreover, the improvements create commensurate demands that the machines be used to solve ever more complex problems and larger or harder instances of the same problem and that ever-larger systems be built.

Computer scientists have a rule of thumb that every time things get 10 times larger or faster a qualitatively different class of research challenges emerges. To get a sense of this, suppose you are playing bridge, and you need to examine your hand to see whether you hold no cards of the suit being played, and therefore are allowed to trump the trick. Since your hand consists of at most 13 cards at any time, you can usually figure it out quickly by scanning each of your cards. But suppose bridge were played with hands of a million cards, with 10,000 suits, each of 100 ranks. Could you figure out which card to play before your opponents got up to get a snack? Computers deal with similar situations all the time, and to avoid scanning all 1,000,000 cards, organizations for data have been devised that allow us to design algorithms that home in on the desired card much more quickly than can the obvious “scan all cards” algorithm.

The expectation of rapid improvement in capabilities leads to a form of research, perhaps unique to computer science, sometimes called “living in the future.” Although almost every technology goes through some period of exponential growth, computers are remarkable because the doubling time is unusually short and the exponential growth period has been unusually long. As a result, it often makes sense to think about what the world will be like when computing machines are 10 times faster, or able to communicate with 100 times the bandwidth. Certain things that one cannot now do, or cannot do for a reasonable cost, are suddenly going to become possible. Many research successes that turned into successful products were the result of such confident, forward thinking.

In addition to Hill’s, many of the essays in this volume show how computer science research has both exploited the exponential improvement in our tools and dealt with the exponential growth in requirements. The essay by Koller and Biermann (in Chapter 6) examines chess playing, where the goals of being able to defeat better and better players have largely been met. Peterson and Clark (in Chapter 7) show how we are coping with the ever-growing Internet.

In addition to developing knowledge that supports practical engineering applications, computer science investigates fundamental limits regarding computation. It has been known since the 1930s that there are undecidable problems, those that can be stated succinctly yet cannot be answered. The canonical example of these is, can you write a computer program that given an arbitrary program P and arbitrary input N to that program, can answer the question, does the program P ever stop running when given the input N? The discovery that the answer to this question is

no is fundamental in the sense that it applies to all possible programs rather than being a statement about a particular piece of programming code.

Perhaps more important is the discovery that not everything that is decidable (a computer can solve it, somehow) is tractable (solvable in sufficiently little time that we can expect to get answers to reasonably large instances of the problem in reasonable time). Some problems, such as searching for cards described above, are tractable. Even the dumb algorithm of examining each one of n cards in one’s hand would only take time proportional to n. However, there are other problems that are not tractable—where time or computing resources proportional to the size of the instance to be solved are insufficient. Instead, they require time or resources that are exponential in the size of the input n—that is, time that grows like 2ⁿ. This sort of analysis extends more generally to how the required computing resources relate to the nature and structure of a problem as well as its size. For some types of problems, the issue is how accurately something can be computed; here computer science seeks an understanding of the fundamental limits in the accuracy of what can be computed and the accuracy of what can be computed quickly (as in approximation algorithms).

An example of a tractability problem is the Traveling Salesman Problem (TSP), where one is given n “cities” (nodes of a graph) with distances between each pair. The goal is for the salesman (who, following our earlier example, is selling sunflower oil) to visit each city once and return to the starting city, but minimize the total distance traveled. An obvious solution, starting from one of the n cities, has n – 1 choices for the first city, n – 2 choices for the next, and so on, a total of (n – 1)(n – 2) … (2)(1) choices. Unfortunately, this number of choices grows faster than 2ⁿ. What is worse, the theory of intractable problems provides powerful evidence that there is no way to solve the TSP in substantially less time. As a result, even the exponential improvement in the speed of computers (“Moore’s law,” as mentioned above) can do almost nothing to increase the size of problem instance that can be dealt with; perhaps one can handle a few more cities each year, at best. Of course, even when it is impractical to solve a problem generally and optimally, the situation is not necessarily hopeless. In practice, salesmen can make their rounds fairly efficiently because algorithms that do well enough most of the time have been discovered.

The fundamental limit on our ability to compute applies not only to the TSP, but also to thousands of problems encountered daily. That is, one can solve these problems by computer only when the problem instance is rather small, and the situation can never get much better. Research on

fundamental limits thus informs practical application, by showing that some system designs are ultimately a dead end.

In Part Two, Kleinberg and Papadimitriou (in Chapter 2) provide a discussion of the precise implications of the theory of intractable problems, and Sudan (in Chapter 7) discusses cryptography, a domain where the intractability of a problem is a help, not a hindrance, because the goal is assurance that an intruder with a fast computer cannot discover secrets within any reasonable amount of time.

One aspiration of computer science has been to understand and emulate capabilities that are associated with intelligent human behavior. One class of these activities is devoted to enabling computers to solve problems that humans can solve easily, yet that appear very difficult for machines. A human can easily pick out the presence of a sunflower in an image, and yet a computer of the early 21st century can do so only with difficulty and limited accuracy. The problems of image understanding, language understanding, locomotion, game playing, and problem solving each provide enormous challenges for the computer scientist. A second class of intelligence-related research is to understand how the human mind works by trying to solve problems the way humans do. It turns out, for example, that the simple “if A then B” logic harking back to Aristotle does not capture nearly enough of the way people think and make inferences about their environment. A third class of intelligence-related research is enabling computers to interact with the world by enabling them to sense the environment, move within it, and manipulate objects.

These efforts are elaborated in several of the essays. In Chapter 6, Koller and Biermann discuss game playing by computer as a testbed for approaches that emulate intelligence. Lee tells about approaches to computer understanding of natural language. Mitchell explores the development of machine-learning techniques.

Part Two of this volume explores some of the depth and breadth of computer science through essays written by computer scientists. The essays provide several researchers’ own views about their research areas and convey what excites these researchers about computer science.

This page intentionally left blank.