{"id":244,"date":"2024-08-02T18:13:09","date_gmt":"2024-08-02T18:13:09","guid":{"rendered":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/?page_id=244"},"modified":"2024-08-02T19:34:01","modified_gmt":"2024-08-02T19:34:01","slug":"sipser-7-4","status":"publish","type":"page","link":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-7-4\/","title":{"rendered":"Sipser 7.4"},"content":{"rendered":"<p><script id=\"MathJax-script\" async src=\"https:\/\/cdn.jsdelivr.net\/npm\/mathjax@3\/es5\/tex-mml-chtml.js\"><\/script><\/p>\n<p>Read the remaining portion of Sipser &sect; 7.4: pages 304 &#8211; 311<\/p>\n<ol>\n<li> Windows are used in the &phi;move formula of the proof of the Cook-Levine theorem. What does this boolean formula capture?\n<li> Suppose that we are translating the Turing machine M1 from figure 3.10 of the text (pp. 173 in the third edition) to a boolean formula according to Cook-Levine. Suppose that the current configuration $$C_i$$ under consideration is<br \/>\n$$x x q_3 1 0 \\# xx00 .$$<br \/>\n(Recall that a configuration represents the current contents of the tape, the current state, and the position of the tape head.)<br \/>\nDescribe (a) a legal window involving configurations $$C_i,$$ and the next configuration $$C_{i+1}.$$ <\/p>\n<p>and (b) an illegal window involving these configurations.<\/p>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Read the remaining portion of Sipser &sect; 7.4: pages 304 &#8211; 311 Windows are used in the &phi;move formula of the proof of the Cook-Levine theorem. What does this boolean formula capture? Suppose that we are translating the Turing machine M1 from figure 3.10 of the text (pp. 173 in the third edition) to a &#8230; <a title=\"Sipser 7.4\" class=\"read-more\" href=\"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/schedule\/sipser-7-4\/\" aria-label=\"Read more about Sipser 7.4\">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-244","page","type-page","status-publish"],"_links":{"self":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/244","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=244"}],"version-history":[{"count":4,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/244\/revisions"}],"predecessor-version":[{"id":283,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/244\/revisions\/283"}],"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=244"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}