X326 | 32473 | Amit Hagar

More than three generations have passed since Church, Turing and Post delineated the limits of computation with their famous theses and in so doing laid the foundations for the theory of computing. The physics of the 21st century, however, is stretching these boundaries. Creating new computational complexity classes, the quantum revolution has penetrated computer science, and scientific journals, as well as popular literature, are saturated with debates on “super-tasks”, “oracles” and “hypercomputers” – machines that perform infinite computational steps in finite time. Are these all- powerful machines physically possible? What are the physical features of the world that allow such reformulation of the notion of computability and complexity? How would this reformulation affect some long-standing debates in the foundations of computer science? Join us to learn more about these questions that lie on the intersection of physics, computer science, and philosophy. We shall discuss the notion of computability and the conceptual problems that arise when analyzing it. We shall acquaint ourselves with Turing machines and the computational complexity “zoo”, and with the Church- Turing thesis and the notion of recursion, and discover some surprisingly non-recursive physical processes. We shall then delve into the fascinating domain of quantum computing, and try to understand how it may affect computer science. The course is self- contained: no formal background is assumed, apart from high-school level math. 2nd 8 weeks