MCS 3311 Theory Of Computation

Abstract models of computing machines and the data they process are developed. These are used to study the theoretical limitations of what they can achieve. The ultimate goal is to develop a sufficiently general model of computation where one may discover universal laws that govern all programming languages together with the computing machines which may be built to interpret them. The topics covered are the theory of automata, formal languages, computability by Turing machines and Churchs thesis. Proofs are required.

Credits

3

Prerequisite

MCS 3316 or consent of instructor.

Offered

Spring, Even years