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.

ChurchTuring 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
 NPCompleteness and the CookLevin 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
 PSPACEcompleteness: TQBF, Noteverything problem for regular expressions
 EXPSPACEcompleteness: Noteverything 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
ladner@cs.washington
(Last Update:
)