Excerpt

I am deeply flattered and at the same time overwhelmed to be invited to give a presentation on a topic of this scope to a group of such eminent scholars. I accepted this invitation not because I possess the qualifications to do justice to the task—I don’t—but out of great interest and respect for what you are trying to do. I have worked primarily in mathematical logic and the foundations of mathematics, and only secondarily in theoretical computer science. I will try to do the best I can under the circumstances.

What I have done is to list ten substantial areas of theoretical computer science in which either (a) sophisticated mathematical ideas and constructions have been used to obtain significant results, or (b) the conceptual framework is so closely related to that of an existing developed area in mathematics that the computer science area can be viewed as almost a redirection of the mathematics area.

Let me describe these ten areas—I’m sure that many more could be discussed— as well as the allied areas of mathematics:

1. ABSTRACT COMPLEXITY AND RECURSION THEORY

Computational complexity theory is a theoretical study of what idealized computers can or cannot do under various relevant restrictions of computing resources, such as the amount of available time or space. Among the idealized models used in this area have been the “multitape Turing machines” and the “random access machines.” More recently, variants of these models involving parallel computation, idealized circuits, and probabilistic algorithms have been studied.

BACK TO Emerging Syntheses in Science