ACM Computing Surveys 28A(4), December 1996, http://www.acm.org/surveys/1996/GWtoc-sp/. Copyright © 1996 by the Association for Computing Machinery, Inc. See the permissions statement below.
Abstract: Theory of Computation (TOC) seeks to understand computational phenomena, be it natural, man-made or imaginative. We argue that TOC is an independent scientific discipline of fundamental importance, and that its great achievements, productivity and impact so far (both scientific and technological) were due to the autonomy it had to pursue its intrinsic goals. Our main recommendation is that in order for TOC to prosper in the coming years, it is essential that Theoretical Computer Scientists concentrate their research efforts in Theory of Computing and that they enjoy the freedom to do so.Categories and Subject Descriptors: F.0 [General]; K.0 [General]
General Terms: Position Paper, Theory of Computing.
Additional Key Words and Phrases: Science, Technology, Universities, Funding.
Theory of Computation (TOC) seeks to understand computational phenomena, be it natural, man-made or imaginative. TOC is an independent scientific discipline of fundamental importance. Its intrinsic goals (those which were achieved, those which are yet to be achieved, and those which are yet to be defined) transcend the immediate applicability to engineering and technology.
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 was responsible for enormous technological progress.
Much of the full version of our manuscript [Goldreich and Wigderson 1996] is devoted to substantiating the strong statements made above. Here, due to space limitations, we merely list a few of the fundamental achievements of TOC.
The success of TOC is directly correlated to the extremely high quality and creativity of researchers in TOC, to their independence, and to the fundamental (and exciting) nature of the questions TOC addresses. In order for the Theory of Computing to prosper in the future it is essential that TOC attracts the same calibre of researchers, that Theoretical Computer Scientists concentrate their research efforts in Theory of Computing and that they enjoy the freedom to do so. Free pursuit of their research interests may well lead individual scientists to work closely with/in application areas. Indeed, our field has already an admirable tradition where many TOC leaders (undirected and un-forced) chose to redirect part of their research so as to strongly influence application areas as well as other sciences. Yet, decisions taken by individual scientists following their own understanding of the discipline differ drastically from attempts to direct the whole discipline towards directions which are not intrinsic to it. Thus we completely reject the opinion, which has been spreading in our community in the last few years, that the prosperity of TOC depends on service to other disciplines and immediate applicability to the current technological development.
We claim that these dangerous feelings within the TOC community, leading to the willingness to dictate non-intrinsic directions to its researchers, are not the outcome of external pressures alone. They also result from two internal sources, which have to be recognized, understood and then counteracted.
The first source is a deep (but unjustified) feeling of frustration among some members of the TOC community. The frustration is due to unrealistic expectations by which the TOC community should have been able to gain by now an almost full understanding of the nature of efficient computation. The unrealistic nature of these expectations stems from the unimagined (by the founders of the field) depth, richness and difficulty of central TOC questions, revealed in the last 20 years. It is not surprising that while these facts generated frustrations in a young, inexperienced field like ours, the same facts generated increasing respect and appreciation for TOC in Mathematics and other more mature sciences. What should be concluded from our short history is positive: our deep unsolved problems, the understanding and techniques we gathered so far, and the continuous introduction of the computational point of view to more diverse natural and artificial phenomena, offer a great agenda of research in TOC for the 21st century.
The second source of internal problems is the lack of a ``leadership group'', deeply convinced of the importance of the discipline, which is willing and able to oppose pressures from the outside, as well as further this conviction to the junior TOC generations. Again, some of this stems from TOC being a young, politically inexperienced field, pampered for a long time due to practical interest in computer science. Thus our leaders have chosen to concentrate on research (with phenomenal success), but have neglected to ensure the same atmosphere of (economic and spiritual) freedom for the younger generations. This can be remedied, by a great public relations offensive of our leaders on the funding agencies and the university administrations as well as the general sceintific community. We strongly feel that it is nearly trivial to ``sell'' TOC as a remarkable, continuous success story, whose future findings are even likely to exceed the past ones both in intrinsic scientific interest as well as influence on technology and other sciences. We recognize that doing this requires sacrifice of time and effort from our leaders, and call upon them to take on this important chore, just as their peers in other sciences like Physics and Biology have been doing for decades. The fact that our research needs are negligible compared to the needs of these other sciences (and even to those of experimental computer science) should help these efforts considerably.
It is clear that despite the measures suggested above, which will hopefully improve the funding and job situation in TOC, we have reached the end of the era of exponential growth and unlimited support. Thus, it is more crucial than ever that TOC continues to attract the best students to its ranks. We believe again that this is an easy task, achieved via the teaching of the great achievements of TOC research and its even greater challenges. Likewise, it is crucial that TOC sustains the complete academic freedom that enabled past success.
To summarize, TOC is a relatively new scientific discipline of fundamental importance, which has been extremely successful and is still far from achieving its intrinsic goals. The intellectual challenges of TOC are gigantic and of the greatest importance. It is thus essential that this discipline be given a high priority, both inside computer science and among the sciences. It is up to us to ensure this, via education of the world outside TOC on our achievements, and via continuous research of the same quality on our scientific agenda.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.