CS 373: Introduction to Theory of Computation

Fall 2012

The final exam will be cumulative, but will concentrate on the material covered since the second midterm (lecture 19 through 27; chapters 3, 4, 5, and 7 of Sipser's book). Key skills that will be tested in the final include the skill sets for midterm 1 and midterm 2, and in addition the following new material:

• Formal Definitions of Turing Machines
  • Know the formal definition of: Turing machines; instantaneous description; single step and a sequence of steps; acceptance of string; language recognized by a Turing machine; Turing recognizable languages or recursively enumerable languages; Turing decidable languages; Turing enumerators.
  • For an example Turing machine, know how to: describe it precisely using a transition diagram, or formal tuple notation; compute the behavior on a specific input; describe the language recognized by a Turing machine.
  • Know how to describe a new variant of Turing machine/automata formally, given its informal description in words.
• Turing Machine Constructions
  • Design a formal Turing machine for a given language.
  • Understand the simulations of different computational models on the Turing machine presented in class and the book. Concentrate on understanding the key ideas in these constructions and theorem proofs, rather than the detailed construction.
  • Constructing (informal) Turing simulation of new models of computation or for variants of the Turing machine model.
• Decidability and Recursive Enumerability
  • Know what it means for a language to be: decidable; undecidable; Turing recognizable/recursively enumerable; not recursively enumerable/Turing recognizable.
  • Know the relationship between recognition and enumerablity. That is, a language is Turing recognizable iff it is recursively enumerable; a language is decidable iff it can be enumerated in a canonical order (problem 3.18 and done in discussion 9).
  • Know the relationship between decidability and recursive enumerability: decidability implies recursive enumerability; a language is decidable iff both the language and its complement are recursively enumerable.
  • Know how to show that a language is decidable or recursively enumerable, by giving a pseudo-code of an algorithm.
  • Ability to classify languages as regular/decidable/recursively enumerable/not recursively enumerable.
  • Know the definitions of standard languages like the diagonal language, the universal language (ATM), halting problem, etc. Know which ones are undecidable/recursively enumerable/not recursively enumerable.
• Proof Techniques
  • Understand the diagonalization proof showing that the diagonal language is not recursively enumerable.
  • Understand diagonalization as a proof technique, for example, as how it implies that any model for decidable languages will be incomplete.
  • Understand the definition of reductions.
  • Understand how reductions can be used to both prove positive results (decidability/recursive enumerability) and negative results (undecidability/recursive enumerability).
  • Know how to prove that one language reduces to another by describing a reduction and proving that it satisfies the properties of a reduction.
  • Know how to use reductions to show a specific language to be undecidable/non-recursive-enumerable.
  • Understand the statement of Rice's Theorem.
  • Understand the proof of Rice's Theorem to get a better understanding of how to construct and use reductions --- we will not ask you to reproduce it.
  • Understand how to use Rice's Theorem to draw conclusions about a given language.
• Closure Properties
  • Know under which operations decidable and recursively enumerable languages are closed.
  • Know how to use closure properties to draw conclusions about other operations and languages.
• Complexity Theory
  • Know what it means for a deterministic/nondeterministic Turing machine to run in bounded time.
  • Know the relationship between time bounded deterministic and nondeterministic complexity classes.
  • Know the definition of P and NP.
  • Know how to show that a problem can be solved in P or NP.
  • Understand the polynomial time reductions, and the definition of NP-complete.