CSCI 438

Theory of Computation

3 Cr. (Hrs.:3 Lec.)

Students will look abstractly at computers and what it means to be computable. Turing Machines, which appear to be powerful enough to serve as the basis for defining computability, will be studied . Students will learn that some questions are not computable by any computing machine. Regular, context-free languages, decidability and computational complexity will also be studied. Prerequisite: CSCI 305 (2nd)

Course generally offered spring (2nd) semester.

Expectations:

E1. Students have a working knowledge of elementary set theory and mathematical structures such as relations, functions, and graphs and are able to apply this knowledge towards solving algorithmic problems. (CSCI 246)

E2. Students are able to use inference and to develop direct and inductive proofs, proofs by construction, and proofs by contradiction. (CSCI 246)

E3. Students can identify and understand why some problems cannot be solved efficiently (NP problems). (CSCI 332)

E4. Students recognize regular languages, know situations where regular languages are useful, and are able to define regular languages using finite automaton (deterministic and nondeterministic), grammars and regular expressions. (CSCI 305)

E5. Students recognize context free languages, know situations where context free languages are useful, and are able to define context free languages using push down automaton and grammars. (CSCI 305)

Course Outcomes:

R1. Students can translate between the regular language formalisms (deterministic finite automaton, non-deterministic finite automaton, regular grammars and regular expressions) and can show that a language is not regular using a pumping lemma argument. (CS: 1, 6)

R2. Students can translate between push-down automaton and context-free grammars and can show that a language is not context free using a pumping lemma argument. (CS: 1, 6)

R3. Students understand the concept of a Turing Machine, and know several variations on Turing Machines that are all equivalent. (CS: 1, 6)

R4. Students know that Turing Machines can be used to define computability and that all other sufficiently complex models of computation are equivalent to Turing Machines (Church-Turing Thesis). (CS: 1, 6)

R5. Students know examples of problems that are undecidable by any Turing Machine. (CS: 1)

R6. Students understand the complexity classes P, NP and NP-complete and can prove membership within these classes. (CS: 1, 6)

CS:
5-2-1 - Techniques, skills, and tools necessary for computing practice
5-a-1 - Substantial coverage of algorithms and complexity, computer science theory, concepts of programming languages, and software development
5-a-4 - The study of computing-based systems at varying levels of abstraction