Sipser 3.2

Read Sipser § 3.2

  1. Explain, in your own words, in the proof idea of Theorem 3.16, why the strategy is to use breadth-first, as opposed to depth-first, search.
  2. What does it mean for a model to be equivalent to the standard Turing machine model?
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.