Theory of Computation: A Scientific Perspective

by Oded Goldreich and Avi Wigderson

The revolutionary impact of Computing Technology on our society does not necessarily facilitate the appreciation of the intellectual contents of the Theory of Computing (TOC). Typically, people are so overwhelmed by the wonders of the computing technology that they fail to wonder about the theory underlying it. Furthermore, they 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 Computing is rarely communicated and rarely understood (by non-specialists).

Our aim is to help to redeem this sour state of affairs and try to communicate the intellectual contents of the Theory of Computing. We provide an assessment of the Theory of Computing (TOC), as a fundamental scientific discipline, highlighting the following points:

• TOC is the science of computation. It seeks to understand computational phenomena, be it natural, man-made or imaginative.
• Research in TOC has been extremely successful and productive in the few decades of its existence, with continuously growing momentum. This research has revolutionized the understanding of computation and has deep scientific and philosophical consequences, which will be further recognized in the future. Moreover, this research and its dissemination through education and interaction has been responsible for enormous technological progress.

Related Material Available On-Line