CMPU 240 - Theory of Computation

Semester Offered: Spring
1 unit(s)

Introduces the theory of computation while exploring the fundamental powers and limitations of all computing machines. Considers appropriate models of a computer and what problems are and are not solvable in such models. Aims to develop an understanding of the intimate connection between computation and language recognition, using as examples several classes of abstract machines and the corresponding classes of formal languages. Students learn how to reason about the nature of computation itself, and develop the intuition of a computer scientist. Provides theoretical foundations for CMPU 331 and 366. Jonathan Gordon.

Prerequisite(s): CMPU 102 and CMPU 145.

Two 75-minute periods.

Course Format: CLS