become so firmly fixed in the instincts of computer scientists and engineers that they are likely to be used as naturally as a cashier uses arithmetic, with little attention to the origins of the process. In this way, theory pervades the daily practice of computer science and lends legitimacy to the very identity of the field.

This chapter reviews the history and the funding sources of four areas of theoretical computer science: state machines, computational complexity, program correctness, and cryptography. A final section summarizes the lessons to be learned from history. 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. Cryptography dates back even further. The evolution of these subfields reflects the interplay of mathematics and computer science and the ways in which research questions changed as computer hardware placed practical constraints on theoretical constructs. Each of the four areas is now ubiquitous in the basic conceptual toolkit of computer scientists as well as in undergraduate curricula and textbooks. Each area also continues to evolve and pose additional challenging questions.

Because it tracks the rise of ideas into the general consciousness of the computer science community, this case study is concerned less with issues of ultimate priority than with crystallizing events. In combination, the history of the four topics addressed in this chapter illustrates the complex fabric of a dynamic field. Ideas flowed in all directions, geographically and organizationally. Breakthroughs were achieved in many places, including a variety of North American and European universities and a few industrial research laboratories. Soviet theoreticians also made a number of important advances, although they are not emphasized in this chapter. Federal funding has been important, mostly from the National Science Foundation (NSF), which began supporting work in theoretical computer science shortly after its founding in 1950. The low cost of theoretical research fit the NSF paradigm of single-investigator research. Originally, such work was funded through the division of mathematical sciences, but with the establishment of the Office of Computing Activities in 1970, the NSF initiated a theoretical computer science program that continues to this day. As Thomas Keenan, an NSF staffer, put it:

Computer science had achieved the title "computer science" without much science in it, [so we] decided that to be a science you had to have theory, and not just theory itself as a separate program, but everything had to have a theoretical basis. And so, whenever we had a proposal . . .

The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001
Copyright © National Academy of Sciences. All rights reserved.
Terms of Use and Privacy Statement