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
See minor revision in
- 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
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
Back to Oded's homepage.