{"id":262,"date":"2024-08-02T18:29:33","date_gmt":"2024-08-02T18:29:33","guid":{"rendered":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/?page_id=262"},"modified":"2024-08-02T18:29:33","modified_gmt":"2024-08-02T18:29:33","slug":"sipser-4-2","status":"publish","type":"page","link":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-4-2\/","title":{"rendered":"Sipser 4.2"},"content":{"rendered":"<p>Read Sipser &sect; 4.2<\/p>\n<ol>\n<li> Before reading the paragraphs after the statement of Theorem 4.11 \u2013 think about why we might believe the statement. Why would this language be undecidable, while the analogous languages corresponding to DFA\u2019s and CFG\u2019s are decidable? Explain your reasoning. After reading the proof, state whether or not you had the right idea.\n<li> 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?\n<li> Explain Figure 4.21 and how it illustrates the proof of Theorem 4.11.\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Read Sipser &sect; 4.2 Before reading the paragraphs after the statement of Theorem 4.11 \u2013 think about why we might believe the statement. Why would this language be undecidable, while the analogous languages corresponding to DFA\u2019s and CFG\u2019s are decidable? Explain your reasoning. After reading the proof, state whether or not you had the right &#8230; <a title=\"Sipser 4.2\" class=\"read-more\" href=\"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-4-2\/\" aria-label=\"Read more about Sipser 4.2\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":29,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-262","page","type-page","status-publish"],"_links":{"self":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/262","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/comments?post=262"}],"version-history":[{"count":1,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/262\/revisions"}],"predecessor-version":[{"id":263,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/262\/revisions\/263"}],"up":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/29"}],"wp:attachment":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/media?parent=262"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}