Sipser 5.1, 5.3

Read Sipser §5.1 and §5.3. Then review this overview of undecidable proof strategies.

  1. Outline the common strategy for proving that a language is undecidable.
  2. How are computation histories used in the proofs of Theorems 5.10 and 5.13?
  3. If $$A ≤_m B,$$ and B is a regular language, does that imply that A is a regular language? Why or why not?
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.