Countable and uncountable sets; diagonalization proofs; finite state automata; regular, context-free, context-sensitive, recursive, and r. e. languages; Turing machines; relationships between classes of languages and machines; the halting problem; proof methods for decidability and undecidabilty.
Prereq: CIS 375 or MAT 375 (or equivalent abstract or discrete mathematics course)
Department: Computer and Information Science
Location: London
Semester: Fall
Credits: 3