Final Exam Study Guide
CSE 431: Introduction to Theory of Computation
Spring 2004

Final Exam, Monday, June 7, 2004, 8:30 - 10:20 am

• Final Exam Policies
  • You may bring the Davis book and the Sipser book to the midterm.
  • You may put your own personal notes, and assignments and their solutions to the midterm.
  • 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 computation histories.
  • Undecidability of the Post Correspondence Problem and applications.
  • Mapping Reducibility
  • Turing Reducibility
  • Decidability in Logic
  • Time and Space Complexity
  • P and NP
  • NP-Completeness and the Cook-Levin Theorem
  • Polynomial time reducibility constructions
  • Time and space complexity classes: L, NL, P, NP, PSPACE, EXPTIME, EXPSPACE
  • Relationship between time and space complexity
  • Hierarchy theorems
  • Savitch's theorem
  • Auxiliary Pushdown Store Machines and Alternating Turing Machines
  • PSPACE-completeness: TQBF, Not-everything problem for regular expressions
  • EXPSPACE-completeness: Not-everything problem for regular expressions with squaring
• Topics covered from Davis
  • Contributions of Leibniz, Boole, Frege, Cantor, Hilbert, Godel, and Turing toward the concept of a computer
  • Development of formal logic and its influence on the development of the computer
  • Godel's Incompleteness Theorem and its impact.
  • Controversies: logic as a mathematical discipline, study of infinity, Russell's paradox, intuitionism.
  • 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, 6.2,6.3, 7, 8, 9.1, 10.1, 10.2 of Sipser and review all chapters of Davis.
  • Do last year's final exam.
  • 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