Funding a Revolution Government Support for Computing Research (1999) / Chapter Skim
Currently Skimming:
8 Theoretical Research: Intangible Cornerstone of Computer Science
8 Theoretical Research: Intangible Cornerstone of Computer Science
Pages 184-197
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 184... ...
contributed to the development of compilers and communications protocols, insights into computational complexity have been applied to improve the efficiency of industrial processes and information systems, formal verification methods have provided a tool for improving the reliability of programs, and advances in number theory resulted in the development of new encryption methods. By serving as practical tools for use in reasoning and description, such theoretical notions have informed progress in all corners of computing.
|
From page 185... ...
Although by no means a comprehensive overview of theoretical computer science, the discussion focuses on topics that are representative of the evolution in the field and can be encapsulated fairly, without favoring any particular thesis. State machines, computational complexity, and verification can be traced to the work of logicians in the late 1800s and early 1900s.
|
From page 186... ...
Mission-oriented agencies, such as the National Aeronautics and Space Administration or the Defense Advanced Research Projects Agency, tend not to fund theoretical work directly because of their emphasis on advancing computing technology, but some advances in theory were made as part of their larger research agendas. MACHINE MODELS: STATE MACHINES State machine are ubiquitous models for describing and implementing various aspects of computing.
|
From page 187... ...
Digit (A Off hook Timeout* / /Timeout Remote l hang up 187 FIGURE 8.1 Simplified state diagram for supervising a telephone line.
|
From page 188... ...
These two threads eventually coalesced in the study of communications protocols, which are now almost universally specified in terms of cooperating state machines (as discussed below in the section dealing with correctness)
|
From page 189... ...
had published the first volume of a treatise on the subject that remains an indispensable reference today. Over time, work on complexity theory has evolved just as practical considerations have evolved: from concerns regarding the time needed to complete a calculation, to concerns about the space required to perform it, to issues such as the number of random bits needed to encrypt a message so that the code cannot be broken.
|
From page 190... ...
The quantitative approach to complexity pioneered by Hartmanis and Stearns spread rapidly in the academic community. Applying this sharpened viewpoint to decision problems in logic, Stephen Cook at the University of Toronto proposed the most celebrated theoretical notion in computing NP completeness.
|
From page 191... ...
The academic movement toward program verification was paralleled by a movement toward structured programming, christened by Edsger Dijkstra at Technische Universiteit Eindhoven and vigorously promoted by Harlan Mills at IBM and many others. A basic tenet of the latter movement was that good program structure fosters the ability to reason about programs and thereby assure their correctness.7 Moreover, analogous structuring was to inform the design process itself, leading to higher productivity as well as better products.
|
From page 192... ...
In this approach, programs are derived from specifications by algebraic calculation. In the most advanced manifestation, formulated by Eric Hehner, programming is identified with mathematical logic.
|
From page 193... ...
followed his founding paper on information theory, it was actually written earlier under conditions of wartime security. Undoubtedly, Shannon's involvement with cryptography on government projects helped shape his thinking about information theory.
|
From page 194... ...
This unsolicited attention has evoked a notable level of independence among investigators. Most, however, have achieved a satisfactory modus vivendi with the concerned agencies, as evidenced by the seminal papers cited in this chapter that report on important cryptographic research performed under unclassified grants.
|
From page 196... ...
By teaching and writing textbooks, academic researchers naturally influenced the subjects taught, especially during the formative years of computer science departments. However, some important synthesizing books have come from industrial research laboratories, where management has seen fit to support such writing to enhance prestige, attract candidates, and foster the competence on which research depends.
|
From page 197... ...
NOTES Between 1973 and 1996, NSF funding for theoretical computer science grew from less than 52 million to almost 57 million dollars. In 1996 dollars (i.e., taking inflation into account)
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.