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.
Next offered when staffing permits.
Prerequisite: CPSC 035 required. Mathematics background at the level of Linear Algebra or higher is required (may be taken concurrently).
Natural science and engineering.
Lab work required.

1 credit.

Catalog chapter: Computer Science
Department website: http://www.cs.swarthmore.edu/

Access the class schedule to search for sections.