CS 175: What Computers Can't Do


Hampshire College, Amherst MA
Spring, 2002



Lee Spector, lspector@hampshire.edu
413-559-5352, ASH 201

Meeting times

Tuesdays and Thursdays, 10:30-11:50 AM


Adele Simmons Hall (ASH) Room 222

Class web page


Class email list



Computers are commonly (and inconsistently) regarded as both omnipotent and as "stupid machines." In this course we will explore the real limits of computation from philosophical, logical, mathematical and public-policy perspectives. We 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 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 turn to social and political questions on which an enlightened 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.


Boden, Margaret A., ed. 1990. The Philosophy of Artificial Intelligence. Oxford: Oxford University Press.

Harel, David. 2000. Computers Ltd.: What they really can't do. Oxford: Oxford University Press.

Additional readings will be distributed in class. The texts will be available on reserve for short-term (3 hr.) borrowing from the Hampshire College Library.


The course will be divided into three segments of approximately equal length but rather different content, classroom activities, and assignments:

Computers and Minds: In this section of the course we will read seminal papers in the philosophy of artificial intelligence (from the Boden collection), covering topics such as the Turing test, the Chinese room argument, and the frame problem. Class time will be devoted to discussion of the papers and the issues that they raise. Students will be expected to complete the assigned reading before class, to participate in class discussions, and to write two short reaction papers.

Limits of Computation: In this section of the course we will read the Harel book, covering (at a relatively non-technical level) fundamentals of the mathematics of computational complexity and computability. Class time will be devoted primarily to lecture-style presentations. Students will be expected to complete the assigned reading before class and to complete a sequence of assigned problem sets.

Limits and Society: In this section of the course students will work in groups to produce half-hour final presentations on public policy issues for which computational limits are important. The topics of these presentations will be determined in class, but possibilities include missile defense, privacy, and copy protection. Class time will be devoted to structured cooperative group work. Students will be expected to conduct research outside of class (in the library and on the internet) and to participate actively in the work of their groups.

This page is maintained by Lee Spector and was last updated on January 28, 2002