Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-072 | 19th April 2018 18:12

On the nature of the Theory of Computation (ToC)

RSS-Feed




TR18-072
Authors: Avi Wigderson
Publication: 19th April 2018 18:12
Downloads: 5744
Keywords: 


Abstract:

[ This paper is a (self contained) chapter in a new book on computational complexity theory, called Mathematics and Computation, available at https://www.math.ias.edu/avi/book ].

I attempt to give here a panoramic view of the Theory of Computation, that demonstrates its place as a revolutionary, disruptive science, and as a central, independent intellectual discipline. I discuss many aspects of the field, mainly academic but also cultural and social. The paper details of the rapid expansion of interactions ToC has with all sciences, mathematics and philosophy. I try to articulate how these connections naturally emanate from the intrinsic investigation of the notion of computation itself, and from the methodology of the field. These interactions follow the other, fundamental role that ToC played, and continues to play in the amazing developments of computer technology. I discuss some of the main intellectual goals and challenges of the field, which, together with the ubiquity of computation across human inquiry makes its study and understanding in the future at least as exciting and important as in the past.

This fantastic growth in the scope of ToC brings significant challenges regarding its internal organization, facilitating future interactions between its diverse parts and maintaining cohesion of the field around its core mission of understanding computation. Deliberate and thoughtful adaptation and growth of the field, and of the infrastructure of its community are surely required and such discussions are indeed underway. To help this discussion I review the history, culture and evolution of the field. I list what I believe are the essential characteristics which allowed ToC to so well embrace and integrate so many external influences, continuously expanding its core mission, and to create one of the greatest success stories in the history of science. I feel that preserving many of these characteristics, primarily its independence, and that educating ToC professionals (as well as other scientists, engineers, and, at appropriate levels, children and the general public too) in these achievements and challenges, are essential for a similarly spectacular future.

I attempt to give here a panoramic view of the Theory of Computation, that demonstrates its place as a revolutionary, disruptive science, and as a central, independent intellectual discipline. I discuss many aspects of the field, mainly academic but also cultural and social. The paper details of the rapid expansion of interactions ToC has with all sciences, mathematics and philosophy. I try to articulate how these connections naturally emanate from the intrinsic investigation of the notion of computation itself, and from the methodology of the field. These interactions follow the other, fundamental role that ToC played, and continues to play in the amazing developments of computer technology. I discuss some of the main intellectual goals and challenges of the field, which, together with the ubiquity of computation across human inquiry makes its study and understanding in the future at least as exciting and important as in the past.

This fantastic growth in the scope of ToC brings significant challenges regarding its internal organization, facilitating future interactions between its diverse parts and maintaining cohesion of the field around its core mission of understanding computation. Deliberate and thoughtful adaptation and growth of the field, and of the infrastructure of its community are surely required and such discussions are indeed underway. To help this discussion I review the history, culture and evolution of the field. I list what I believe are the essential characteristics which allowed ToC to so well embrace and integrate so many external influences, continuously expanding its core mission, and to create one of the greatest success stories in the history of science. I feel that preserving many of these characteristics, primarily its independence, and that educating ToC professionals (as well as other scientists, engineers, and, at appropriate levels, children and the general public too) in these achievements and challenges, are essential for a similarly spectacular future.



ISSN 1433-8092 | Imprint