Midterm Study Guide
CSE 431: Introduction to Theory of Computation
Spring
2004
Midterm Exam, April 30, 2004
 Midterm 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 10:30 and ends at 11: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
 Topics covered from Davis
 Contributions of Leibniz, Boole, Frege, Cantor, Hilbert, Godel, Hilbert, and Turing
toward the
concept of a computer
 Development of formal logic and its influence on the development of
the computer
 Controversies: logic as a mathematical discipline, study of infinity,
Russell's paradox, intuitionism.
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 of Sipser and review chapters
16 of Davis.
 Do last year's midterm 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
ladner@cs.washington
(Last Update:
)