This is an archived page and may be obsolete; the current pages are at http://www.iit.edu/csl/cs

CS 530: Theory of Computation

Objectives

This course discusses basic computation models including finite automata, push-down automata, and Turing machines. Recursive function theory and logical theories will also be discussed. Computability issues (including undecidability) as well as complexity issues related to the various models will also be discussed.

Prerequisites

CS 430 and a formal languages course.

Syllabus

• Finite Automata and Regular Sets
  • Formal definitions of automata, regular expressions and equivalence with automata
  • Non-deterministic FA and their equivalence to deterministic FA
  • Pumping Lemma to show that a language is not regular
• Push-down Automata
  • Formal definition of push-down automata and equivalence with context-free grammars
• Turing Machines
  • Formal definition of a Turing machine
  • Various models of TM's and their equivalence
• Decidability, Reducibility, and Undecidability
  • The Halting problem
  • Mapping reducibility
  • Undecidable problems in language models
• Recursive Function Theory  
• Decidability of Logical Theories
• Time Complexity of Turing Machine Computations
  • The classes P and NP
  • NP-Completeness and the Cook-Levin theorem
  • Polynomial reducibility
  • NP-Complete problems
• Space Complexity
  • Savitch's Theorem
  • PSPACE and PSPACE-complete theorems
• Additional topics in Complexity: Probabilistic Algorithms, Alternation

Edited March 2006 (html, css checks)