Sipser 4.2

Read Sipser § 4.2

  1. Before reading the paragraphs after the statement of Theorem 4.11 – think about why we might believe the statement. Why would this language be undecidable, while the analogous languages corresponding to DFA’s and CFG’s are decidable? Explain your reasoning. After reading the proof, state whether or not you had the right idea.
  2. In Corollary 4.18, the author proves that the set of all Turing machines is countable, while the set of all languages is uncountable. Why do these two facts give the desired conclusion?
  3. Explain Figure 4.21 and how it illustrates the proof of Theorem 4.11.
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.