Sipser 5.2

Read Sipser §5.2

  1. As you begin to read The proof of Theorem 5.15, recall: What is the language $$A_{TM} ?$$
  2. In the first line of the proof of Theorem 5.15, why do we state, “We let TM R decide the PCP…”?
  3. Give your best attempt at a summary of Theorem 5.15.
css.php
The views and opinions expressed on individual web pages are strictly those of their authors and are not official statements of Grinnell College. Copyright Statement.