TCS = TOC + TOP

Oded Goldreich


My main thesis is that Theoretical Computer Science (TCS) consists of two separate theoretical (or mathematical) disciplines, which study different parts of the phenomenon of computation. Broadly speaking, the Theory of Computation (TOC) is concerned with computation as an automatic process, with the possible outcomes of such processes, the resources that they require, and the design of processes that achieve a desired goal. The computaional rules that determine the process of computation can be natural or artificial, real-life or abstract, determined beforehand or to be designed. The specific formulation of these rules and the process of designing them is typically ignored.

In contarst, the Theory of Programming (TOP) is typically concerned with the process of designing desired rules of computation (i.e., computer programs), a task that typically involves the participation of humans. One key concern is that of the correspondance between the imformal intensions of the human designers (or actually of their clients) and the actual program that is supposed to meet these intensions. That is, TOP is concerned with the creative process of designing program, whereas TOC is concerned with the automated process that evolves when programs are run (regardless of how they were designed).

The above is a description of the current state of affairs. It represents the way that these two disciplines are understood by scholars who are interested in them. Indeed, scientific disciplines are defined in terms of the corresponding resaerch communities, which in turn are groups of scholars who are interested in the same (or very similar) type of questions. In light of the above, I claim the following.

  1. TOC and TOP are distinct scientific disciplines, since they are defined by almost disjoint scientific communities, which are interested in different types of questions.
  2. TCS is and should mean the combination of TOC and TOP. Both parts of TCS should be well represented in CS depts.
  3. FOCS/STOC should be devoted to TOC.
    The single TOP sessions that existed in STOC/FOCS in early 1980s were not a good idea; they did not make these venues true TCS venues (i.e., they were TOC venues with a "symbolic" representation of TOP). Both TOC and TOP are better of without such a lip-service for a (non-existing) "unity" (in lack of candid joint interests).
An interesting question (in sociology of science) is what is why is TOP currently underrepresented in the USA, while it is not underrepresented in Europe.

It seems that item (1) is the item that requires most justification, since (2) and (3) follows from it. Identifying disciplines with the corresponding research communities, one may ask what is a research community, how are its borders determined, and what do these borders serve? These are fundamental questions in the philosophy and sociology of science. The application of the answers to the identification of research communities is not only interesting for the study of science (as a sociological and philosophical discipline) but has significant implications on the operations of the specific scientific communuities.

Definite answers to the foregoing questions seem far too challenging, but a couple of principles can be stated. The first principle is that the borders of the disciplines (and the relevant communities) are determined by the actual interests and activities of researchers. That is, a discipline and a community emerge when a group of researchers realize that they have shared interests and act accordingly. At such a point, the group may establish institutes and/or forums of meeting, which would farther foster the shared interests and a shared identity. Hence, the formal forms follow the actual contents, and the administration of operation follows the actual activity. The above principle is both descriptive and normative; that is, it describes how fields have actually evolved as well as provides a guidelines for a desirable evolution.

A second principle is that the definition of a discipline and a research community is always tentative. It refers to a current situation that may be subject to change, whereas change is part of the inner dynamic of the field.


Back to Oded's page of essays and opinions or to Oded's homepage.