Course CSE350
Title Theory of Computation: Honors
Credits 4
Course Coordinator

Michael Bender


Introduces the abstract notions of machine computation for honors students. Includes finite automata, regular expressions, and formal languages, with emphasis on regular and context-free grammars. Explores what can and cannot be computed by considering various models of computation including Turing machines, recursive functions, and universal machines

Bulletin Link


CSE150 or CSE215; AMS 210 or MAT 211; Computer Science Honors Program or Honors College or the WISE Honors program or University Scholar

Course Outcomes
  • An ability to define and use abstract models of computation such as finite and push-down automata, and analyze their relative expressive power.
  • An ability to define, use, and convert between abstract machine models and formal languages.
  • Understanding of the power and inherent limitations of algorithmic computation.


Harry R. Lewis and Christos H. Papadimitriou, Elements of the theory of computation, Prentice Hall. (Second Edition, 1998).

Major Topics Covered in Course
  • Strings and languages
  • Regular languages, regular expressions and finite automata
  • Turing machines, unrestricted grammars, Church-Turing thesis
  • Introduction to recursion theory, universal Turing machine, halting problem, undecidability
  • Probabilistic computation
  • Applications to operating systems, programming languages, and other areas will be discussed throughout the semester

Laboratory Projects

No large scale projects are required.

Course Webpage