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
explain the theoretical limits on computational solutions of undecidable
and inherently complex problems.
describe concrete examples of computationally undecidable
or inherently infeasible problems from different fields.
devise and analyze the complexity of procedures to
determine properties of computationally bounded automata.
understand formal definitions of
machine models.
prove the undecidability or complexity of a variety of problems.
Learning Outcomes
Students will be able to:
synthesize finite automata with specific properties.
convert among multiple representations of finite automata.
use pigeon-holing arguments and closure properties
to prove particular problems cannot be solved by finite automata.
calculate asymptotic
estimates of the computational complexity of simple procedures from
automata, language and graph theory.
prove undecidability using
diagonalization and reducibility methods.
use the relationship between
recognizability and decidability to determine decidability
properties of problems.
describe concrete examples of
undecidable problems from different fields.
define, and explain the significance of, the "P = NP?"
question and NP-completeness.
describe concrete examples of
NP-complete problems from different fields.
prove lower bounds on time and space
complexity using diagonalization and polynomial time reducibility methods.
define deterministic and nondeterministic
computation time and space, and explain the relationships among them.
describe concrete examples of decidable problems
that are known to be unsolvable in polynomial time.
