CISC 601: Elements of the Theory of Computation

Catalog Description:
General models of computation, formal languages and automata theory, and algorithmic unsolvability.

Current Text:
Computability, Complexity and Languages:
Fundamentals of Theoretical Computer Science, Second Edition,
M. Davis, R. Sigal, and E. Weyuker
Academic Press, New York, NY, 1994.

Additional References:

• J. E. Hopcroft and J. D. Ullman , Introduction to Automata Theory, Languages and Computation, Addison Wesley, Reading, MA, 1979.
• H. Lewis and C. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, Englewood Cliffs, NJ, 1981.

Goals:
The student should learn the general concept of computability through some classical formalisms defining computability; the elements of various special cases of general computability from formal language theory, which underpin the formal language theory of practical utility to both compiler theory and natural language processing; algorithmic unsolvability; and proof techniques used in all of the above.

Content:

• Computability Theory.
  Unlimited register machines, Turing machines, partial recursive functions; Church-Turing thesis; algorithmically unsolvable problems and diagonalization; primitive recursive functions; Kleene normal form theorem; universal programs; recursively enumerable and recursive sets; recursion theorem; Rice's theorem.
• Formal Language Theory.
  Deterministic and non-deterministic finite automata and their equivalence to regular expressions, pumping lemma and Myhill-Nerode theorem; context-free grammars and languages, and the corresponding pushdown automata.

Required Background:
At least one course in which the student was required to prove theorems.