|Theory of Computation
|3 - credits
The purpose of this course is to study the capabilities and limitations of computers, by formulating mathematically various models of idealized computers and establishing rigorously for these models what kinds of problems can and cannot be solved, as well as what kinds of problems can and cannot be solved with a reasonable amount of computing resources.
Topics include but not limited to:
An introductory treatment of Turing machines would typically be part of an undergraduate course in the theory of computation, which is a prerequisite for this course. Though we shall cover this topic, the treatment will be fairly speedy, so as to leave enough time for complexity theory and advanced topics.
|Major Topics Covered in Course