MATH 643Theory of Computation

This course will use mathematics to study the foundations of problem solving and computation. A decision problem (answering "yes" or "no") can be characterized as a set of strings of characters encoding inputs that yield "yes" answers, and a computer can be characterized as a simple mathematical machine model that processes strings of characters. By studying properties of classes of problems of increasing complexity, we will be able to establish relationships among classes, membership in classes, and hard problems for classes. The course will culminate in the examination of classes and models that correspond to the power of computers, and the demonstration that there exist problems that cannot be solved.