Final Exam Study Guide
CSE 431: Introduction to Theory of Computation
Winter 2001

Final Exam, 8:30-10:20 a.m. Monday, June 4, 2001

• Final Policies
  • You may bring the Davis book but not the Sipser book to the midterm.
  • An 8 1/2 X 11 inch blue (or green) book is required.
  • You may put your own hand written notes in your blue book to aid you during the exam.
  • The exam begins promptly at 8:30 and ends at 10:20.
• Topics covered from Sipser
  • Turing machines: Basic definitions. Equivalence of multitape Turing machines and nondeterministic Turing machines with the one tape variety.
  • Turing enumerators and their properties.
  • Closure properties of Turing decidable and Turing recognizable languages.
  • Church-Turing Thesis: Turing machines are as powerful as any other models of computation.
  • The universal Turing machine.
  • The undecidability of the acceptance problem for Turing machines and diagonal arguments.
  • Use of reductions in showing undecidability. Reductions using accepting histories.
  • Undecidability of the Post Correspondence Problem and applications.
  • Mapping reducibility and its properties.
  • Time complexity, both deterministic and nondeterministic time complexity classes.
  • P and NP, polynomial time reducibility, NP-completeness, Cook-Levin Theorem.
  • Use of reductions to show NP-completeness. 3-CNF-SAT, 3-COLOR, Independent Set, Clique, Subset Sum, and other problems are NP-complete.
  • Space complexity, both deterministic and nondeterministic space complexity classes. Relationships between time and space complexity classes.
  • PSPACE completeness. TQBF, Not Everything problem for Regular Expressions.
  • Provably exponential problems. Temporal Logic Satisfiablility, Theory of addition, Not Everything problem for Regular Expressions with squaring.
• Topics covered from Davis
  • Contributions of Leibniz, Boole, Frege, Cantor, and Hilbert toward the concept of a computer
  • Development of formal logic and its influence on the development of the computer
  • Controversies: logic a mathematical discipline, study of infinity, Russell's paradox, intuitionism.
  • Godel's Incompleteness theorem and its impact.
  • Turing's contributions. Impact of the development of models of computation.
  • Impact of mathematical foundations and engineering on the building of the first computers.
  Study suggestions
  • Work in study groups to help each other out in preparation. Give each other problems to do in an exam setting. After doing the problems alone, critique each others answers.
  • Practice designing Turing machines. Practice doing some basic reductions.
  • Review chapters 3,4,5,7,8.1-3 of Sipser and review all of Davis.
  • Do concrete problems from Sipser:
    3.5, 3.7, 3.8, 3.9, 3.14, 3.15, 3.16, 3.19, 4.2, 4.7, 4.8, 4.18, 5.3, 5.10, 5.12, 5.13, 5.19, 5.20, 5.21, 7.16, 7.17, 7.20, 7.21, 7.22, 7.23, 8.9, 8.11, 8.18