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
A related question is that of the comparable difficulty of solving problems versus verifying the validity of solutions. We believe that some problems are much harder to solve than to verify the validity of a solution for them. However, we don't know this to be a fact either: this is actually the famous P versus NP question. Still, we know of many problems that are hard to solve, provided that the above belief is indeed valid. For each of these problems (called NP-hard), an efficient solving method would imply an efficient solving-method for each problem in NP (i.e., each problem for which verifying the validity of solutions is easy). Thus, all the (hundreds of natural) NP-complete problems (i.e., problems are both NP-hard and in NP) are computationally equivalent, although the formulation of many of them seems totally unrelated.
The Theory of Computation provides a new viewpoint on old phenomena. For example, a computational approach to randomness leads to the conclusion that randomness can be expanded almost arbitrarily (cf. the theory of pseudorandomness). Likewise, a computational approach to proofs leads to the conclusion that obtaining a proof to a statement may not teach you anything beyond the validity of the statement (such proofs are called zero-knowledge). In general, a computational approach to proofs leads to the realization that the standard notion may be generalized by allowing interaction and randomization, and the derived notions of probabilistic proof systems offer many advantages over standard (static and deterministic) proof systems.
The Theory of Computation is also concerned with finding the most efficient methods for solving specific problems. For example, multiplying numbers can be done more efficient than via the simple method learned in elementary school.
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.