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:

A preliminary version (written in June 2001) is available in PostScript. See minor revision in PDF.

Related Material Available On-Line

A related essay (with the same title), was written by the same authors in 1996. A full version is available from the essay's webpage. In particular, a 3-page extended abstract of that essay is available in HTML and PostScript formats.

Back to Oded's homepage.