Fall 2002 Course
22C:135 Introduction to Computation Theory

Instructor: Arthur C. Fleck
Teaching Assistant: Jin Zhou, Office: B20J MLH, Hours: 11-12:20 T-Th, Ph.: 335-3650
Time/place: 10:30 am MWF / 110 MLH
Text: A. C. Fleck, Formal Models of Computation: The Ultimate Limits of Computing, at IMU bookstore

Course overview

The course develops several formal models of computing systems, and investigates what computations can be accomplished with various combinations of computing resources. Properties of both the possible, and the impossible, computations are studied. The course culminates with results about computations that are impossible on any computer system regardless of its speed and size.

General background from the formal prerequisite 22C:34 will be assumed. In particular, it will be assumed that the student has basic knowledge of sets, functions, relations, and graphs, plus experience with formal proofs, especially induction proofs.

The course will involve two in-class exams, announced well in advance, and a final exam, scheduled for Monday December 16 from 2:15-4:15 pm in our regular classroom. There is also weekly homework. The assignments in the course do not involve computer programming. The work involves problem solving, and the careful proof of the conclusions that can be drawn from rigorous definitions of the computing models.

Anyone who has a disability that requires modification of testing or other class arrangements should contact me as soon as possible. Please see me after class or during office hours.

Topic list

Related Web sources: