Midterm Study Guide
CSE 431: Introduction to Theory of Computation
Winter 2001

Midterm Exam, April 27, 2001

• Midterm Policies
  • You may bring the Davis book but not the Sipser book to the midterm.
  • An 8 1/2 X 11 inch blue (or green) book is required.
  • You may put your own hand written notes in your blue book to aid you during the exam.
  • 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 accepting histories.
  • Undecidability of the Post Correspondence Problem and applications.
• Topics covered from Davis
  • Contributions of Leibniz, Boole, Frege, Cantor, and Hilbert toward the concept of a computer
  • Development of formal logic and its influence on the development of the computer
  • Controversies: logic 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 and 5 (except section 5.3) of Sipser and review chapters 1-5 of Davis.
  • 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