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