Listed in: First Year Seminar, as FYSE-131
Lee Spector (Section 01)
Computers play increasingly important roles in nearly all human activities, and computational power is changing the world. But what are the limits and contours of computational power? Are there things that humans can do, but that no computer will ever be able to do? Will computers eventually be able to solve any clearly stated logical or mathematical problem? What computational power might we expect from future technologies, and what can we rule out? These questions raise complex, interdisciplinary issues. In some cases, there is strong evidence that popular conceptions of computational power are incorrect, underestimating or overestimating the power of computers in significant ways. In this course we will explore the real limits of computation from philosophical, logical, mathematical, and public-policy perspectives. We will begin with a discussion of the possibility of artificial intelligence (AI), covering the claims that have been made by AI scientists and the critiques of such claims that have arisen from the philosophical community. We will then focus on the fundamental logic and mathematics of computation, including techniques for proving that certain problems are intractable or unsolvable. In the third part of the course we will turn to social and political questions on which an informed view of the limits of computation can have an impact. Students will be evaluated through a combination of short papers and problem sets, along with a final project.
Fall semester. Professor Spector.