National Academies Press: OpenBook
Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×

Computer Science

Reflections on the Field, Reflections from the Field

Committee on the Fundamentals of Computer Science:Challenges and Opportunities

Computer Science and Telecommunications Board

NATIONAL RESEARCH COUNCIL OF THE NATIONAL ACADEMIES

THE NATIONAL ACADEMIES PRESS
Washington, D.C. www.nap.edu

Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×

THE NATIONAL ACADEMIES PRESS
500 Fifth Street, N.W. Washington, DC 20001

NOTICE: The project that is the subject of this report was approved by the Governing Board of the National Research Council, whose members are drawn from the councils of the National Academy of Sciences, the National Academy of Engineering, and the Institute of Medicine. The members of the committee responsible for the report were chosen for their special competences and with regard for appropriate balance.

Support for this project was provided by the National Science Foundation under grant No. CCR-9981754. Any opinions, findings, conclusions, or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the sponsor.

International Standard Book Number 0-309-09301-5 (Book)

International Standard Book Number 0-309-54529-3 (PDF)

Copies of this report are available from the
National Academies Press,
500 Fifth Street, N.W., Lockbox 285, Washington, DC 20055; (800) 624-6242 or (202) 334-3313 in the Washington metropolitan area; Internet, http://www.nap.edu.

Copyright 2004 by the National Academy of Sciences. All rights reserved.

Printed in the United States of America

Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×

THE NATIONAL ACADEMIES

Advisers to the Nation on Science, Engineering, and Medicine

The National Academy of Sciences is a private, nonprofit, self-perpetuating society of distinguished scholars engaged in scientific and engineering research, dedicated to the furtherance of science and technology and to their use for the general welfare. Upon the authority of the charter granted to it by the Congress in 1863, the Academy has a mandate that requires it to advise the federal government on scientific and technical matters. Dr. Bruce M. Alberts is president of the National Academy of Sciences.

The National Academy of Engineering was established in 1964, under the charter of the National Academy of Sciences, as a parallel organization of outstanding engineers. It is autonomous in its administration and in the selection of its members, sharing with the National Academy of Sciences the responsibility for advising the federal government. The National Academy of Engineering also sponsors engineering programs aimed at meeting national needs, encourages education and research, and recognizes the superior achievements of engineers. Dr. Wm. A. Wulf is president of the National Academy of Engineering.

The Institute of Medicine was established in 1970 by the National Academy of Sciences to secure the services of eminent members of appropriate professions in the examination of policy matters pertaining to the health of the public. The Institute acts under the responsibility given to the National Academy of Sciences by its congressional charter to be an adviser to the federal government and, upon its own initiative, to identify issues of medical care, research, and education. Dr. Harvey V. Fineberg is president of the Institute of Medicine.

The National Research Council was organized by the National Academy of Sciences in 1916 to associate the broad community of science and technology with the Academy’s purposes of furthering knowledge and advising the federal government. Functioning in accordance with general policies determined by the Academy, the Council has become the principal operating agency of both the National Academy of Sciences and the National Academy of Engineering in providing services to the government, the public, and the scientific and engineering communities. The Council is administered jointly by both Academies and the Institute of Medicine. Dr. Bruce M. Alberts and Dr. Wm. A. Wulf are chair and vice chair, respectively, of the National Research Council.

www.national-academies.org

Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×

This page intentionally left blank.

Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×

COMMITTEE ON THE FUNDAMENTALS OF COMPUTER SCIENCE: CHALLENGES AND OPPORTUNITIES

MARY SHAW,

Carnegie Mellon University,

Chair

ALFRED V. AHO,

Columbia University

CHARLES H. BENNETT,

IBM Research

ALAN BIERMANN,

Duke University

EDWARD W. FELTEN,

Princeton University

JAMES D. FOLEY,

Georgia Institute of Technology

MARK D. HILL,

University of Wisconsin at Madison

JON M. KLEINBERG,

Cornell University

DAPHNE KOLLER,

Stanford University

JAMES R. LARUS,

Microsoft Research

TOM M. MITCHELL,

Carnegie Mellon University

CHRISTOS H. PAPADIMITRIOU,

University of California, Berkeley

LARRY L. PETERSON,

Princeton University

MADHU SUDAN,

Massachusetts Institute of Technology

KEVIN J. SULLIVAN,

University of Virginia

JEFFREY D. ULLMAN,

Stanford University and Gradience Corporation

Staff

JON EISENBERG, Senior Program Officer and Study Director

LYNETTE I. MILLETT, Program Officer

D.C. DRAKE, Senior Project Assistant (through November 2003)

Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×

COMPUTER SCIENCE AND TELECOMMUNICATIONS BOARD

DAVID LIDDLE,

U.S. Venture Partners,

Co-Chair

JEANNETTE M. WING,

Carnegie Mellon University,

Co-Chair

ERIC BENHAMOU,

3Com Corporation

DAVID D. CLARK,

Massachusetts Institute of Technology, CSTB Member Emeritus

WILLIAM DALLY,

Stanford University

MARK E. DEAN,

IBM Systems Group

DEBORAH L. ESTRIN,

University of California, Los Angeles

JOAN FEIGENBAUM,

Yale University

HECTOR GARCIA-MOLINA,

Stanford University

KEVIN KAHN,

Intel Corporation

JAMES KAJIYA,

Microsoft Corporation

MICHAEL KATZ,

University of California, Berkeley

RANDY H. KATZ,

University of California, Berkeley

WENDY A. KELLOGG,

IBM T.J. Watson Research Center

SARA KIESLER,

Carnegie Mellon University

BUTLER W. LAMPSON,

Microsoft Corporation, CSTB Member Emeritus

TERESA H. MENG,

Stanford University

TOM M. MITCHELL,

Carnegie Mellon University

DANIEL PIKE,

GCI Cable and Entertainment

ERIC SCHMIDT,

Google Inc.

FRED B. SCHNEIDER,

Cornell University

WILLIAM STEAD,

Vanderbilt University

ANDREW J. VITERBI,

Viterbi Group, LLC

CHARLES BROWNSTEIN, Director

KRISTEN BATCH, Research Associate

JENNIFER M. BISHOP, Program Associate

JANET BRISCOE, Administrative Officer

JON EISENBERG, Senior Program Officer

RENEE HAWKINS, Financial Associate

MARGARET MARSH HUYNH, Senior Project Assistant

HERBERT S. LIN, Senior Scientist

LYNETTE I. MILLETT, Program Officer

JANICE SABUDA, Senior Project Assistant

BRANDYE WILLIAMS, Staff Assistant

For more information on CSTB, see its Web site at <http://www.cstb.org>, write to CSTB, National Research Council, 500 Fifth Street, N.W., Washington, DC 20001, call at (202) 334-2605, or e-mail the CSTB at cstb@nas.edu.

Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×

Preface

The blossoming of computer science (CS) research is evident in the information technology that has migrated from a specialized tool confined to the laboratory or corporate back office to a ubiquitous presence in machines and devices that now figure in the lives of virtually every individual. This widespread diffusion of information technology can obscure the nature of computer science research underlying the IT—from the perspective of many outside the field, computer science is seen not as a basic area of systematic inquiry but as a tool to support other endeavors.

Mindful of these issues, the National Science Foundation’s Computer and Information Science and Engineering Directorate asked the Computer Science and Telecommunications Board of the National Academies to conduct a study that would improve understanding of CS research among the scientific community at large, policymakers, and the general public. By describing in accessible form the field’s intellectual character and by conveying a sense of its vibrancy through a set of examples, the committee also aims to prepare readers for what the future might hold and inspire CS researchers to help create it.

This volume, the product of that study, is divided into two parts that contain nine chapters.

The volume’s prelude, “Emily Shops at VirtualEmporia.com,” takes a now-familiar use of computing—shopping online—and illustrates how CS research has made this seemingly simple activity possible.

Page viii Cite
Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×

Part OneChapter 1, “The Essential Character of Computer Science”—offers the committee’s concise characterization of CS research. Like CS researchers more generally, the committee members evince a wide range of perspectives that mirror the broad reach of computation into the very fabric of our intellectual and physical lives. Recognizing the richness and diversity of the field, the committee expressly decided not to provide either a comprehensive list of research topics or a taxonomy of research areas, nor to develop criteria for what research is inside and outside of CS. Instead, the committee’s approach is to describe some key ideas that lie at the core of CS but not to define boundaries.

Part Two—Chapters 2 through 9—comprises two dozen essays written by committee members, participants in a June 6-7, 2001, symposium organized by the committee, and other invited authors. The essays describe several aspects of CS research and some of the results from the perspectives of their authors. By providing this diverse set of views on CS research, the committee aims to express some of the spark that motivates and excites CS researchers. The essays have a deliberately historical focus, for three reasons: (1) as described above, the committee decided not to present a research agenda, either explicit or implicit; (2) other publications look at current, hot topics in CS and these tend, in any case, to become dated quickly; and (3) results that have proven durable best illustrate the strengths of CS.

The prelude and Part One are intended to be accessible to all readers (as are many of the essays). But because this report is also intended to reach scientists and engineers from a variety of disciplines, a few of the essays do presume some familiarity with some technical concepts.

The committee would like to thank all of the participants in the June 2001 symposium; presentations and informal discussions at that event provided important input to the committee. Julie Sussman, PPA, provided a number of helpful suggestions concerning the manuscript. The reviewers listed below provided many valuable suggestions for improvement.

Mary Shaw, Chair

Committee on the Fundamentals of Computer Science: Challenges and Opportunities

Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×

Acknowledgment of Reviewers

This report has been reviewed in draft form by individuals chosen for their diverse perspectives and technical expertise, in accordance with procedures approved by the National Research Council’s Report Review Committee. The purpose of this independent review is to provide candid and critical comments that will assist the institution in making its published report as sound as possible and to ensure that the report meets institutional standards for objectivity, evidence, and responsiveness to the study charge. The review comments and draft manuscript remain confidential to protect the integrity of the deliberative process. We wish to thank the following individuals for their review of this report:

David D. Clark, Massachusetts Institute of Technology

Robert L. Constable, Cornell University

Ronald Fedkiw, Stanford University

Joan Feigenbaum, Yale University

Juris Hartmanis, Cornell University

James Jay Horning, Intertrust

Anna R. Karlin, University of Washington

Richard Karp, University of California, Berkeley

Wendy A. Kellogg, IBM Research

Monica S. Lam, Stanford University

Butler W. Lampson, Microsoft Research

Fred B. Schneider, Cornell University

Lynn Andrea Stein, Olin College

Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×

Gerald Jay Sussman, Massachusetts Institute of Technology

Thomas N. Theis, IBM T.J. Watson Research Center

Jeanette M. Wing, Carnegie Mellon University

Margaret H. Wright, New York University

Although the reviewers listed above provided many constructive comments and suggestions, they were not asked to endorse the conclusions or recommendations nor did they see the final draft of the report before its release. The review of this report was overseen by Lawrence Snyder, University of Washington. Appointed by the National Research Council, he was responsible for making certain that an independent examination of this report was carried out in accordance with institutional procedures and that all review comments were carefully considered. Responsibility for the final content of this report rests entirely with the authoring committee and the institution.

Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×

PART TWO
SELECTED PERSPECTIVES ON COMPUTER SCIENCE

 

25

2

 

EXPONENTIAL GROWTH, COMPUTABILITY, AND COMPLEXITY

 

27

   

 Harnessing Moore’s Law,
Mark D. Hill, University of Wisconsin, Madison

 

28

   

 Computability and Complexity,
Jon Kleinberg, Cornell University, and Christos Papadimitriou, University of California, Berkeley

 

37

   

 Quantum Information Processing,
Charles H. Bennett, IBM Research

 

51

3

 

SIMULATION

 

57

   

 The Real Scientific Hero of 1953,
Steven Strogatz, Cornell University

 

58

   

 Making a Computational Splash,
Ronald Fedkiw, Stanford University

 

61

4

 

ABSTRACTION, REPRESENTATION, AND NOTATIONS

 

65

   

 Abstraction: Imposing Order on Complexity in Software Design,
Mary Shaw, Carnegie Mellon University

 

66

   

 Programming Languages and Computer Science,
Alfred V. Aho, Columbia University, and James Larus, Microsoft Research

 

74

5

 

DATA, REPRESENTATION, AND INFORMATION

 

79

   

 Database Systems: A Textbook Case of Research Paying Off,
Jim Gray, Microsoft Research

 

80

   

 Computer Science Is to Information as Chemistry Is to Matter,
Michael Lesk, Rutgers University

 

88

   

 History and the Fundamentals of Computer Science,
Edward L. Ayers, University of Virginia

 

96

6

 

ACHIEVING INTELLIGENCE

 

101

   

 The Experiment-Analyze-Generalize Loop in Computer Science Research: A Case Study,
Tom Mitchell, Carnegie Mellon University

 

103

   

 “I’m Sorry Dave, I’m Afraid I Can’t Do That”: Linguistics, Statistics, and Natural-Language Processing Circa 2001,
Lillian Lee, Cornell University

 

111

Page xiii Cite
Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×
   

 Computer Game Playing: Beating Humanity at Its Own Game,
Daphne Koller, Stanford University, and Alan Biermann, Duke University

 

119

7

 

BUILDING COMPUTING SYSTEMS OF PRACTICAL SCALE

 

127

   

 The Internet: An Experiment That Escaped from the Lab,
Larry Peterson, Princeton University, and David Clark, Massachusetts Institute of Technology

 

129

   

 Many-to-Many Communication: A New Medium,
Amy Bruckman, Georgia Institute of Technology

 

134

   

 Cryptography,
Madhu Sudan, Massachusetts Institute of Technology

 

144

   

 Strategies for Software Engineering Research,
Mary Shaw, Carnegie Mellon University

 

151

8

 

RESEARCH BEHIND EVERYDAY COMPUTATION

 

159

   

 How You Got Microsoft Word,
Jeffrey Ullman, Stanford University and Gradience Corporation

 

161

   

 VisiCalc, Spreadsheets, and Programming for the Masses, Or “How a Killer App Was Born,”
James D. Foley, Georgia Institute of Technology

 

167

   

 Internet Searching,
Peter Norvig, Google Inc.

 

174

9

 

PERSONAL STATEMENTS OF PASSION ABOUT COMPUTER SCIENCE RESEARCH

 

179

   

 The Legacy of Computer Science,
Gerald Jay Sussman, Massachusetts Institute of Technology

 

180

   

 Fairy Tales,
Allen Newell, Carnegie Mellon University

 

184

   

 Revisiting “What Is Computer Science,”
Allen Newell, Carnegie Mellon University

 

189

APPENDIX
Agenda of July 25-26, 2001, Symposium

 

193

Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×

This page intentionally left blank.

Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×
Page R1
Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×
Page R2
Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×
Page R3
Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×
Page R4
Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×
Page R5
Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×
Page R6
Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×
Page R7
Page viii Cite
Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×
Page R8
Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×
Page R9
Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×
Page R10
Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×
Page R11
Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×
Page R12
Page xiii Cite
Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×
Page R13
Suggested Citation:"Front Matter." National Research Council. 2004. Computer Science: Reflections on the Field, Reflections from the Field. Washington, DC: The National Academies Press. doi: 10.17226/11106.
×
Page R14
Next: Prelude: Emily Shops at VirtualEmporia.com »
Computer Science: Reflections on the Field, Reflections from the Field Get This Book
×
Buy Paperback | $48.00 Buy Ebook | $38.99
MyNAP members save 10% online.
Login or Register to save!
Download Free PDF

Computer Science: Reflections on the Field, Reflections from the Field provides a concise characterization of key ideas that lie at the core of computer science (CS) research. The book offers a description of CS research recognizing the richness and diversity of the field. It brings together two dozen essays on diverse aspects of CS research, their motivation and results. By describing in accessible form computer science’s intellectual character, and by conveying a sense of its vibrancy through a set of examples, the book aims to prepare readers for what the future might hold and help to inspire CS researchers in its creation.

  1. ×

    Welcome to OpenBook!

    You're looking at OpenBook, NAP.edu's online reading room since 1999. Based on feedback from you, our users, we've made some improvements that make it easier than ever to read thousands of publications on our website.

    Do you want to take a quick tour of the OpenBook's features?

    No Thanks Take a Tour »
  2. ×

    Show this book's table of contents, where you can jump to any chapter by name.

    « Back Next »
  3. ×

    ...or use these buttons to go back to the previous chapter or skip to the next one.

    « Back Next »
  4. ×

    Jump up to the previous page or down to the next one. Also, you can type in a page number and press Enter to go directly to that page in the book.

    « Back Next »
  5. ×

    Switch between the Original Pages, where you can read the report as it appeared in print, and Text Pages for the web version, where you can highlight and search the text.

    « Back Next »
  6. ×

    To search the entire text of this book, type in your search term here and press Enter.

    « Back Next »
  7. ×

    Share a link to this book page on your preferred social network or via email.

    « Back Next »
  8. ×

    View our suggested citation for this chapter.

    « Back Next »
  9. ×

    Ready to take your reading offline? Click here to buy this book in print or download it as a free PDF, if available.

    « Back Next »
Stay Connected!