CSCI 4050/6972: Theory of Computation

General Information

Instructor: Stacy Patterson (sep@cs.rpi.edu)
Instructor Office Hours: M 1pm - 3pm in Lally 301

Lectures: TF 12pm - 1:50pm in DARRIN 239 SAGE 3713

Course Description

This course covers the formal foundations of computability and complexity. We aim to answer fundamental questions about what problems can be solved and what problems cannot be solved, and what problems can be solved given our limited resources. Topics include: the Church-Turing thesis; variations of Turing Machines; decidability; the Halting Problem; reducibility; the Recursion Theorem; time and space complexity; intractability; NP-completeness; and Cook’s theorem. We will also discuss some unconventional computing models, such as optical computing and DNA computing.