A Brief Introduction to the Theory of Computation

written by Oded Goldreich

The revolutionary impact of a technology (in our case the Computing Technology) on our society does not necessarily facilitate the appreciation of the intellectual contents of the theory underlying it (in our case the Theory of Computation). Typically, people are so overwhelmed by the wonders of the technology that they fail to wonder about the theory underlying it. Specifically, people tend not to think of computing in general terms but rather in the concrete terms in which they have lastly encountered it. Consequently, the intellectual contents of the Theory of Computation is rarely communicated and rarely understood (by non-specialists). We hope this page and links provided by it may help to redeem the state of affairs.

Computer Science is a cluster of related scientific and engineering disciplines concerned with the study and application of computations. These disciplines range from the pure and basic scientific discipline concerned with the foundations (or theory) of computer science (or of computation) to engineering disciplines concerned with specific applications.

The foundations (or theory) of computer science can be partitioned into two sub-disciplines: one concerned with the Theory of Computation, and the other concerned with the Theory of Programming. The Theory of Computation aims at understanding the nature of computation, and specifically the inherent possibilities and limitations of efficient computations. The Theory of Programming is concerned with the actual task of implementing computations (i.e., writing computer programs).

The Theory of Computation is a scientific discipline concerned with the study of general properties of computation be it natural, man-made, or imaginary. Most importantly, it aims to understand the nature of efficient computation. A few examples that are related to my specific research interests follow

The nature of efficient computation (and computation in general) is indeed the formative question of the Theory of Computation. We consider this question (or rather a cluster of questions) to be one of the most fundamental scientific questions ever asked. Unfortunately, the fundamental status of this question is usually disregarded due to its immediate technological impact.

The theory of computation can be sub-divided to numerous overlapping areas. Two main clusters of areas are complexity theory and algorithms, where the distinction is on whether the focus is on the computational resources (as in complexity theory) or on the tasks to be solved (as in algorithms). Indeed, complexity theory is sub-divided according to the model and resources of computation (i.e., time complexity, space complexity, circuit complexity, communication complexity, proof complexity, etc), whereas algorithms are sub-divided according to the respective tasks (e.g., graph algorithms, linear programming, approximation algorithms, computational number theory, computational geometry, etc). In addition, there are areas of the theory of computation that are not to be forced into the above two clusters. Examples include Cryptography, Distributed Computing, and Computational Learning Theory.

Additional material available on-line

Back to homepage.