CPSC 046. Theory of Computation
(Cross-listed as MATH 046 )
This study of various models of computation leads to a characterization of the kinds of problems that can and cannot be solved by a computer. Solvable problems will be classified with respect to their degree of difficulty. Topics to be covered include formal languages and finite state devices; Turing machines; and other models of computation, computability, and complexity.
Group 1 course.
Prerequisite: CPSC 035 and Mathematics background at the level of Linear Algebra or higher (may be taken concurrently)
Natural science and engineering.
Lab work required.
Spring 2022. Wehar.
Fall 2023. Brody.
Catalog chapter: Computer Science
Department website: https://www.swarthmore.edu/computer-science
Check the Spring 2021 Schedule of Courses
Check the Fall 2021 Schedule of Courses