## 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.
• 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
• 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 1-6 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