The idea that “Life, the Universe, and Everything” (to borrow from Adams’ “The Hitchhiker’s Guide to the Galaxy”) is some sort of a computer is a captivating idea, featured in science fiction. But could it be more than science fiction? A growing movement in science, sometimes referred to as “the Computational Lens,” views physical and social phenomena being (or performing) forms of computations. The usefulness of this perspective is to a large extent the result of the success of a rather small community, the love child of Computer Science and Math, that studies the `Theory of Computing.’
In this seminar, we will discuss the Theory of Computing as an ambitious intellectual endeavor to understanding the fundamental nature of computations. What are computations? How can we study them in enough generality to capture aspects of the evolution of species, the structure of social networks, and the computations on your smart phone? What are the laws of efficiency and complexity that govern computations?
We will see surprising algorithms for very familiar problems (like long multiplication), as well as simple problems no one knows how to solve efficiently. We will encounter logic paradoxes that expose the limitations of computations. We will see why creating tests is probably much easier than solving them and what this gap in efficiency means in Cryptography. We will view time, memory, communication and even randomness as resources of computation. We will encounter new understanding of knowledge, learning and entropy, through the computational lens. We will explore the different worlds we may be living in, depending on the answers to some of the central problems of Computer Science and Math.
The class is intended for students with a wide range of interests. The course will not involve programming (and knowing how to program is not a prerequisite). While our class will not rely on any deep mathematics (beyond basic high-school math) we will deal with mathematical formalization of concepts and with mathematical problem-solving. Therefore, some mathematical maturity and interest would be useful.
Omer Reingold 