Automata, Computability, and Complexity

Course Home Page
General Information/Policies
Contact Info
Objectives and Outcomes
Course Materials by Lecture Date


On completion of 6.045, students will be able to explain the basic methods and conclusions of the Theory of Computation. They will be able to apply these methods to problems from different fields and be guided by the results in searching for computational solutions to the problems.

In particular, students will be able to

  1. explain the theoretical limits on computational solutions of undecidable and inherently complex problems.
  2. describe concrete examples of computationally undecidable or inherently infeasible problems from different fields.
  3. devise and analyze the complexity of procedures to determine properties of computationally bounded automata.
  4. understand formal definitions of machine models.
  5. prove the undecidability or complexity of a variety of problems.

Learning Outcomes

Students will be able to:
  1. synthesize finite automata with specific properties.
  2. convert among multiple representations of finite automata.
  3. use pigeon-holing arguments and closure properties to prove particular problems cannot be solved by finite automata.
  4. calculate asymptotic estimates of the computational complexity of simple procedures from automata, language and graph theory.
  5. prove undecidability using diagonalization and reducibility methods.
  6. use the relationship between recognizability and decidability to determine decidability properties of problems.
  7. describe concrete examples of undecidable problems from different fields.
  8. define, and explain the significance of, the "P = NP?" question and NP-completeness.
  9. describe concrete examples of NP-complete problems from different fields.
  10. prove lower bounds on time and space complexity using diagonalization and polynomial time reducibility methods.
  11. define deterministic and nondeterministic computation time and space, and explain the relationships among them.
  12. describe concrete examples of decidable problems that are known to be unsolvable in polynomial time.

Objectives vs Outcomes

Objectives: related Outcomes

Outcomes: reflected Objectives

Last modified: Sunday, January 18, 2004