History and Philosophy Of Science | Computers LTD: Logical and Physical Limits on Computation
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